Approximately low-rank recovery from noisy and local measurements by convex program

Kiryung Lee, Rakshith Srinivasa Sharma, Marius Junge, Justin Romberg

Research output: Contribution to journalArticlepeer-review


Low-rank matrix models have been universally useful for numerous applications, from classical system identification to more modern matrix completion in signal processing and statistics. The nuclear norm has been employed as a convex surrogate of the low-rankness since it induces a low-rank solution to inverse problems. While the nuclear norm for low rankness has an excellent analogy with the ℓ1 norm for sparsity through the singular value decomposition, other matrix norms also induce low-rankness. Particularly as one interprets a matrix as a linear operator between Banach spaces, various tensor product norms generalize the role of the nuclear norm. We provide a tensor-norm-constrained estimator for the recovery of approximately low-rank matrices from local measurements corrupted with noise. A tensor-norm regularizer is designed to adapt to the local structure. We derive statistical analysis of the estimator over matrix completion and decentralized sketching by applying Maurey’s empirical method to tensor products of Banach spaces. The estimator provides a near-optimal error bound in a minimax sense and admits a polynomial-time algorithm for these applications.

Original languageEnglish (US)
Article numberiaad013
JournalInformation and Inference
Issue number3
StatePublished - Sep 2023


  • lasso
  • low-rank matrices
  • regularized estimation
  • tensor product

ASJC Scopus subject areas

  • Analysis
  • Statistics and Probability
  • Numerical Analysis
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Approximately low-rank recovery from noisy and local measurements by convex program'. Together they form a unique fingerprint.

Cite this