# What exactly is “sparse representation”? [closed]

I saw a recommended topic for the final project in my university called "dsp and dip applications using sparse representation techniques (MATLAB, C, C++)".

I consider taking this topic as my final project, but there are not so many things about it on the internet to understand what this is exactly.

So, I would like to hear some clear answers about it and some opinions about how productive would that be for me considering that I want to learn more and more about dsp and dip.

• sorry, it's not clear what your question is, although you wish answers. Remember, this is a Q&A site, and you need to do the Q(uestion) yourself. Now, I'm not sure I agree to "there's not many things on the internet about sparse signal representation techniques"; that doesn't match my experience. "Sparse Representation", however, is not an entry-level topic. I think the fact that you're not formulating a clear question might betray the fact that you don't have DSP basics. In that case, maybe, in your own interest, pick a topic for which you're well-equipped, skill-wise. – Marcus Müller Mar 10 '18 at 13:57
• (I know you've got "What exactly is "sparse representation"?" in your title, but that title really just says "I haven't really researched much"; as a question, it's IMHO far too broad. The first hit on google for "sparse representation" takes you to the wikipedia, and you show no sign of having tried to read that page.) – Marcus Müller Mar 10 '18 at 14:49

Take a sine-like signal $s$. In the appropriate Fourier $\mathcal{F}$ domain, it is represented by two "peaks", the other coefficients being zero. Fourier is a sparse representation for sines or close-to-sine signals. Conversely, a zero signal, except for a few values, is sparse in its original domain.

In narrow sense, a sparse representation of data is a representation in which few parameters or coefficients are not zero, and many are (strictly) zero. This can be measured by the $\ell_0$ count index, which yields the number of non-zero components. Here, $\ell_0(\mathcal{F(s)})=2$.

However, in practice, it is very rare to have few exactly non-zero components, and a lot being exactly zero. This happens especially as floating point computations are rarely exactly zeros, albethey very small. You can see for instance the simulations for Why is $\exp(\ln(x))-x \neq 0$ in floating point arithmetic?

So, broader senses are accepted in practice, amounting to few high components, many small components. I will thus extend the discussion on terminology on either "sparse" and "representation". On sparsity, or parsimony, one should mention the economy principle, law of parsimony or Ockham's razor:

An explanation of a thing or event is made with the fewest possible assumptions

Initially, this pre-scientific principle has being used in theological debates. In science, it is used as a heuristic guide in the selection or development of theoretical models. One early example is the geocentric model. Starting from the belief that Earth was the center of the Universe, further observations revealed complicated star motion patterns, building a model with complex (epicycloidal) curves, requiring many parameters to explain. Until some understood that the hypothesis of a centered earth was not appropriate, and that other models could provide simpler explanations, and formulae, with the same, or a better, prediction or description power. Kepler or Newton laws were way more efficient.

Another example is polynomial representation: suppose that you have fifteen couples of $x_i,y_i$ values that you want to use for prediction. Of course a Lagrange polynomial of degree 14 will fit then perfectly. Should it be used for prediction? Probably not, as data are imprecise, and the polynomial extrapolation will be unstable; maybe, a one or two degrees fit, according to some cost function, might be more appropriate. The idea is that two or three parameters (slope/intercept/second degree term) could be more efficient for a given task.

We now have the major ingredients. Take a set of data $d_i$, with meaningful content. The data generally has many dimensions, $i\in \mathcal{I}$ (think about the number of pixels in images). There is some expectation that there exists a combination of a small subset of features (sparsity) $c_k$ that can faithfully describe the dataset, or predict, infer from this dataset. In other words, with $k\in \mathcal{K}$, with cardinals such that $|\mathcal{K}| \ll |\mathcal{I}|$, there is a transformation $T$ such that the quantities $d_i - T(c_k)$ are small enough.

In the case of sines, $|\mathcal{K}|=2$ is sufficient in a Fourier basis. In practice, one tries to have sequences of $c_k$ such that most of them are very small (if not zero), and few of them recovers data correctly. There are measures to quantify the sparseness of a sequence, and to quantify how close the sparse representation is to the actual goal.

Transformations to represent data are standard tools from harmonic analysis (Fourier, Wavelets, filter banks, Radon, bases or redundant frames), statistical analysis (least-square regression, PCA, PLS, lasso, ridge regression), clustering and segmentation tools, etc. The distance is often some norm or quasi-norm. Even neural networks strive to provide learned sparse representations from a training set.

Sparsity indices are 0-homogeneous (Gini index, norm ratios) or akin to norms or quasi-norms for minimization purposes. Some use a milder description, i.e. the compressibility, reordering coefficients $T(c_k)$ with decreasing magnitudes $|(c_{\sigma(k)}|$ and studying the exponent $\alpha\le 0$ such that:

$$\|d_i - T(c_{\sigma(k)})\| \leq K|k|^{\alpha}$$

or "how fast compressible representations can approximate a data or a dataset".

I consider the idea of sparse representations to be a key driver in machine learning, classification, compresison, and you can find a plenty of ressources to reuse.

• sparsity being understood as Ockham's Razor for signals :) Awesome metaphor! Have a well-earned upvote, especially since I've only read the intro section of your paper and already like it very much! – Marcus Müller Mar 10 '18 at 18:50
• Jeje. There is much more to it. If you saw the movie "The name of the rose", Sean Connery is Guillaume (of Ockham) on purpose – Laurent Duval Mar 10 '18 at 19:04
• very clear and well explained answer. Thank you very much! – agelosnm Mar 11 '18 at 8:46