Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions

Details Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions

2011-04-06

arxiv.org/abs/1104.1041v2

Computer Science

Information Theory

26 pages

Scientific paper

We improve existing results in the field of compressed sensing and matrix completion when sampled data may be grossly corrupted. We introduce three new theorems. 1) In compressed sensing, we show that if the m \times n sensing matrix has independent Gaussian entries, then one can recover a sparse signal x exactly by tractable \ell1 minimimization even if a positive fraction of the measurements are arbitrarily corrupted, provided the number of nonzero entries in x is O(m/(log(n/m) + 1)). 2) In the very general sensing model introduced in "A probabilistic and RIPless theory of compressed sensing" by Candes and Plan, and assuming a positive fraction of corrupted measurements, exact recovery still holds if the signal now has O(m/(log^2 n)) nonzero entries. 3) Finally, we prove that one can recover an n \times n low-rank matrix from m corrupted sampled entries by tractable optimization provided the rank is on the order of O(m/(n log^2 n)); again, this holds when there is a positive fraction of corrupted samples.

Affiliated with

Also associated with

No associations

Rating

Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed Sensing and Matrix Completion with Constant Proportion of Corruptions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-417795