<p>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.</p>

<p>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... <em>unless</em> 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 (<em>not</em> 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.</p>

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

CC BY-SA 4.0
2019-02-01T00:07:37.613Z
2019-02-01T02:26:48.700Z
2019-02-01T02:26:48.700Z
argentum2f
<p>If I understand correctly, <code>Compressed Sensing</code> as an application of <code>Sparse Representation</code> is defined as:</p>

<blockquote>
  <p>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: <a href="https://cstheory.stackexchange.com/questions/399/analogs-of-compressed-sensing">this
  question</a>)</p>
</blockquote>

<p>So based on my understanding, <strong>compressed sensing</strong> is like a precoding before analog to digital data conversion.<br>
And my take on <strong>sparse representation</strong> is:<br>
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 <code>sparse representation</code> of $Y$. </p>

<p>So as far as I've understood, the output of <code>sparse representation</code> is used in <code>compressed sensing</code>. 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!</p>

<sparse-matrix><compressed-sensing>
The connection between compressed sensing and sparse representation
Meysam
# The connection between compressed sensing and sparse representation

(Asked by: username_0 on 2016-09-06)

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](https://cstheory.stackexchange.com/questions/399/analogs-of-compressed-sensing))

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!

**Tags:** sparse-matrix, compressed-sensing


---

## 1 answers

### Answer by username_1 on 2019-02-01. Score: 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


---

