Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements

Abstract

This paper presents several novel theoretical results regarding the recovery of a low-rank matrix from just a few measurements consisting of linear combinations of the matrix entries. We show that properly constrained nuclear-norm minimization stably recovers a low-rank matrix from a constant number of noisy measurements per degree of freedom; this seems to be the first result of this nature. Further, the recovery error from noisy data is within a constant of three targets: 1) the minimax risk, 2) an oracle error that would be available if the column space of the matrix were known, and 3) a more adaptive oracle error which would be available with the knowledge of the column space corresponding to the part of the matrix that stands above the noise. Lastly, the error bounds regarding low-rank matrices are extended to provide an error bound when the matrix has full rank with decaying singular values. The analysis in this paper is based on the restricted isometry property (RIP) introduced in [6] for vectors, and in [22] for matrices.

30 pages

References in corpus (7)

• Quantum state tomography via compressed sensing
• Robust Principal Component Analysis?
• A Singular Value Thresholding Algorithm for Matrix Completion
• Matrix Completion from a Few Entries
• Guaranteed Rank Minimization via Singular Value Projection
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• SET: an algorithm for consistent matrix completion

Cited by in corpus (47)

• Templates for Convex Cone Problems with Applications to Sparse Signal Recovery
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Joint variable and rank selection for parsimonious estimation of high-dimensional matrices
• Matrix Completion via Max-Norm Constrained Optimization
• New Null Space Results and Recovery Thresholds for Matrix Rank Minimization
• Performance Analysis of Sparse Recovery Based on Constrained Minimal Singular Values
• Guaranteed clustering and biclustering via semidefinite programming
• Stable Principal Component Pursuit
• Provable Meta-Learning of Linear Representations
• Universal low-rank matrix recovery from Pauli measurements
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling
• Compressed Sensing of Simultaneous Low-Rank and Joint-Sparse Matrices
• Guaranteed recovery of quantum processes from few measurements
• Understanding Generalization and Optimization Performance of Deep CNNs
• Rank penalized estimation of a quantum system
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Asymptotic equivalence of quantum state tomography and noisy matrix completion
• Sharp MSE Bounds for Proximal Denoising
• Blind Deconvolution using Convex Programming
• Simultaneously Structured Models with Application to Sparse and Low-rank Matrices
• Improving compressed sensing with the diamond norm
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• Sharp oracle inequalities for the prediction of a high-dimensional matrix
• Selective Factor Extraction in High Dimensions
• Rapid characterisation of linear-optical networks via PhaseLift
• Towards the study of least squares estimators with convex penalty
• Blind Identification of ARX Models with Piecewise Constant Inputs
• How Many Samples is a Good Initial Point Worth in Low-rank Matrix Recovery?
• Simple Bounds for Recovering Low-complexity Models
• Empirical Chaos Processes and Blind Deconvolution
• Optimal spectral norm rates for noisy low-rank matrix completion
• Optimal Schatten-q and Ky-Fan-k Norm Rate of Low Rank Matrix Estimation
• Learning Non-Parametric Basis Independent Models from Point Queries via Low-Rank Methods
• Sufficient Conditions for Low-rank Matrix Recovery, Translated from Sparse Signal Recovery
• On robust width property for Lasso and Dantzig selector
• Compressed Subspace Matching on the Continuum
• Sequential scaled sparse factor regression
• Sparse Recovery with Coherent Tight Frames via Analysis Dantzig Selector and Analysis LASSO
• Sharp Oracle Inequalities in Low Rank Estimation
• Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient
• Adaptive estimation of the rank of the coefficient matrix in high dimensional multivariate response regression models
• Low-rank matrix recovery via iteratively reweighted least squares minimization
• On Cross-validation for Sparse Reduced Rank Regression
• Painless Breakups -- Efficient Demixing of Low Rank Matrices
• Provable Low Rank Phase Retrieval
• Stochastic continuum armed bandit problem of few linear parameters in high dimensions