ROP: Matrix Recovery via Rank-One Projections

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.

• Publication year

  2013

• Venue

  arXiv.org

• Publication date

  2013-10-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1214/14-AOS1267arXiv 1310.5791
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Optimal estimation and rank detection for sparse spiked covariance matrices

  2014cited by this paper
• The bounds of restricted isometry constants for low rank matrices recovery

  2013cited by this paper
• Asymptotic equivalence of quantum state tomography and noisy matrix completion

  2013cited by this paper
• Compressed Sensing and Affine Rank Minimization Under Restricted Isometry

  2013influential reference
• Optimal estimation and rank detection for sparse spiked covariance matrices

  2013cited by this paper
• Sketching Sparse Matrices

  2013cited by this paper
• Exact and Stable Covariance Estimation From Quadratic Sampling via Convex Programming

  2013influential reference
• Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices

  2013influential reference
• Sharp RIP Bound for Sparse Signal and Low-Rank Matrix Recovery

  2013influential reference
• Covariance sketching

  2012cited by this paper
• Rank penalized estimation of a quantum system

  2012cited by this paper
• Asymptotic Equivalence of Quantum State Tomography and Trace Regression

  2012cited by this paper
• MINIMAX BOUNDS FOR SPARSE PCA WITH NOISY HIGH-DIMENSIONAL DATA.

  2012cited by this paper
• Sparse PCA: Optimal rates and adaptive estimation

  2012cited by this paper
• A simplified approach to recovery conditions for low rank matrices

  2011cited by this paper
• Tight Oracle Inequalities for Low-Rank Matrix Recovery From a Minimal Number of Noisy Random Measurements

  2011influential reference
• PhaseLift: Exact and Stable Signal Recovery from Magnitude Measurements via Convex Programming

  2011cited by this paper
• Nuclear norm penalization and optimal rates for noisy low rank matrix completion

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

  2010influential reference
• A nullspace analysis of the nuclear norm heuristic for rank minimization

  2010cited by this paper
• Nonparametric Detection of Signals by Information Theoretic Criteria: Performance Analysis and an Improved Estimator

  2010cited by this paper
• New Null Space Results and Recovery Thresholds for Matrix Rank Minimization

  2010cited by this paper
• Quantum state tomography via compressed sensing.

  2009cited by this paper
• Matrix Factorization Techniques for Recommender Systems

  2009cited by this paper
• Robust principal component analysis?

  2009influential reference
• The Power of Convex Relaxation: Near-Optimal Matrix Completion

  2009cited by this paper
• A Simpler Approach to Matrix Completion

  2009influential reference
• Estimation of (near) low-rank matrices with noise and high-dimensional scaling

  2009cited by this paper
• Estimation of high-dimensional low-rank matrices

  2009cited by this paper
• Spectral norm of products of random and deterministic matrices

  2008cited by this paper
• Exact Matrix Completion via Convex Optimization

  2008influential reference
• On Recovery of Sparse Signals Via $\ell _{1}$ Minimization

  2008cited by this paper
• Graph Implementations for Nonsmooth Convex Programs

  2008cited by this paper
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization

  2007influential reference
• High dimensional covariance matrix estimation using a factor model

  2007cited by this paper
• Principal components analysis corrects for stratification in genome-wide association studies

  2006cited by this paper
• An Architecture for Compressive Imaging

  2006cited by this paper
• Population Structure and Eigenanalysis

  2006cited by this paper
• ADAPTIVE ESTIMATION OF A QUADRATIC FUNCTIONAL BY MODEL SELECTION

  2001cited by this paper
• On the distribution of the largest eigenvalue in principal components analysis

  2001cited by this paper
• Lambertian reflectance and linear subspaces

  2001cited by this paper
• Distance Matrix Completion by Numerical Optimization

  1997cited by this paper
• Detection of signals by information theoretic criteria

  1985cited by this paper
• Singular Value Decomposition (SVD) Image Coding

  1976cited by this paper

• Provably Learning Attention with Queries

  2026influential citation
• Near-Quadratic Convergence of the Gauss–Newton Method for Complex Phase Retrieval

  2026cites this paper
• Robust Sparse Signal Recovery with Outliers: A Hard Thresholding Pursuit Approach Based on LAD

  2026influential citation
• SCaLE: Switching Cost aware Learning and Exploration

  2026influential citation
• A Smoothing Newton Method for Rank-one Matrix Recovery

  2025cites this paper
• Near-optimal Reconfigurable Intelligent Surface Configuration: Blind Beamforming with Sensing

  2025cites this paper
• Sparse Signal Recovery From Quadratic Systems with Full-Rank Matrices

  2025cites this paper
• The restricted isometry property of block diagonal matrices generated by φ -sub-Gaussian variables

  2025cites this paper
• Theoretical Guarantees for Low-Rank Compression of Deep Neural Networks

  2025cites this paper
• Robust Gridless DOA Estimation Using Coprime Array Under Nonuniform Noise

  2025cites this paper
• Random Features for Grassmannian Kernels

  2025cites this paper
• Phase retrieval and matrix sensing via benign and overparametrized nonconvex optimization

  2025cites this paper
• Robust Outlier Bound Condition to Phase Retrieval with Adversarial Sparse Outliers

  2025cites this paper
• On the Performance of Amplitude-Based Models for Low-Rank Matrix Recovery

  2025cites this paper
• On Relatively Smooth Optimization over Riemannian Manifolds

  2025cites this paper
• Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix

  2024cites this paper
• Matrix Completion via Residual Spectral Matching

  2024cites this paper
• Geometric Characteristic in Phaseless Operator and Structured Matrix Recovery

  2024cites this paper
• Exact matrix completion via smooth matrix factorization

  2024cites this paper
• Compressive Radio-Interferometric Sensing With Random Beamforming as Rank-One Signal Covariance Projections

  2024cites this paper
• Convergence of projected subgradient method with sparse or low-rank constraints

  2024influential citation
• Trend of high dimensional time series estimation using low-rank matrix factorization: heuristics and numerical experiments via the TrendTM package

  2024cites this paper
• Geometric Characteristics and Stable Guarantees for Phaseless Operators and Structured Matrix Restoration

  2024cites this paper
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms

  2024cites this paper
• Restricted Isometry Property of Rank-One Measurements with Random Unit-Modulus Vectors

  2024influential citation
• Efficient 2D DOA Estimation via Decoupled Projected Atomic Norm Minimization

  2024cites this paper
• Enhanced DOA Estimation Through Coprime Planar Coarray Interpolation via Alternating Projection

  2024cites this paper
• Interferometric Lensless Imaging: Rank-One Projections of Image Frequencies With Speckle Illuminations

  2023cites this paper
• Interferometric single-pixel imaging with a multicore fiber

  2023cites this paper
• Compressive Recovery of Sparse Precision Matrices

  2023cites this paper
• The Dantzig Selector: Sparse Signals Recovery via l_p-q Minimization

  2023cites this paper
• Perceptual adjustment queries and an inverted measurement paradigm for low-rank metric learning

  2023cites this paper
• Two novel models with nuclear norm for robust matrix recovery

  2023cites this paper
• Linearly Embedding Sparse Vectors from $\ell_2$ to $\ell_1$ via Deterministic Dimension-Reducing Maps

  2023cites this paper
• A General Algorithm for Solving Rank-one Matrix Sensing

  2023cites this paper
• Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression

  2023cites this paper
• Robust Outlier Bound Condition to Phase Retrieval with Adversarial Sparse Outliers

  2023cites this paper
• Completion of Matrices with Low Description Complexity

  2023cites this paper
• Sharpness and well-conditioning of nonsmooth convex formulations in statistical signal recovery

  2023cites this paper
• ROP inception: signal estimation with quadratic random sketching

  2022cites this paper
• Signal Processing with Optical Quadratic Random Sketches

  2022cites this paper
• Computationally Efficient and Statistically Optimal Robust Low-rank Matrix and Tensor Estimation

  2022cites this paper
• Computationally Efficient and Statistically Optimal Robust Low-rank Matrix Estimation

  2022cites this paper
• A global exact penalty for rank-constrained optimization problem and applications

  2022cites this paper
• Learning the Structure of Large Networked Systems Obeying Conservation Laws

  2022cites this paper
• Bures-Wasserstein Barycenters and Low-Rank Matrix Recovery

  2022influential citation
• Flat minima generalize for low-rank matrix recovery

  2022influential citation
• Low-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence

  2021cites this paper
• Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence

  2021cites this paper
• Parting Thoughts

  2021cites this paper
• On Riemannian Optimization over Positive Definite Matrices with the Bures-Wasserstein Geometry

  2021cites this paper
• Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization

  2021influential citation
• The Dantzig selector: recovery of signal via ℓ 1 − αℓ 2 minimization

  2021influential citation
• ℓ1 − αℓ2 minimization methods for signal and image reconstruction with impulsive noise removal

  2020cites this paper
• Learning Polynomial Neural Networks via Low Rank Tensor Recovery

  2020cites this paper
• Effective Data-Aware Covariance Estimator From Compressed Data

  2020cites this paper
• Finiteness of fibers in matrix completion via Plücker coordinates

  2020cites this paper
• Gridless DOA Estimation and Root-MUSIC for Non-Uniform Linear Arrays

  2020cites this paper
• Low-Rank Matrix Estimation From Rank-One Projections by Unlifted Convex Optimization

  2020cites this paper
• Norm and trace estimation with random rank-one vectors

  2020cites this paper
• Performance bound of the intensity-based model for noisy phase retrieval

  2020cites this paper
• For Matrix Recovery, Rank Restricted Isometry Property and Robust Uniform Boundedness Property Imply Rank Robust Null Space Property

  2020influential citation
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs

  2020cites this paper
• Connecting weighted automata, tensor networks and recurrent neural networks through spectral learning

  2020cites this paper
• Composite optimization for robust rank one bilinear sensing

  2020cites this paper
• Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence

  2020cites this paper
• Spectral Methods for Data Science: A Statistical Perspective

  2020cites this paper
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets

  2020influential citation
• On Low-rank Trace Regression under General Sampling Distribution

  2019influential citation
• Low-Rank Matrix Recovery with Composite Optimization: Good Conditioning and Rapid Convergence

  2019cites this paper
• Solving Quadratic Equations via Amplitude-based Nonconvex Optimization

  2019cites this paper
• Gridless DOA Estimation via. Alternating Projections

  2019cites this paper
• Universality in Learning from Linear Measurements

  2019cites this paper
• Provable algorithms for nonlinear models in machine learning and signal processing

  2019influential citation
• Deterministic Completion of Rectangular Matrices Using Asymmetric Ramanujan Graphs: Exact and Stable Recovery

  2019cites this paper
• Statistical inferences of linear forms for noisy matrix completion

  2019cites this paper
• Sample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior

  2019cites this paper
• ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching

  2019cites this paper
• Blind normalization of public high-throughput databases

  2019cites this paper
• A Spectral Method for Estimating Low-Rank Subspaces from Nonlinear Measurements

  2019cites this paper
• Fast and Provable Algorithms for Learning Two-Layer Polynomial Neural Networks

  2019influential citation
• Which Factorization Machine Modeling is Better: A Theoretical Answer with Optimal Guarantee

  2019cites this paper
• Bilinear Bandits with Low-rank Structure

  2019cites this paper
• Matrix factorization for multivariate time series analysis

  2019cites this paper
• Jointly low-rank and bisparse recovery: Questions and partial answers

  2019cites this paper
• Towards Provable Learning of Polynomial Neural Networks Using Low-Rank Matrix Estimation

  2018influential citation
• Efficient and Robust Recovery of Signal and Image in Impulsive Noise via $\ell_1-\alpha \ell_2$ Minimization

  2018cites this paper
• Stable Recovery of Signals From Highly Corrupted Measurements

  2018cites this paper
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview

  2018cites this paper
• Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning

  2018cites this paper
• Two-stage Method for the Reconstruction of a Low-Rank Matrix

  2018cites this paper
• Convex and Nonconvex Formulations for Mixed Regression With Two Components: Minimax Optimal Rates

  2018cites this paper
• Leveraging the Restricted Isometry Property: Improved Low-Rank Subspace Decomposition for Hybrid Millimeter-Wave Systems

  2018cites this paper
• Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation: Recent Theory and Fast Algorithms via Convex and Nonconvex Optimization

  2018cites this paper
• Nonconvex Matrix Factorization From Rank-One Measurements

  2018cites this paper
• Leveraging subspace information for low-rank matrix reconstruction

  2018cites this paper
• Array Shape Calibration Using Low Rank Projections

  2018cites this paper
• Distributed and Robust Statistical Learning

  2018cites this paper
• Sparse and Low-Rank Tensor Estimation via Cubic Sketchings

  2018cites this paper
• Recovery of simultaneous low rank and two-way sparse coefficient matrices, a nonconvex approach

  2018cites this paper