The connection between compressed sensing and sparse representation

Question

If I understand correctly, Compressed Sensing as an application of Sparse Representation is defined as:

To find linear compression schemes for huge input signals that are known to have a sparse representation, so that the input signal can be recovered efficiently from the compression (the "sketch").(ref: this question)

So based on my understanding, compressed sensing is like a precoding before analog to digital data conversion.
And my take on sparse representation is:
A signal can be represented as a linear combination of basis functions where the set of basis functions is called dictionary and data samples are much more than their features. Mathematically, in the system of linear equations $Y=DX$ where $Y \in \mathbb{R}^{n \times N} (n \ll N)$ we seek a dictionary that results in sparse representation of $Y$.

So as far as I've understood, the output of sparse representation is used in compressed sensing. In my thesis on dictionary learning, after an introduction about compressed sensing, I'd like to talk a bit about the connection between compressed sensing and sparse representation before getting into the details of sparse representation. What I fail to do is to explain the connection between the two even though I am aware of the concepts. I'd like to have a good understanding of the connection between compressed sensing and sparse representation. Any explanation would be greatly appreciated!

Answer 1

Consider a real world 'signal' - a discrete set of numbers representing something real (e.g. an image, an audio recording, etc.). These numbers form a vector in some vector space. Any such vector can be transformed into many different bases. The vector will be more 'sparse' in some of those bases than others. In fact, there's even a set of bases where the signal is 100% sparse - i.e. a basis set which includes that particular vector as one of it's components. The representation of the vector in a basis in which it is very sparse is a 'sparse representation' of that vector. Unless there is some deliberate connection between the two, the common sense assumption is that in any randomly chosen basis, a given vector will most likely have a very not sparse representation. However, it turns out that in the real world, useful signals are often time very sparse in certain domains. This information can be used.

Compressed sensing seeks to reconstruct a signal with more information than given directly by the measurements (e.g. in imaging, a higher resolution than the number of pixels actually measured, etc.). This is mathematically impossible... unless you have some additional information about the signal aside from the measurements, such as knowing it will likely be sparse in some known domain (e.g. images tend to have a sparse representation in the Fourier domain). So, you measure the signal in some domain (not the sparse one), then you fill in the missing values with guesses to form a a bigger dataset, transform to the sparse domain, and measure the sparsity there. You then adjust your guesses and check again, and so on until you find a set of guess values that minimize sparsity in the alternate domain. You now have a more complete vector.

So the connection is: compressed sensing uses the fact that the signal has a sparse representation in some known basis