Matrix denoising: Bayes-optimal estimators via low-degree polynomials

Abstract

We consider the additive version of the matrix denoising problem, where a random symmetric matrix $S$ of size $n$ has to be inferred from the observation of $Y=S+Z$, with $Z$ an independent random matrix modeling a noise. For prior distributions of $S$ and $Z$ that are invariant under conjugation by orthogonal matrices we determine, using results from first and second order free probability theory, the Bayes-optimal (in terms of the mean square error) polynomial estimators of degree at most $D$, asymptotically in $n$, and show that as $D$ increases they converge towards the estimator introduced by Bun, Allez, Bouchaud and Potters in [IEEE Transactions on Information Theory 62, 7475 (2016)]. We conjecture that this optimality holds beyond strictly orthogonally invariant priors, and provide partial evidences of this universality phenomenon when $S$ is an arbitrary Wishart matrix and $Z$ is drawn from the Gaussian Orthogonal Ensemble, a case motivated by the related extensive rank matrix factorization problem.

44 pages, v2 : updated references, minor clarifications

References in corpus (20)

• Integration with respect to the Haar measure on unitary, orthogonal and symplectic group
• Statistical physics of inference: Thresholds and algorithms
• Local semicircle law and complete delocalization for Wigner random matrices
• On Asymptotic Properties of Large Random Matrices with Independent Entries
• Cleaning large correlation matrices: tools from random matrix theory
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• On the Large N Limit of the Itzykson-Zuber Integral
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Rotational invariant estimator for general noisy matrices
• Computational Barriers to Estimation from Low-Degree Polynomials
• High-temperature Expansions and Message Passing Algorithms
• Instanton Approach to Large $N$ Harish-Chandra-Itzykson-Zuber Integrals
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Sharp Bounds for Sums Associated to Graphs of Matrices
• Statistical limits of dictionary learning: random matrix theory and the spectral replica method
• Real Second Order Freeness and Haar Orthogonal Matrices
• Real second-order freeness and the asymptotic real second-order freeness of several real matrix ensembles
• Matrix factorization with neural networks
• Cumulants, lattice paths, and orthogonal polynomials
• Singular Vectors of Sums of Rectangular Random Matrices and Optimal Estimators of High-Rank Signals: The Extensive Spike Model

Cited by in corpus (5)

• The Wishart--Rosenzweig--Porter random matrix ensemble
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation