Mutual information for symmetric rank-one matrix estimation: A proof of the replica formula
Factorizing low-rank matrices has many applications in machine learning and statistics. For probabilistic models in the Bayes optimal setting, a general expression for the mutual information has been proposed using heuristic statistical physics computations, and proven in few specific cases. Here, we show how to rigorously prove the conjectured formula for the symmetric rank-one case. This allows to express the minimal mean-square-error and to characterize the detectability phase transitions in a large set of estimation problems ranging from community detection to sparse PCA. We also show that for a large set of parameters, an iterative algorithm called approximate message-passing is Bayes optimal. There exists, however, a gap between what currently known polynomial algorithms can do and what is expected information theoretically. Additionally, the proof technique has an interest of its own and exploits three essential ingredients: the interpolation method introduced in statistical physics by Guerra, the analysis of the approximate message-passing algorithm and the theory of spatial coupling and threshold saturation in coding. Our approach is generic and applicable to other open problems in statistical estimation where heuristic statistical physics predictions are available.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Information-theoretic limits of a multiview low-rank symmetric spiked matrix model
We consider a generalization of an important class of high-dimensional inference problems, namely spiked symmetric matrix models, often used as probabilistic models for principal component analysis. Such paradigmatic mod…
Rank-one matrix estimation: analysis of algorithmic and information theoretic limits by the spatial coupling method
Factorizing low-rank matrices is a problem with many applications in machine learning and statistics, ranging from sparse PCA to community detection and sub-matrix localization. For probabilistic models in the Bayes opti…
Community DetectionCompressive SensingStatistical limits of dictionary learning: random matrix theory and the spectral replica method
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. T…
DenoisingDictionary LearningInterpretable Fault Detection using Projections of Mutual Information Matrix
This paper presents a novel mutual information (MI) matrix based method for fault detection. Given a $m$-dimensional fault process, the MI matrix is a $m \times m$ matrix in which the $(i,j)$-th entry measures the MI val…
Density EstimationFault DetectionClutter Edges Detection Algorithms for Structured Clutter Covariance Matrices
This letter deals with the problem of clutter edge detection and localization in training data. To this end, the problem is formulated as a binary hypothesis test assuming that the ranks of the clutter covariance matrix …
Edge Detection