Low-Rank Positive Semidefinite Matrix Recovery from Corrupted Rank-One Measurements

Abstract

We study the problem of estimating a low-rank positive semidefinite (PSD) matrix from a set of rank-one measurements using sensing vectors composed of i.i.d. standard Gaussian entries, which are possibly corrupted by arbitrary outliers. This problem arises from applications such as phase retrieval, covariance sketching, quantum space tomography, and power spectrum estimation. We first propose a convex optimization algorithm that seeks the PSD matrix with the minimum ${\ell }_1$-norm of the observation residual. The advantage of our algorithm is that it is free of parameters, therefore eliminating the need for tuning parameters and allowing easy implementations. We establish that with high probability, a low-rank PSD matrix can be exactly recovered as soon as the number of measurements is large enough, even when a fraction of the measurements are corrupted by outliers with arbitrary magnitudes. Moreover, the recovery is also stable against bounded noise. With the additional information of an upper bound of the rank of the PSD matrix, we propose another non-convex algorithm based on subgradient descent that demonstrates excellent empirical performance in terms of computational efficiency and accuracy.

arXiv comment12 pages, 7 figures

References in corpus (11)

• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Quantum state tomography via compressed sensing
• Phase Retrieval via Wirtinger Flow: Theory and Algorithms
• Rank-Sparsity Incoherence for Matrix Decomposition
• Compressive Phase Retrieval via Generalized Approximate Message Passing
• Robust PCA as Bilinear Decomposition with Outlier-Sparsity Regularization
• A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices
• Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion
• Compression Limits for Random Vectors with Linearly Parameterized Second-Order Statistics
• A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements
• The local convexity of solving systems of quadratic equations

Cited by in corpus (16)

• Global Optimality in Low-rank Matrix Optimization
• The Non-convex Geometry of Low-rank Matrix Optimization
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Universality in Learning from Linear Measurements
• Robust Recovery via Implicit Bias of Discrepant Learning Rates for Double Over-parameterization
• Unrolling SVT to obtain computationally efficient SVT for n-qubit quantum state tomography
• Quantized Corrupted Sensing with Random Dithering
• Nonconvex Robust Low-rank Matrix Recovery
• Nonconvex Low-Rank Matrix Recovery with Arbitrary Outliers via Median-Truncated Gradient Descent
• Solving Systems of Quadratic Equations via Exponential-type Gradient Descent Algorithm
• Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recovery
• About some works of Boris Polyak on convergence of gradient methods and their development
• Low solution rank of the matrix LASSO under RIP with consequences for rank-constrained algorithms
• Matrix Recovery from Rank-One Projection Measurements via Nonconvex Minimization
• Deep learned SVT: Unrolling singular value thresholding to obtain better MSE
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets