Near-optimal matrix recovery from random linear measurements

DOI10.1073/PNAS.1705490115zbMATH Open1416.65130arXiv1705.09958OpenAlexW2619269121WikidataQ89241109 ScholiaQ89241109MaRDI QIDQ4967445FDOQ4967445

Elad Romanov, Matan Gavish

Publication date: 3 July 2019

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

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,ldots,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.

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

Recommendations

• The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
• Uniqueness conditions for low-rank matrix recovery
• Iterative hard thresholding for low-rank recovery from rank-one projections
• Normalized iterative hard thresholding for matrix completion
• Stable low-rank matrix recovery via null space properties

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Applications of mathematical programming (90C90) Numerical linear algebra (65F99)

Cited In (7)

• Convex Recovery of a Structured Signal from Independent Random Linear Measurements
• Max-norm optimization for robust matrix recovery
• Uniform Recovery Bounds for Structured Random Matrices in Corrupted Compressed Sensing
• On the universality of noiseless linear estimation with respect to the measurement matrix
• Worst-case recovery guarantees for least squares approximation using random samples
• Recovery of Short, Complex Linear Combinations Via&lt;tex&gt;$ell _1$&lt;/tex&gt;Minimization
• On exact recovery of sparse vectors from linear measurements

This page was built for publication: Near-optimal matrix recovery from random linear measurements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4967445)