Stable low-rank matrix recovery from 3-designs

2025/12/12 by Gilles, Timm
Engineering · Mathematics · Physics and Astronomy · #60B20 #90C25 #94A12 #94A20 #Advanced X-ray Imaging Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Mathematical Approximation and Integration #Sparse and Compressive Sensing Techniques

paper · doi:10.48550/arxiv.2512.11642

openalex publication_date 2025/12/12 · openalex created_date 2025/12/16 · openalex updated_date 2026/07/28

Abstract

We study the recovery of low-rank Hermitian matrices from rank-one measurements obtained by uniform sampling from complex projective 3-designs, using nuclear-norm minimization. This framework includes phase retrieval as a special case via the PhaseLift method. In general, complex projective t-designs provide a practical means of partially derandomizing Gaussian measurement models. While near-optimal recovery guarantees are known for 4-designs, and it is known that 2-designs do not permit recovery with a subquadratic number of measurements, the case of 3-designs has remained open. In this work, we close this gap by establishing recovery guarantees for (exact and approximate) 3-designs that parallel the best-known results for 4-designs. In particular, we derive bounds on the number of measurements sufficient for stable and robust low-rank recovery via nuclear-norm minimization. Our results are especially relevant in practice, as explicit constructions of 4-designs are significantly more challenging than those of 3-designs.

Citations

• Low rank matrix recovery from Clifford orbits
• Stable low-rank matrix recovery via null space properties
• Low rank matrix recovery from rank one measurements
• Convex recovery of a structured signal from independent random linear measurements
• Learning without Concentration
• Bounding the smallest singular value of a random matrix without\n concentration
• Solving Quadratic Equations via PhaseLift when There Are About As Many Equations As Unknowns
• Exact Matrix Completion via Convex Optimization
• Quantum t-designs: t-wise independence in the quantum world

Related

• Low rank matrix recovery from rank one measurements
• Stable low-rank matrix recovery via null space properties
• The minimal measurement number for low-rank matrices recovery
• On the robustness of noise-blind low-rank recovery from rank-one measurements
• Low-rank matrix recovery via regularized nuclear norm minimization