The Stability of Low-Rank Matrix Reconstruction: A Constrained Singular Value View

DOI10.1109/TIT.2012.2204535MaRDI QIDQ2989801zbMATH OpenFDO

Authors Gongguo Tang, Arye Nehorai

Publication date 8 June 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.4088

Mathematics Subject Classification ID

Matrix completion problems (15A83) Applications of mathematical programming (90C90) Sampling theory in information and communication theory (94A20)

Abstract: The stability of low-rank matrix reconstruction with respect to noise is investigated in this paper. The $el{l}_{\ast }$-constrained minimal singular value ($el{l}_{\ast }$-CMSV) of the measurement operator is shown to determine the recovery performance of nuclear norm minimization based algorithms. Compared with the stability results using the matrix restricted isometry constant, the performance bounds established using $el{l}_{\ast }$-CMSV are more concise, and their derivations are less complex. Isotropic and subgaussian measurement operators are shown to have $el{l}_{\ast }$-CMSVs bounded away from zero with high probability, as long as the number of measurements is relatively large. The $el{l}_{\ast }$-CMSV for correlated Gaussian operators are also analyzed and used to illustrate the advantage of $el{l}_{\ast }$-CMSV compared with the matrix restricted isometry constant. We also provide a fixed point characterization of $el{l}_{\ast }$-CMSV that is potentially useful for its computation.

Cited in

(4)

• A study of the gap between the structured singular value and its convex upper bound for low-rank matrices
• Low-rank matrix recovery problem minimizing a new ratio of two norms approximating the rank function then using an ADMM-type solver with applications
• A bootstrap method for spectral statistics in high-dimensional elliptical models
• Stability of low-rank matrix recovery and its connections to Banach space geometry

This page was built for publication: The Stability of Low-Rank Matrix Reconstruction: A Constrained Singular Value View

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2989801)