Low-Rank Matrix Recovery via Heavy-Tailed Quadratic Sampling

Jul 16, 2026

Upload by Ophelia

Recovery of an approximately low-rank Hermitian matrix M0 from quadratic measurements of the form ⟨a_k a_k*, M0⟩ arises in applications such as phase retrieval, where sampling vectors are often modeled to obtain guarantees. Existing theory typically assumes Gaussian or subGaussian behavior, leaving heavy-tailed regimes underexplored. This work establishes uniform, stable, and robust recovery for two convex methods under finite (4+δ)-moment assumptions, reaching sample complexity m = O(rn) up to moment-dependent factors via decoupling-based moment estimates and heavy-tailed covariance estimation.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages33

Reading Time1 h 23 min

Abstract

Introduction

Measurement model and convex recovery programs

Motivation and limitations of Gaussian/subGaussian assumptions

arXiv :2607 .08671v1 [math . ST] 9 Jul 2026 Low-Rank Matrix Recovery via Heavy-Tailed Quadratic Sampling ∗ Gao Huang†and Song Li‡ Abstract The problem of recovering an (approximately) low-rank Hermitian matrix M0 ∈ Cn ×n of rank r from quadratic sampling matrices of the form {aka∗k} arises in a variety of applications, including phase retrieval. To obtain rigorous recovery guarantees, the sampling vectors {ak} are typically modeled probabilistically. However, most existing theoretical results rely on Gaussian or subGaussian 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 = 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. Keywords: Low-Rank Matrix; Phase Retrieval; Heavy Tails; Covariance Estimation ∗ This work was supported by NSFC under grant number U21A20426 †School of Mathematical Science, Zhejiang University, Hangzhou 310027, P. R. China, E-mail address: [hgmath@zju.edu.cn](hgmath@zju.edu.cn) ‡School of Mathematical Science, Zhejiang University, Hangzhou 310027, P. R. China, E-mail address: [songli@zju.edu.cn](songli@zju.edu.cn) 1 Introduction The problem of recovering a low-rank matrix from a small number of linear measurements is a central topic in applied mathematics, statistics, electrical engineering, and computer science; see, e.g., [52, 14] . It arises in a variety of areas, including quantum tomography [25, 20, 39], signal processing [4], recommender systems [35], and linear system identification and control [43] . A prominent example is phase retrieval, which arises in a range of signal and imaging applications, including X-ray crystallography, astronomical imaging, and diffraction imaging [47, 55] . In phase retrieval, the apparent obstacle posed by nonlinear magnitude-only measurements can be overcome by lifting the problem to a matrix space, an idea first introduced by Balan et al. [7] . This viewpoint later inspired the PhaseLift approach of Cand`es et al. [10, 13], which recasts phase retrieval as a low-rank matrix recovery problem. Motivated by these applications and the close connection with phase retrieval, in this paper we study the recovery of an (approximately) low-rank Hermitian matrix M0 ∈ Hn from the quadratic (i.e., rank-one) sampling model yk = ⟨aka∗k , M0 ⟩ + ωk , k = 1 , . . . , m. (1) Here, Hn denotes the space of n × n complex Hermitian matrices, {ak } are the sampling vectors, y := {yk } denotes the measurement vector and ω := {ωk } denotes the measurement noise. When M0 = x0x∗0 is rank-one for some x0 ∈ Cn , (1) reduces to the intensity-only measurement model arising in phase retrieval [7, 10] . To describe the setup more precisely, let A : Hn → Rm denote the linear map A (M) = {⟨aka∗k , M⟩} . (2) Then (1) can be written compactly as y = A (M0 ) + ω . (3) A prominent approach for recovering the matrix M0 from (3) is nuclear norm minimization, formulated as the following convex program [13, 15, 9, 39, 30, 26, 23]: in ∥M∥∗ subject to ∥A (M) − y∥ℓq ≤ η, (4) where ∥M∥∗ denotes the nuclear norm of M ∈ Cn ×n , and η is a know

FAQs

What recovery problem does the paper study?

It studies recovering an approximately low-rank Hermitian matrix M0 from quadratic (rank-one) sampling measurements with possible noise.

Why do heavy-tailed sampling vectors matter?

The paper targets settings where practical sampling vectors have heavier tails than Gaussian/subGaussian models, while existing theoretical results do not cover such regimes well.

Which recovery methods are proved to work under finite (4+δ) moments?

The paper proves guarantees for nuclear norm minimization and for a semidefinite-constrained empirical risk minimization approach under a mild finite moment assumption on the sampling vectors.

Jul 16, 2026

Upload by Ophelia