Compressive Sensing vs. Sparse Coding

Question

There apparently are different terminologies used to refer to the same field called "compressive sensing" such as (see this wiki page): compressed sensing, compressive sampling, or sparse sampling. I wonder about "sparse sensing" though!

Nonetheless, and after some internet search, what people refer to as "sparse coding" seems to not refer to the "compressive sensing" field as the other terminologies I cited above.

Is there really a difference between compressive sensing and sparse coding?

What about dictionary learning?

Answer 1

A couple of reference works offer an exaplanation:

• A neurological interpretation described in Scholarpedia
• Stanford's Unsupervised Feature Learning and Deep Learning tutorial

If we look at the definition of the term in the context of dictionary learning, for example in K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation, the term is defined:

Sparse coding is the process of computing the representation coefficients $\mathbf x$ based on the given signal $\mathbf y$ and the dictionary $\mathbf D$.

So sparse coding is the operation of finding a sparse representation of a given signal in a given dictionary. In relation to compressed sensing this seems to me to be the most relevant interpretation of the term. As such, sparse coding is closely related to compressed sensing, but compressed sensing specifically deals with finding the sparsest solution to an under-determined set of linear equations which, as the theory shows, is the correct solution in this case with high probability. Sparse coding is then more general in the sense that it does not necessarily deal with an under-determined set of equations.

Answer 2

As you correctly noted compressed sensing, compressive sampling, sparse sampling all mean the same thing. Some authors also call it sparse sensing. The idea behind compressed sensing is that a sparse signal can be recovered from very few linear measurements. In symbols, if $\mathbf x$ is $N\times 1$ sparse$^\ddagger$ vector, and $\mathbf A$ is an $M\times N$ matrix with $M\ll N$, and we measure $\mathbf y=\mathbf{Ax}$, then compressed sensing theory tells us$^\dagger$ that we can exactly recover $\mathbf x$ from $\mathbf y$. This is remarkable because it says that we can recover the original signal from fewer measurements.

Dictionary learning on the other hand deals with an entirely different problem of representing a bunch of data vectors in a parsimonious way. Given a set of data vectors $\{\mathbf x_1, \mathbf x_2,\ldots, \mathbf x_K\}$, we would like to find another set of vectors $\{\mathbf v_1, \mathbf v_2,\ldots, \mathbf v_L\}$ (called "atoms") such that that each data vector $\mathbf x_i$ can be represented as a linear combination of these $\mathbf v_j$'s. The set of atoms is called a dictionary. The goal here is to learn a dictionary that is much smaller than the number of data vectors$^*$ i.e. $L < K$.

Given a set of atoms in a dictionary and a vector $\mathbf y$, the goal of sparse coding is to represent $\mathbf y$ as a linear combination of as few atoms as possible.

Finally, sparse dictionary learning is a combination of dictionary learning and sparse coding. The goal here is two-fold: finding a parsimonious representation of the set of data vectors and ensuring that each data vector can be written as a linear combination of as few of the atoms as possible.

Compressed Sensing v/s Sparse Coding
Both of these techniques deal with finding a sparse representation but there are subtle differences.

Compressed sensing deals specifically with the problem of solving an underdetermined system of linear equations i.e. fewer data points than the original signal. From an unknown sparse signal $\mathbf x$ and sensing matrix $\mathbf A$, we observe the data vector $\mathbf y = \mathbf{Ax}$. $\mathbf A$ has fewer rows than columns. Compressed sensing theory deals with the following kinds of questions questions:

1. Under what conditions is the under-determined set of linear equations solvable and how do we solve it in a noise-robust, computationally tractable manner?

2. How do we design sensing matrices $\mathbf A$ for various applications?

In contrast, sparse coding does not deal with the question of designing $\mathbf A$. Moreover you aren't interested in solving under-determined system of equations --- $\mathbf A$ is allowed to have more rows than columns.$^\%$

References:

Compressive Sensing [Lecture Notes]

Dictionary Learning

Online dictionary learning for sparse coding

Footnotes:

$^\ddagger$ Sparse means the vector has very few non-zero elements.

$^\dagger$ $\mathbf A$ and $M$ need to satisfy some technical conditions.

$^*$ Unlike standard transform methods such as Fourier transform, dictionary learning is data-adaptive. When taking a Fourier transform, the basis vectors $\mathbf v_j$'s are fixed ahead of time (complex exponentials). In dictionary learning, they are learned from data.

$^\%$ This is called an over-complete dictionary.