ROP: Matrix recovery via rank-one projections

Abstract

Estimation of low-rank matrices is of significant interest in a range of contemporary applications. In this paper, we introduce a rank-one projection model for low-rank matrix recovery and propose a constrained nuclear norm minimization method for stable recovery of low-rank matrices in the noisy case. The procedure is adaptive to the rank and robust against small perturbations. Both upper and lower bounds for the estimation accuracy under the Frobenius norm loss are obtained. The proposed estimator is shown to be rate-optimal under certain conditions. The estimator is easy to implement via convex programming and performs well numerically. The techniques and main results developed in the paper also have implications to other related statistical problems. An application to estimation of spiked covariance matrices from one-dimensional random projections is considered. The results demonstrate that it is still possible to accurately estimate the covariance matrix of a high-dimensional distribution based only on one-dimensional projections.

Published in at http://dx.doi.org/10.1214/14-AOS1267 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (6)

• Sparse PCA: Optimal rates and adaptive estimation
• ROP: Matrix recovery via rank-one projections
• Compressed Sensing and Affine Rank Minimization under Restricted Isometry
• New Null Space Results and Recovery Thresholds for Matrix Rank Minimization
• Rank penalized estimation of a quantum system
• Asymptotic equivalence of quantum state tomography and noisy matrix completion

Cited by in corpus (14)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Gridless DOA Estimation and Root-MUSIC for Non-Uniform Arrays
• Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrieval
• ROP: Matrix recovery via rank-one projections
• Leveraging the Restricted Isometry Property: Improved Low-Rank Subspace Decomposition for Hybrid Millimeter-Wave Systems
• Optimal large-scale quantum state tomography with Pauli measurements
• The Dantzig selector: Recovery of Signal via ${\ell }_1-\alpha {\ell }_2$ Minimization
• Matrix factorization for multivariate time series analysis
• Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks
• Interferometric lensless imaging: rank-one projections of image frequencies with speckle illuminations
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Information-theoretic Bounds on Matrix Completion under Union of Subspaces Model
• Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix