Compressed Sensing and Affine Rank Minimization under Restricted Isometry
Tony Cai and Anru Zhang
-
Abstract:
This paper establish new restricted isometry conditions for compressed sensing and affine rank minimization. It is shown for compressed sensing that δAk + θAk,k < 1 guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained l1 minimization. Furthermore, the upper bound 1 is sharp in the sense that for any ε > 0, the condition δAk + θAk,k < 1+ ε is not sufficient to guarantee such exact recovery using any recovery method. Similarly, for affine rank minimization, if δAk + θAk,k < 1 then all matrices with rank at most r can be reconstructed exactly in the noiseless case via the constrained nuclear norm minimization; and for any ε > 0, δAk + θAk,k < 1 + ε does not ensure such exact recovery using any method. Moreover, in the noisy case the conditions δAk + θAk,k < 1 and δAk + θAk,k < 1 are also sufficient for the stable recovery of sparse signals and low-rank matrices respectively. Applications and extensions are also discussed.
- Paper:
pdf file.
- Other related papers:
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.