Matrix Recovery from Rank-One Projection Measurements via Nonconvex Minimization

Peng Li, Wengu Chen

Abstract

In this paper, we consider the matrix recovery from rank-one projection measurements proposed in [Cai and Zhang, Ann. Statist., 43(2015), 102-138], via nonconvex minimization. We establish a sufficient identifiability condition, which can guarantee the exact recovery of low-rank matrix via Schatten-$p$ minimization $\min_{X}\|X\|_{S_p}^p$ for $0 < p \le 1$ and least $q$ minimization $\min_{X}\|\mathcal{A}(X)-b\|_q^q$ for $0 < q \le 1$. Furthermore, the stable recovery is also investigated in the presence of noise. Specifically, we show that for the Gaussian rank-one projection measurements, the Schatten-$p$ minimization and least $q$ minimization can achieve the exact and stable recovery with high probability with the optimal number of measurements $L \ge Cr(m+n)$.

Introduction

Low-rank matrix recovery (LRMR) is a fundamental challenge in modern data science, with applications spanning quantum state tomography, system identification, and phase retrieval. The objective is to reconstruct an unknown low-rank matrix $X \in \mathbb{R}^{m \times n}$ from a limited set of linear measurements $b = \mathcal{A}(X) + e$, where $e$ represents noise.

While much of the existing literature focuses on general linear maps using the Restricted Isometry Property (RIP), this paper investigates the specific case of Rank-One Projections (ROP). In the ROP model, measurements are obtained by projecting the target matrix onto rank-one matrices, such that $b_j = \text{trace}(A_j^T X)$ where each $A_j$ is a rank-one matrix. Standard RIP-based analysis often yields suboptimal results for ROP. Furthermore, while convex nuclear norm minimization is the standard tool for recovery, nonconvex methods—such as Schatten-$p$ minimization—often demonstrate superior performance in practice. This paper provides the rigorous theoretical guarantees previously lacking for these nonconvex approaches in the ROP setting.

Nonconvex Minimization Framework

The authors analyze two primary nonconvex optimization strategies to address the recovery problem:

  1. Schatten-$p$ Minimization ($0 < p \le 1$): This approach involves minimizing the sum of the singular values raised to the power of $p$. As $p$ decreases toward zero, the objective function becomes a tighter proxy for the rank of the matrix than the convex nuclear norm ($p=1$).
  2. Least $q$ Minimization ($0 < q \le 1$): This method minimizes the $\ell_q$ norm of the residual, $\|\mathcal{A}(X) - b\|_q^q$. A significant advantage of least $q$ minimization is that it does not require an a priori estimate of the noise level $\eta$, making it highly practical for real-world applications where noise characteristics may be unknown.

To handle cases where the sampling operator has a non-zero mean—which can introduce bias into the recovery—the authors utilize a "debiasing" technique for the measurement matrices. This ensures the theoretical framework remains robust across different measurement distributions.

The $\ell_q$-Restricted Uniform Boundedness Condition

The core theoretical innovation of this work is the introduction of the $\ell_q$-Restricted Uniform Boundedness ($\ell_q$-RUB) condition. This condition is a generalization of the Restricted Uniform Boundedness (RUB) condition originally introduced by Cai and Zhang (2015).

The $\ell_q$-RUB condition ensures that the "energy" of a rank-$r$ matrix is preserved through the measurement process in a manner compatible with $\ell_q$ analysis. Crucially, the authors demonstrate that the $\ell_q$-RUB condition implies the robust rank null space property. By establishing this connection, the paper integrates ROP recovery into the well-established theoretical pillars of compressed sensing.

Theoretical Results and Sample Complexity

The paper provides several key theorems regarding the performance of these nonconvex methods:

  • Exact Recovery: Theorem 2.6 establishes that under specific $\ell_q$-RUB constants, Schatten-$p$ minimization perfectly recovers all rank-$r$ matrices in the noiseless setting.
  • Stable Recovery: Theorem 2.11 provides explicit error bounds for noisy environments. It demonstrates that the recovery error is proportional to the noise level and the approximation error of the best rank-$r$ representation of the matrix.
  • Gaussian Design Efficiency: For Gaussian ROP measurements, the authors prove that stable recovery is achievable with high probability when the number of measurements $L$ scales linearly with the matrix's degrees of freedom: $L \ge Cr(m+n)$. This matches the theoretical minimum required to describe a rank-$r$ matrix.
  • Least Absolute Deviation (LAD): The analysis highlights that for Gaussian ROP, using Least Absolute Deviation (least $q$ with $q=1$) is particularly effective, providing a robust alternative to least squares when the noise distribution is heavy-tailed or unknown.

Conclusion and Future Work

By establishing the $\ell_q$-RUB condition, the authors provide a theoretical "green light" for the use of nonconvex methods in ROP settings. These methods are shown to be both stable and efficient, often requiring fewer measurements than convex alternatives to achieve the same level of accuracy.

Future research directions include refining the tightness of the conditions for the $q=1$ case, as the current $(k+1)r$ order condition may be slightly more restrictive than the $kr$ order found in some convex studies. Additionally, while Gaussian distributions are well-characterized here, identifying other specific distributions that satisfy $\ell_q$-RUB for $0 < q < 1$ remains an open challenge. Finally, while this paper focuses on the existence and stability of global minimizers, further study is needed regarding the convergence properties of specific local search algorithms used to solve these nonconvex problems.

Summary updated

Abstract

In this paper, we consider the matrix recovery from rank-one projection measurements proposed in [Cai and Zhang, Ann. Statist., 43(2015), 102-138], via nonconvex minimization. We establish a sufficient identifiability condition, which can guarantee the exact recovery of low-rank matrix via Schatten-$p$ minimization $\min_{X}\|X\|_{S_p}^p$ for $0
BibTeX
@misc{li2018matrix,
  author = {Peng Li and Wengu Chen},
  title = {{Matrix Recovery from Rank-One Projection Measurements via Nonconvex Minimization}},
  year = {2018},
  eprint = {1806.10803},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1806.10803},
}
Figure