Beyond sparsity: Universally stable compressed sensing when the number of ‘free’ values is less than the number of observations

Recent results in compressed sensing have shown that a wide variety of structured signals can be recovered from undersampled and noisy linear observations. In this paper, we show that many of these signal structures can be modeled using an union of affine subspaces, and that the fundamental number of observations needed for stable recovery is given by the number of “free” values, i.e. the dimension of the largest subspace in the union. One surprising consequence of our results is that the fundamental phase transition for random discrete-continuous signal models can be attained by a universal estimator that does not depend on the distribution.