Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-rank Matrices

2013/06/05 by T. Tony Cai, Tommaso Cai, Anru R. Zhang +3 · 2 citations
Computer Science · Engineering · Mathematics · Medicine · #Advanced MRI Techniques and Applications #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (stat.ML) #Microwave Imaging and Scattering Analysis #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #cs.IT #math.IT #math.ST #stat.ML #stat.TH

paper · pdf · doi:10.48550/arxiv.1306.1154

to appear in IEEE Transactions on Information Theory

openalex publication_date 2013/06/05 · arxiv created 2013/10/22 · arxiv updated 2013/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper considers compressed sensing and affine rank minimization in both noiseless and noisy cases and establishes sharp restricted isometry conditions for sparse signal and low-rank matrix recovery. The analysis relies on a key technical tool which represents points in a polytope by convex combinations of sparse vectors. The technique is elementary while leads to sharp results. It is shown that for any given constant t≥ 4/3, in compressed sensing δ_tk^A < √((t-1)/t) guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained ℓ₁ minimization, and similarly in affine rank minimization δ_tr^M< √((t-1)/t) ensures the exact reconstruction of all matrices with rank at most r in the noiseless case via the constrained nuclear norm minimization. Moreover, for any ε>0, δ_tk^A<√((t-1)/(t))+ε is not sufficient to guarantee the exact recovery of all k-sparse signals for large k. Similar result also holds for matrix recovery. In addition, the conditions δ_tk^A < √((t-1)/t) and δ_tr^M< √((t-1)/t) are also shown to be sufficient respectively for stable recovery of approximately sparse signals and low-rank matrices in the noisy case.

Citations

• New bounds on the restricted isometry constant δ2k
• Sharp RIP bound for sparse signal and low-rank matrix recovery
• Compressed Sensing MRI
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Stable signal recovery from incomplete and inaccurate measurements
• On the Theorem of Uniform Recovery of Random Sampling Matrices

Cited by

• On the Performance of Amplitude-Based Models for Low-Rank Matrix Recovery
• Stable recovery of complex dictionary-sparse signals from phaseless measurements
• On the ℓ₁-Norm Invariant Convex k-Sparse Decomposition of Signals

Related

• Sharp RIP Bound for Sparse Signal and Low-Rank Matrix Recovery
• Near Optimal Compressed Sensing of a Class of Sparse Low-Rank Matrices via Sparse Power Factorization
• Compressed Sensing of Simultaneous Low-Rank and Joint-Sparse Matrices
• Soft Recovery Through ℓ_1,2 Minimization with Applications in Recovery of Simultaneously Sparse and Low-Rank Matrice
• Compressed sensing of low-rank plus sparse matrices