The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising

DOI10.1073/pnas.1306110110zbMath1292.94004arXiv1302.2331OpenAlexW2119787772WikidataQ30540129 ScholiaQ30540129MaRDI QIDQ5170964

Matan Gavish, David L. Donoho, Andrea Montanari

Publication date: 25 July 2014

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1302.2331

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items

Recovering Structured Signals in Noise: Least-Squares Meets Compressed Sensing, Sharp MSE bounds for proximal denoising, Statistical Inference, Learning and Models in Big Data, Super-twisting sliding-mode observer-based model reference adaptive speed control for PMSM drives, Local laws for multiplication of random matrices, CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion, Minimax risk of matrix denoising by singular value thresholding, Overcoming the limitations of phase transition by higher order analysis of regularization techniques, Unnamed Item, An arbitrary-order differentiator design paradigm with adaptive gains, Ranking recovery from limited pairwise comparisons using low-rank matrix completion, Edge statistics of large dimensional deformed rectangular matrices

Uses Software

• SeDuMi

Cites Work

• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• The LASSO Risk for Gaussian Matrices
• Recovering Low-Rank Matrices From Few Coefficients in Any Basis
• The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing
• Neighborliness of randomly projected simplices in high dimensions
• DISTRIBUTION OF EIGENVALUES FOR SOME SETS OF RANDOM MATRICES