Jameson Cahill and I recently posted a new paper on the arXiv that we’re pretty excited about. Suppose you want to do compressed sensing with L1 minimization. That is, you get for some nearly -sparse vector and some noise satisfying , and then you attempt to reconstruct by taking

One of the main results of compressed sensing is that the optimizer of the above program satisfies

provided satisfies the -restricted isometry property (RIP) for some . Here, denotes the best -term approximation of , and so captures how close is to being -sparse. Jameson and I wondered if RIP was necessary to enjoy this uniformly stable and robust performance (uniform in the sense that the fixed matrix works for all simultaneously, stable because we don’t require to be exactly -sparse, and robust because we allow noise). In our paper, we completely characterize the matrices that offer this performance, and we show that RIP matrices form a strict subset.