Simple Bounds for Recovering Low-complexity Models

Details Simple Bounds for Recovering Low-complexity Models Simple Bounds for Recovering Low-complexity Models

2011-06-07

arxiv.org/abs/1106.1474v2

Computer Science

Information Theory

Scientific paper

This note presents a unified analysis of the recovery of simple objects from random linear measurements. When the linear functionals are Gaussian, we show that an s-sparse vector in R^n can be efficiently recovered from 2s log n measurements with high probability and a rank r, n by n matrix can be efficiently recovered from r(6n-5r) with high probability. For sparse vectors, this is within an additive factor of the best known nonasymptotic bounds. For low-rank matrices, this matches the best known bounds. We present a parallel analysis for block sparse vectors obtaining similarly tight bounds. In the case of sparse and block sparse signals, we additionally demonstrate that our bounds are only slightly weakened when the measurement map is a random sign matrix. Our results are based on analyzing a particular dual point which certifies optimality conditions of the respective convex programming problem. Our calculations rely only on standard large deviation inequalities and our analysis is self-contained.

Affiliated with

Also associated with

No associations

Rating

Simple Bounds for Recovering Low-complexity Models 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 Simple Bounds for Recovering Low-complexity Models, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple Bounds for Recovering Low-complexity Models will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-319794