New Null Space Results and Recovery Thresholds for Matrix Rank Minimization

Abstract

Nuclear norm minimization (NNM) has recently gained significant attention for its use in rank minimization problems. Similar to compressed sensing, using null space characterizations, recovery thresholds for NNM have been studied in \cite{arxiv,Recht_Xu_Hassibi}. However simulations show that the thresholds are far from optimal, especially in the low rank region. In this paper we apply the recent analysis of Stojnic for compressed sensing \cite{mihailo} to the null space conditions of NNM. The resulting thresholds are significantly better and in particular our weak threshold appears to match with simulation results. Further our curves suggest for any rank growing linearly with matrix size $n$ we need only three times of oversampling (the model complexity) for weak recovery. Similar to \cite{arxiv} we analyze the conditions for weak, sectional and strong thresholds. Additionally a separate analysis is given for special case of positive semidefinite matrices. We conclude by discussing simulation results and future research directions.

28 pages, 2 figures

References in corpus (3)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements
• Various thresholds for ${\ell }_1$-optimization in compressed sensing

Cited by in corpus (10)

• Minimax risk of matrix denoising by singular value thresholding
• A new perspective on least squares under convex constraint
• ROP: Matrix recovery via rank-one projections
• Theoretical Insights Into Multiclass Classification: A High-dimensional Asymptotic View
• On Convergence of the Alternating Projection Method for Matrix Completion and Sparse Recovery Problems
• Universality in Learning from Linear Measurements
• Uniform Convergence of Interpolators: Gaussian Width, Norm Bounds, and Benign Overfitting
• Separation-Free Super-Resolution from Compressed Measurements is Possible: an Orthonormal Atomic Norm Minimization Approach
• Subspace Expanders and Matrix Rank Minimization
• Sharp RIP Bound for Sparse Signal and Low-Rank Matrix Recovery