Compressed sensing started with the promise that it "directly acquires the important information from the signals/images-in effect not acquiring data that would eventually be thrown away by lossy compression" (Donoho 2006). However, the premise of compressed sensing has been limited to simple structures, such as sparsity and low-rankness, and many important questions have remained unanswered. For instance, it is not known whether or under what conditions the existence of lossy compression algorithms for a class of signals/images necessarily leads to a compressed sensing algorithm that can recover data from an undersampled set of linear measurements (as promised in the initial compressed sensing papers). Furthermore, the amount of improvement gained through the use of compression schemes that employ more complicated structures than sparsity or low-rankness is unknown.
In this talk, I will address these problems. In particular, after defining the rate-distortion (RD) performance of a family of compression algorithms, I will explain the connection between the RD of a coder and the success of the compressed sensing algorithms that are based on those compression methods. Finally, I will discuss the connections between our results and the relevant concepts in algorithmic complexity theory and embedology.
This is based on a joint work with Shirin Jalali from New York University.