Skip to main content
Signal Processing

Return to Answer

added details
Source Link
Laurent Duval
Laurent Duval
  • 32.3k
  • 3
  • 35
  • 105

Rephrased, "simpler solutions are more likely to be correct than complex ones." In His history can be retraced in Il nome della rosa, a novel by Umberto Eco, and The Name of the Rose, a movie by Jean-Jacques Annaud: Guillaume de Baskerville is named along Ockham and Sherlock Holmes.

In the current context, this now involves (at least) two measures:

1- one that accounts for the error between the observed data and the sparse one, 2- one that measures the sparsity of the data, or the model behind the data.

  1. one that accounts for the error between the observed data and the sparse one,
  2. one that measures the sparsity of the data, or the model behind the data.

How one can balance between both measures is of current concern.

To come back to the "Real world application", a sparsity prior often helps find sound solutions to underdetermined systems. I have used them for actual sparse signals processing (chromatography, mass spectrometry), for adaptive filtering (assuming the adaptive system was sparse) and in compression contexts. However, one of the major difficulty lies in a proper and usable definition of "sparsity". THe $\ell_0$ count measure is rarely tractable, the $\ell_1$ proxy has limitations, and most often, sparsity penalties like $\ell_p$ ($p<1$) quansi-norms, $\log$ or norm-ratios are non-convex, and proofs and algorithms are still to develop.

Rephrased, "simpler solutions are more likely to be correct than complex ones." In the current context, this now involves (at least) two measures:

1- one that accounts for the error between the observed data and the sparse one, 2- one that measures the sparsity of the data, or the model behind the data.

How one can balance between both measures is of current concern.

Rephrased, "simpler solutions are more likely to be correct than complex ones." His history can be retraced in Il nome della rosa, a novel by Umberto Eco, and The Name of the Rose, a movie by Jean-Jacques Annaud: Guillaume de Baskerville is named along Ockham and Sherlock Holmes.

In the current context, this now involves (at least) two measures:

  1. one that accounts for the error between the observed data and the sparse one,
  2. one that measures the sparsity of the data, or the model behind the data.

How one can balance between both measures is of current concern.

To come back to the "Real world application", a sparsity prior often helps find sound solutions to underdetermined systems. I have used them for actual sparse signals processing (chromatography, mass spectrometry), for adaptive filtering (assuming the adaptive system was sparse) and in compression contexts. However, one of the major difficulty lies in a proper and usable definition of "sparsity". THe $\ell_0$ count measure is rarely tractable, the $\ell_1$ proxy has limitations, and most often, sparsity penalties like $\ell_p$ ($p<1$) quansi-norms, $\log$ or norm-ratios are non-convex, and proofs and algorithms are still to develop.

Source Link
Laurent Duval
Laurent Duval
  • 32.3k
  • 3
  • 35
  • 105

Sparsity covers a wide range of concepts. It characterizes an object (a signal, a system, a function) for which their exists a representation (exact or approximate) whose dimension (number of parameters, degrees of freedom) is much lower than the inherent dimension of the object. For instance, let us first consider 1.000.000 points $(x_i,y_i)$, acquired to measure a relationship between two continuous variables $X$ and $Y$. They are perfectly aligned in the plane. They can be modeled as a straight line $ax+b$, with only two parameters, much lower than the initial point quantity. In a way, the set of points (and their relationship) admits a deterministic sparse representation. A similar phenomenon appears when you model (in a stochastic way) a set of random values as a parametric probably law, like a Gaussian with a mean and a standard deviation.

Second, consider a measurement system for chemical mixtures. A nice measurement could provide a concentration for each atom/molecule in the mixture, at a given index, representative (a sort of signature) of each atom/molecule. The resulting signal would be made of a positive quantity (related to concentration) at each index where the molecule is present, and zero elsewhere. A lot of analytical chemistry methods (chromatography, infrared spectroscopy, Raman, etc.) are devoted to this purpose, as illustrated by the mass spectrometry signal shown on the top of the following picture: the signal is zero in a lot of places, with non-zero peaks on few places.

Mass spectrometry

Of course, reality is more complicated, and the peaks are not so narrow, as shown at the bottom. Yet, remains a feeling that the distorted sparse signal has way more small values that high-valued components. And if you communicate the data from the highest values to the lowest ones, you will get a progressive rendering of the data, the first high amplitudes having a high information content.

Here, we begin to extend the concept of sparsity to the idea of compressibility: high values (in some domain) yield faithful representation of the data, or high information content. Note that so far, faithfulness or information are not well defined. I'll come back on that later. Meanwhile, this means that the data may not be sparse by itself, but there is something compressible in it. The motivation is that when we measure something (including recording a song, taking a picture, measuring a physical experiment), we expect to extract some meaning from it. And a meaning (or a sense, or labels) is to the human of much lower dimensionality that signals. A million-pixel picture can be categorized as a "cat".

Compressibility does not assume that a large portion of data samples is zero. Indeed, with numerical limits on digital signals, noise and model uncertainty, that rarely happens in practice. Compressibility supposes that data can be turned into a series of coefficients that, sorted by magnitude, decay very fast, while providing a good approximation to the data. This may involve a transformation of the data, into a domain where the data is better concentrated. A typically example is transform-based compression, where data is cast to local Fourier, time-scale or time-frequency representations that can account for perceptual importance. This is used in MP3, JPEG or JPEG 2000.

If we go back to the past, sparsity is akin to the law of parsimony, or law of economy, related to the pre-scientific postulate by William of Ockham, known as Occam's razor:

"Entities are not to be multiplied without necessity" (Non sunt multiplicanda entia sine necessitate)

Rephrased, "simpler solutions are more likely to be correct than complex ones." In the current context, this now involves (at least) two measures:

1- one that accounts for the error between the observed data and the sparse one, 2- one that measures the sparsity of the data, or the model behind the data.

How one can balance between both measures is of current concern.