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

Yuanxin Li, Yue Sun, Yuejie Chi

TL;DR

This paper tackles the challenge of recovering a low-rank positive semidefinite (PSD) matrix from noisy and potentially outlier-corrupted rank-one measurements. They introduce a parameter-free convex optimization method that guarantees exact recovery under mild conditions and a computationally efficient non-convex approach for cases where the rank is known.

What Problem Does This Paper Address?

In many scientific and engineering fields, we need to estimate a matrix that has a low-rank structure and is positive semidefinite (PSD). This arises in areas like phase retrieval, covariance sketching, and quantum state tomography. The measurements we get are often "rank-one," meaning they are formed by taking a quadratic form with a sensing vector. The core problem is that these measurements can be corrupted by outliers – data points that are wildly different from the true signal – or by bounded noise. Traditional methods for low-rank matrix recovery often struggle with these corruptions, either failing completely or requiring careful parameter tuning. This paper aims to develop robust and efficient methods that can handle these corrupted measurements, even without knowing the exact nature or location of the outliers.

Methods

The paper proposes two main approaches:

  • Parameter-Free Convex Relaxation (Robust-PhaseLift): This method formulates the problem as a convex optimization task. Instead of directly minimizing the rank (which is hard), it minimizes the L1-norm of the measurement residual. This L1-norm is key to handling outliers, as it penalizes large errors less severely than L2-norms, effectively making the algorithm robust to sparse, large errors. A significant advantage is that this method is "parameter-free," meaning it doesn't require any prior knowledge of the noise bound, outlier sparsity, or even the rank of the matrix. The authors provide theoretical guarantees that this method can recover the true low-rank PSD matrix with high probability, even when a fraction of measurements are corrupted.
  • Non-Convex Subgradient Descent: When the rank of the PSD matrix is known (or an upper bound is available), a more computationally efficient approach is possible. This method leverages the fact that any rank-r PSD matrix can be decomposed as $X = U U^T$. Instead of recovering $X$ directly, it focuses on recovering $U$. The algorithm uses a subgradient descent method to minimize a non-smooth objective function derived from the L1-norm of the residual. This approach is shown to have excellent empirical performance and lower computational complexity compared to the convex method, especially for large-scale problems.

Datasets

Not discussed in the paper. The paper focuses on theoretical guarantees and numerical simulations using synthetic data generated according to the problem formulation.

Key Insights and Ideas

  • L1-norm for Outlier Robustness: The paper highlights the power of using the L1-norm of the residual in a convex optimization framework for robustly recovering low-rank matrices from corrupted measurements. This is a standard technique for robust statistics, but its application here with rank-one measurements and PSD constraints is a key contribution.
  • Parameter-Free Recovery: The development of a convex algorithm that doesn't require tuning parameters like noise bounds or sparsity levels is a significant practical advantage. This simplifies implementation and makes the method more broadly applicable.
  • Rank-One Measurements and PSD Constraint: The specific structure of rank-one measurements ($a_i a_i^T$) combined with the PSD constraint ($X \succeq 0$) allows for a simpler convex formulation than general low-rank matrix recovery problems, where trace minimization is often needed.
  • Non-Convex for Efficiency: The paper demonstrates that when the rank is known, a non-convex approach can achieve comparable or even better empirical performance with significantly reduced computational cost. This is crucial for handling large-scale applications.
  • Theoretical Guarantees: The paper provides theoretical guarantees for the convex method, showing that exact recovery is possible with a number of measurements that scales roughly as $nr^2$, even with a fraction of outliers. This provides a solid foundation for the practical performance observed.

Key Results

  • Convex Algorithm (Robust-PhaseLift): Theoretical guarantees show that with $m \gtrsim nr^2$ measurements, the algorithm can recover a rank-r PSD matrix with high probability, even when a fraction of measurements are corrupted by arbitrary outliers. The recovery is also stable against bounded noise.
  • Non-Convex Algorithm (Subgradient Descent): Empirical results show that this algorithm performs comparably to the convex method in terms of success rate, even in the presence of outliers, but with much lower computational cost.
  • Numerical Simulations: Extensive simulations demonstrate the effectiveness of both algorithms across various scenarios, including different numbers of measurements, ranks, and outlier percentages. The figures illustrate phase transitions showing the conditions under which recovery is successful.
  • Toeplitz Structure Advantage: For Toeplitz PSD matrices, the required number of measurements for successful recovery is shown to be sublinear in $n$, highlighting the benefit of exploiting additional structural information.

Limitations and Future Work

  • Non-Convex Algorithm Theoretical Justification: The authors acknowledge that while the non-convex subgradient descent algorithm shows excellent empirical performance, theoretical guarantees for its robustness and convergence are still needed. This is identified as a direction for future work.
  • Outlier Fraction Dependence: While the convex method handles outliers, the theoretical guarantees depend on the fraction of outliers being below a certain threshold related to the rank.
  • Parameter-Free vs. Rank-Known: The paper presents two distinct algorithms for different scenarios (rank unknown vs. rank known). Future work could explore unifying these or developing adaptive methods.
  • Extension of Median-Truncated Gradient Descent: The authors mention recent work on median-truncated gradient descent for phase retrieval with outliers and suggest that this approach could potentially be extended to the robust low-rank PSD matrix recovery problem.

Summary updated

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.
BibTeX
@article{li2017low,
  author = {Yuanxin Li and Yue Sun and Yuejie Chi},
  title = {{Low-Rank Positive Semidefinite Matrix Recovery From Corrupted Rank-One Measurements}},
  journal = {IEEE Trans. Signal Process.},
  year = {2017},
  url = {https://openreview.net/forum?id=zTqnQOe9qsC},
}
Figure