Robust width: A characterization of uniformly stable and robust compressed sensing

Dustin just sent me the following:

Igor, 

Jameson Cahill and I just wrote a paper that you might like:
http://arxiv.org/abs/1408.4409
Keep up the great blog! 

Cheers,
Dustin

Thanks Dustin. Uh, a cheat sheet to follow when you want to figure out if your sensing matrix will do well for compressive sensing, I like that indeed. Here is the paper: Robust width: A characterization of uniformly stable and robust compressed sensing by Jameson Cahill, Dustin G. Mixon

Compressed sensing seeks to invert an underdetermined linear system by exploiting additional knowledge of the true solution. Over the last decade, several instances of compressed sensing have been studied for various applications, and for each instance, reconstruction guarantees are available provided the sensing operator satisfies certain sufficient conditions. In this paper, we completely characterize the sensing operators which allow uniformly stable and robust reconstruction by convex optimization for many of these instances. The characterized sensing operators satisfy a new property we call the robust width property, which simultaneously captures notions of widths from approximation theory and of restricted eigenvalues from statistical regression. We provide a geometric interpretation of this property, we discuss its relationship with the restricted isometry property, and we apply techniques from geometric functional analysis to find random matrices which satisfy the property with high probability.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.