Journal
IEEE TRANSACTIONS ON SIGNAL PROCESSING
Volume 61, Issue 13, Pages 3279-3290Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TSP.2013.2259164
Keywords
Affine rank minimization; compressed sensing; Dantzig selector; constrained l(1) minimization; low-rank matrix recovery; constrained nuclear norm minimization; restricted isometry; sparse signal recovery
Categories
Funding
- NSF FRG Grant [DMS-0854973]
- NIH Grant [R01 CA127334]
- Direct For Mathematical & Physical Scien
- Division Of Mathematical Sciences [1208982] Funding Source: National Science Foundation
Ask authors/readers for more resources
This paper establishes new restricted isometry conditions for compressed sensing and affine rank minimization. It is shown for compressed sensing that delta(A)(k) + theta(A)(k,k) < 1 guarantees the exact recovery of all k sparse signals in the noiseless case through the constrained l(1) minimization. Furthermore, the upper bound 1 is sharp in the sense that for any epsilon > 0, the condition delta(A)(k) + theta(A)(k,k) < 1 + epsilon is not sufficient to guarantee such exact recovery using any recovery method. Similarly, for affine rank minimization, if delta(M)(r) + theta(M)(r,r) < 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 epsilon > 0, delta(M)(r) + theta(M)(r,r) < 1 + epsilon does not ensure such exact recovery using any method. Moreover, in the noisy case the conditions and delta(A)(k) + theta(A)(k,k) < 1 and delta(M)(r) + theta(M)(r,r) < 1 are also sufficient for the stable recovery of sparse signals and low-rank matrices respectively. Applications and extensions are also discussed.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available