Sparse Representation of a Polytope and Recovery of Sparse Signals and Low-Rank Matrices
Tony Cai and Anru Zhang
It is shown that for any given constant t ≥ 4/3, in compressed sensing δAtk < √ (t-1)/t guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained l1 minimization, and similarly in affine rank minimization δMtk < √ (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, δAtk < √ (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 δAtk < √ (t-1)/t and δMtr < √ (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.
Cai, T. & Zhang, A. (2013).
Compressed sensing and affine rank minimization under restricted isometry.
IEEE Transactions on Signal Processing 61, 3279-3290.
Cai, T. & Zhang, A. (2013).
Sharp RIP bound for sparse signal and low-rank matrix recovery.
Applied and Computational Harmonic Analysis 35, 74-93.
Cai, T., Wang, L. & Xu, G. (2010).
New Bounds for Restricted Isometry Constants.
IEEE Transactions on Information Theory 56, 4388-4394.
Cai, T., Wang, L. & Xu, G. (2010).
Stable recovery of sparse signals and an oracle inequality.
IEEE Transactions on Information Theory 56, 3516-3522.
Cai, T., Wang, L. & Xu, G. (2010).
Shifting inequality and recovery of sparse signals.
IEEE Transactions on Signal Processing 58, 1300-1308.
Cai, T., Xu, G. & Zhang, J. (2009).
On recovery of sparse signals via l1 minimization.
IEEE Transactions on Information Theory 55, 3388-3397.