Low-Rank Matrix Recovery via Heavy-Tailed Quadratic Sampling
2026-07-09 • Information Theory
Information Theory
AI summaryⓘ
The authors study how to recover a low-rank Hermitian matrix from special measurements formed by sampling vectors, important in areas like phase retrieval. Unlike earlier work that assumed these vectors are Gaussian or close to Gaussian, they analyze situations where the vectors have heavier-tailed distributions with only mild moment conditions. They prove that two common recovery methods still work reliably under these weaker assumptions, with an optimal number of measurements. Their approach uses advanced mathematical tools dealing with heavy-tailed data and leads to improved results in related measurement models.
Low-rank matrix recoveryHermitian matrixPhase retrievalHeavy-tailed distributionsNuclear norm minimizationSemidefinite programmingMoment conditionsQuadratic formsCovariance estimationComplex projective design
Authors
Gao Huang, Song Li
Abstract
The problem of recovering an (approximately) low-rank Hermitian matrix $\pmb{M}_0 \in \mathbb{C}^{n \times n}$ of rank $r$ from quadratic sampling matrices of the form $\{\pmb{a}_k \pmb{a}_k^*\}_{k=1}^m$ arises in a variety of applications, including phase retrieval. To obtain rigorous recovery guarantees, the sampling vectors $\{\pmb{a}_k\}_{k=1}^m$ are typically modeled probabilistically. However, most existing theoretical results rely on Gaussian or sub-Gaussian assumptions, which may not accurately capture practical data models. In many applications, sampling vectors exhibit heavier tails, while theoretical understanding in such regimes remains scarce. In this paper, we bridge this gap. We show that two widely used convex approaches, nuclear norm minimization and semidefinite-constrained empirical risk minimization, achieve uniform, stable, and robust recovery under the mild assumption that the entries of the sampling vectors have only finite $4+δ$ moments, with the optimal sample complexity $m = \mathcal{O}(rn)$ up to moment-dependent constants. The two main ingredients of our analysis are moment estimates for quadratic forms established via decoupling, together with recent advances in covariance estimation in heavy-tailed settings. As byproducts, we also establish the optimal sample complexity for low-rank matrix recovery under complex projective $4$-design sampling, thereby improving upon previous results, and obtain stability guarantees for phase retrieval under similarly weak moment assumptions.