Low-Rank Matrix Recovery Through Rank-One Projections
summary
Measurements take the form Yi = beta_i^T A gamma_i + noise with Xi = beta_i gamma_i^T, so recovery uses rank-one measurements and a convex constrained nuclear-norm minimization to estimate A. Provable sample complexity is N on the order of r times the ambient dimension (counting degrees of freedom), exact recovery in the noiseless case, and a Frobenius-error bound that matches a minimax lower bound up to constants. Works for sub-Gaussian/±1 designs, symmetric reuse of beta, approximate low-rank A, and applies to phase retrieval and covariance-from-projections.
AI-written summary · about
chapters (11)
- 0:00Inference on High-Dimensional Matrices
- 1:04Recovery of Low-Rank Matrix
- 1:34General Formulation of Matrix Recovery
- 4:04Compressed Sensing
- 5:09Low-Rank Matrix Recovery
- 9:33Constrained Nuclear Norm Minimization
- 11:33Example: Recovery of MIT Logo
- 16:46Recovery of Symmetric Low-Rank Matrix
- 18:04Phase Retrieval
- 19:37Estimating Spiked Covariance Matrix Based on Projections
- 20:25Other Related Problems
related talks
37mLow-rank Matrix Completion: Adaptive Sampling Can Help When, How?
45mNoisy Estimation of Simultaneously Structured Models
01h 04mUser-Friendly Tools for Random Matrices I
27mOptimal Spectral Recovery Of A Planted Vector In A Subspace
32mRandomized Numerical Linear Algebra: Overview
38mAll-or-Nothing Statistical and Computational Phase Transitions in Sparse Spiked Matrix Estimation
39mThe Overlap Gap Property in Principal Submatrix Recovery
29mComputational Barriers to Estimation from Low-Degree Polynomials