Near-optimal matrix recovery from random linear measurements

Abstract

In matrix recovery from random linear measurements, one is interested in recovering an unknown $M$-by-$N$ matrix $X_0$ from $n<MN$ measurements $y_i=Tr(A_i^T{X}_0)$ where each $A_i$ is an $M$-by-$N$ measurement matrix with i.i.d random entries, $i=1,\dots ,n$. We present a novel matrix recovery algorithm, based on approximate message passing, which iteratively applies an optimal singular value shrinker -- a nonconvex nonlinearity tailored specifically for matrix estimation. Our algorithm typically converges exponentially fast, offering a significant speedup over previously suggested matrix recovery algorithms, such as iterative solvers for Nuclear Norm Minimization (NNM). It is well known that there is a recovery tradeoff between the information content of the object $X_0$ to be recovered (specifically, its matrix rank $r$) and the number of linear measurements $n$ from which recovery is to be attempted. The precise tradeoff between $r$ and $n$, beyond which recovery by a given algorithm becomes possible, traces the so-called phase transition curve of that algorithm in the $(r,n)$ plane. The phase transition curve of our algorithm is noticeably better than that of NNM. Interestingly, it is close to the information-theoretic lower bound for the minimal number of measurements needed for matrix recovery, making it not only state-of-the-art in terms of convergence rate, but also near-optimal in terms of the matrices it successfully recovers.

arXiv commentSupporting information (SI Appendix) and code available at: https://purl.stanford.edu/rt605yk2478

References in corpus (16)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Message Passing Algorithms for Compressed Sensing
• Quantum state tomography via compressed sensing
• Recovering low-rank matrices from few coefficients in any basis
• An overview of low-rank matrix recovery from incomplete observations
• Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
• Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing
• Bilinear Generalized Approximate Message Passing
• Unbiased Risk Estimates for Singular Value Thresholding and Spectral Estimators
• Matrix Completion from Noisy Entries
• Minimax risk of matrix denoising by singular value thresholding
• Parametric Bilinear Generalized Approximate Message Passing
• The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
• Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
• Near-optimal matrix recovery from random linear measurements
• Phase diagram of matrix compressed sensing

Cited by in corpus (4)

• Bilinear Recovery using Adaptive Vector-AMP
• Near-optimal matrix recovery from random linear measurements
• On Compressed Sensing of Binary Signals for the Unsourced Random Access Channel
• Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokens