Low-rank matrix recovery landscapes beyond RIP with application to rank-one measurements
Abstract
We study the problem of low-rank matrix recovery from linear measurements via the global nonconvex landscape of a low-rank factored formulation of the matrix LASSO (nuclear-norm--regularized least-squares). If the landscape is benign, that is, has no bad local optima, then practical and scalable algorithms can compute good statistical estimates. Previous state-of-the-art landscape guarantees have typically assumed that the linear measurement operator has the restricted isometry property, that is, the operator is approximately an isometry over all low-rank matrices. This is an unrealistic assumption for many applications; in particular, when the individual measurement matrices are themselves low-rank, we typically have poor upper isometry constants. To overcome this, we establish new guarantees of a benign landscape under a weaker isometry condition: rather than requiring upper isometry over all low-rank matrices, we only require it over the linear low-rank tangent space to the low-rank ground truth matrix. To illustrate the utility of this result, we apply it to the problem of matrix recovery from random rank-one linear measurements; via high-probability concentration bounds on the random measurement operator, we prove a novel landscape guarantee with statistically near-optimal sample complexity and recovery error.
Related
- Stable Recovery and Benign Overparameterized Landscapes for Phase Retrieval from Coded Diffraction Patterns
- Simultaneous recovery of multiple parameters in nonlocal diffusion equations from internal measurements
- A Stress-Based Estimator for Pressure and Stress Recovery from Velocity Measurements
- Learned Score-Based Turbo Message Passing for Channel Recovery From Spatially Compressed Measurements
- Efficient Support Recovery of Mixtures of Sparse Linear Classifiers with Fewer Measurements
BibTeX
@misc{mcrae2026lowrank,
title = {{Low-rank matrix recovery landscapes beyond RIP with application to rank-one measurements}},
author = {Andrew D Mcrae},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.06146},
eprint = {2609.06146},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05740523v1},
}
RIS
TY - UNPB
TI - Low-rank matrix recovery landscapes beyond RIP with application to rank-one measurements
AU - Andrew D Mcrae
PY - 2026
DA - 2026/09/05
PB - HAL
DO - 10.48550/arxiv.2609.06146
UR - https://hal.science/hal-05740523v1
AB - We study the problem of low-rank matrix recovery from linear measurements via the global nonconvex landscape of a low-rank factored formulation of the matrix LASSO (nuclear-norm--regularized least-squares). If the landscape is benign, that is, has no bad local optima, then practical and scalable algorithms can compute good statistical estimates. Previous state-of-the-art landscape guarantees have typically assumed that the linear measurement operator has the restricted isometry property, that is, the operator is approximately an isometry over all low-rank matrices. This is an unrealistic assumption for many applications; in particular, when the individual measurement matrices are themselves low-rank, we typically have poor upper isometry constants. To overcome this, we establish new guarantees of a benign landscape under a weaker isometry condition: rather than requiring upper isometry over all low-rank matrices, we only require it over the linear low-rank tangent space to the low-rank ground truth matrix. To illustrate the utility of this result, we apply it to the problem of matrix recovery from random rank-one linear measurements; via high-probability concentration bounds on the random measurement operator, we prove a novel landscape guarantee with statistically near-optimal sample complexity and recovery error.
ER -