Matrix denoising beyond rotational invariance

Denoising a large matrix modeled as a product of two factors is a hard problem, both algorithmically, and from the viewpoint of theoretical analysis, especially if its rank is proportional to its dimension. Its applications range from signal processing, to representation learning, sparse coding, community detection, video processing, recommender systems and many more.

One can formulate the problem as an inference task, where a Statistician is given the set of observations Y, that is the result of the product of two N x M matrices X, identical to each other in our case, with some additional blurring noise Z.

The goal is then to estimate the product XX given Y, and to establish how well it is possible to perform this task. The minimum mean square error for this estimation problem is intimately connected to the Mutual Information (MI) between the data Y and the matrix to denoise XX.

The exact MI for this problem is computed only when X is generated with a rotationally invariant prior distribution, namely any conjugation of X with an orthogonal matrix does not change the probability law of it, or when M is finite. The classical example of the first situation is when the elements of X are identically and independently distributed as standard Gaussians. Beyond this setting few results can be found. The reason is that the model is not a usual spin glass because of the growing rank dimension, nor a matrix model due to the lack of rotation symmetry, but rather a hybrid between the two.

In our paper we make progress towards the understanding of this model with a completely factorized prior on the elements of X, both from a phenomenological and theoretical point of view.

Concerning the first, via extensive Monte Carlo simulations we find a region of the parameters of the model, (α=M/N,λ), where the MI is universal, namely it is insensitive of the fine details brought in by the prior used to generate X. Hence, the model behaves as if only Gaussian variables where involved.

However, we also prove that this universality must break down for high enough signal-to-noise ratio λ, giving rise to what we called factorisation phase, as opposed to the universal phase, called denoising phase. The latter is characterised by the fact that denoising XX taking into account its factorised inner structure does not yield any improvement. On the contrary, in the factorisation phase the factorised structure plays a crucial role decreasing drastically the minimum mean square error in the estimation of XX.

Afterwards we build a multiscale mean-field theory, based on a combination of the cavity and the replica methods. This theory relies on decouplings assumption that are typical of mean-field regimes, and it yields an excellent approximation to the true minimum mean square error in the factorisation phase, where the model indeed seems to behave in mean-field fashion. In the figure on the right, you can see yourself the agreement between our theory (solid black line) and the points of the finite size experiments.

This is just a preview of our paper, which contains many further insights regarding the nature of this denoising-factorisation transition. If you are curious to know how we did it, check our paper at https://doi.org/10.48550/arXiv.2411.01974 or send us an email!