Statistical limits of dictionary learning: random matrix theory and the spectral replica method

Abstract

We consider increasingly complex models of matrix denoising and dictionary learning in the Bayes-optimal setting, in the challenging regime where the matrices to infer have a rank growing linearly with the system size. This is in contrast with most existing literature concerned with the low-rank (i.e., constant-rank) regime. We first consider a class of rotationally invariant matrix denoising problems whose mutual information and minimum mean-square error are computable using techniques from random matrix theory. Next, we analyze the more challenging models of dictionary learning. To do so we introduce a novel combination of the replica method from statistical mechanics together with random matrix theory, coined spectral replica method. This allows us to derive variational formulas for the mutual information between hidden representations and the noisy data of the dictionary learning problem, as well as for the overlaps quantifying the optimal reconstruction error. The proposed method reduces the number of degrees of freedom from $\Theta (N^2)$ matrix entries to $\Theta (N)$ eigenvalues (or singular values), and yields Coulomb gas representations of the mutual information which are reminiscent of matrix models in physics. The main ingredients are a combination of large deviation results for random matrices together with a new replica symmetric decoupling ansatz at the level of the probability distributions of eigenvalues (or singular values) of certain overlap matrices and the use of HarishChandra-Itzykson-Zuber spherical integrals.

References in corpus (57)

• Bilinear Generalized Approximate Message Passing
• Universality of the local spacing distribution in certain ensembles of hermitian Wigner matrices
• A random matrix model with localization and ergodic transitions
• Introduction to Random Matrices - Theory and Practice
• Products of Rectangular Random Matrices: Singular Values and Progressive Scattering
• Sparse Principal Components Analysis
• Correlations of Nearby Levels Induced by a Random Potential
• Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
• Induced QCD at Large N
• Spectrum of the Product of Independent Random Gaussian Matrices
• Phase transitions and sample complexity in Bayes-optimal matrix factorization
• Recent exact and asymptotic results for products of independent random matrices
• From non-ergodic eigenvectors to local resolvent statistics and back: a random matrix perspective
• Eigenvalues and Singular Values of Products of Rectangular Gaussian Random Matrices
• Weak Commutation Relations and Eigenvalue Statistics for Products of Rectangular Random Matrices
• On the Large N Limit of the Itzykson-Zuber Integral
• Constrained Low-rank Matrix Estimation: Phase Transitions, Approximate Message Passing and Applications
• Random covariance matrices: Universality of local statistics of eigenvalues
• Singular value correlation functions for products of Wishart random matrices
• Singular value statistics of matrix products with truncated unitary matrices
• Optimality and Sub-optimality of PCA I: Spiked Random Matrix Models
• Rotational invariant estimator for general noisy matrices
• Universal microscopic correlation functions for products of independent Ginibre matrices
• The Lévy-Rosenzweig-Porter random matrix ensemble
• On some integrals over the U(N) unitary group and their large N limit
• Induced Ginibre ensemble of random matrices and quantum operations
• On the Asymptotic Spectrum of Products of Independent Random Matrices
• A note on classical ground state energies
• Universal microscopic correlation functions for products of truncated unitary matrices
• Infinite Products of Large Random Matrices and Matrix-valued Diffusion
• The adaptive interpolation method for proving replica formulas. Applications to the Curie-Weiss and Wigner spike models
• Generalizations of some integrals over the unitary group
• Fundamental limits of low-rank matrix estimation: the non-symmetric case
• High-temperature Expansions and Message Passing Algorithms
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• Products of Independent Quaternion Ginibre Matrices and their Correlation Functions
• Products of Independent Gaussian Random Matrices
• Instanton Approach to Large $N$ Harish-Chandra-Itzykson-Zuber Integrals
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Singular values for products of complex Ginibre matrices with a source: hard edge limit and phase transition
• Solvable Matrix Models
• The solution of the deep Boltzmann machine on the Nishimori line
• Statistical Mechanics of Dictionary Learning
• An inference problem in a mismatched setting: a spin-glass model with Mattis interaction
• Hamilton-Jacobi equations for mean-field disordered systems
• The multi-species mean-field spin-glass on the Nishimori line
• Random matrix ensembles involving Gaussian Wigner and Wishart matrices, and biorthogonal structure
• Finite Size Corrections and Likelihood Ratio Fluctuations in the Spiked Wigner Model
• On the large N limit of matrix integrals over the orthogonal group
• Hydrodynamical spectral evolution for random matrices
• Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
• Kosterlitz--Thouless Phase Transitions on Discretized Random Surfaces
• Large Deviations Asymptotics of Rectangular Spherical Integral
• Mismatched Estimation of rank-one symmetric matrices under Gaussian noise
• D-dimensional Induced Gauge Theory as a Solvable Matrix Model
• Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization
• Rank-one matrix estimation: analytic time evolution of gradient descent dynamics

Cited by in corpus (13)

• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Depth induces scale-averaging in overparameterized linear Bayesian neural networks
• Matrix factorization with neural networks
• Singular Vectors of Sums of Rectangular Random Matrices and Optimal Estimators of High-Rank Signals: The Extensive Spike Model
• Matrix denoising: Bayes-optimal estimators via low-degree polynomials
• Phase transitions induced by standard and predetermined measurements in transmon arrays
• Bayesian reconstruction of memories stored in neural networks from their connectivity
• Spherical Integrals of Sublinear Rank
• Some observations on the ambivalent role of symmetries in Bayesian inference problems
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens
• Optimal generalisation and learning transition in extensive-width shallow neural networks near interpolation
• Statistical mechanics of extensive-width Bayesian neural networks near interpolation
• Statistical physics of deep learning: Optimal learning of a multi-layer perceptron near interpolation