2
$\begingroup$

There are theories based on signal sparsity in frequency domain like Compressive Sensing, Sparse FFT, etc. Throughout searching and studying papers I found out Cognitive Radio is a good example of application of Fourier sparse signals in real world. However, I am curious what are other applications in which the input signal is 1-D and is also sparse? or if there is any? I feel there should be some important applications where the signal can be modeled as sum of a few sine functions, but I can't find any.

  • So, my question is in which applications the input signal sparse in Fourier (only) and is 1-Dimensional?

I would appreciate a lot any suggestion.

$\endgroup$
  • 1
    $\begingroup$ Can you please provide some more information about what your question is about exactly? Is the question about Sparse Signals and how frequently these are encountered in practical applications for example? $\endgroup$ – A_A Nov 28 '16 at 14:50
2
$\begingroup$

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." 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.

$\endgroup$
4
$\begingroup$

Sparsity concept is extensively being used in computer vision and image processing. The Idea is that natural image can be pretty sparse when it is transformed to different bases. this bases can be predefined, e.g. FFT,DCT or can be learned from the image, e.g. sparse coding.

Here are a few well know example of algorithms that uses the sparsity assumption on images:

  1. Jpeg image compression: Uses DCT transformation. assumes that high frequencies are low in natural image, so they are being removed in order to preserve space for compression. see more information on Wikepedia
  2. Sparse coding: is a technique being used that assumes that an image has a lot of redundant information and because of that can be reconstructed from an overcomplete dictionary. each patch in the image should be sparse combination in the dictionary. see instroduction to sparse representation presentation
  3. inverse problems in computer vision like recovering image embedded in noise and recovering sharpe image from blurred image are also using sparse assumption, e.g. wavelete shrinkage is being used for image denoising. See application to wavelet trasform in here
$\endgroup$
  • $\begingroup$ thanks for the answer. Honestly, I meant application in which the signal is 1-D and Fourier sparse. I notices I screwed my problem statement so modified the question. Would you please provide me with your suggestions about 1-D fourier sparse signals. $\endgroup$ – MimSaad Nov 30 '16 at 8:28
2
$\begingroup$

A couple of example areas:

  1. Sonar beamforming - in many cases there are a small number of targets
  2. Radar processing - a radar image can be decomposed to a background and sparse set of point like targets, or a small number of moving targets.
  3. Radar tomography - This application uses multiple radar passes at slightly different elevations to extract elevation information from the multiple Synthetic Aperture Radar (SAR) images (similar to interferometry). In the far range this looks pretty much like narrowband beamforming - so it is looking for spatial frequencies rather that temporal ones.

Many of these topics are discussed at the yearly CoSeRa conference

The sparsity concept can also be extended to matrices - you now consider the rank of the matrix - it can be thought of as the $l_0$ measure for matrices. You are trying to minimize the rank of the matrix, but rank is not convex function, so you then look at minimizing the nuclear norm (sum of the singular values). This is basis for problems like the Netflix problem - where you have incomplete entries of a matrix and you are trying to fill in the entries you don't know.

$\endgroup$
  • 2
    $\begingroup$ To be pedantic, the $l_0$ "measure" is not a norm. $\endgroup$ – Thomas Arildsen Nov 29 '16 at 14:26
  • 2
    $\begingroup$ @ThomasArildsen True - I changed it to read "pseudo-norm". $\endgroup$ – David Nov 29 '16 at 14:54
  • $\begingroup$ @ThomasArildsen,@David, thanks for suggestion on Sonar beamforming. About 2-D signal, honestly I was aware of such application, in my question I meant 1-D fourier sparse signals in real application, and unfortunatlly I didn't state it correclty. Now I'v edit the post so would you please provide me with your suggestions about 1-D fourier sparse signals. $\endgroup$ – MimSaad Nov 30 '16 at 8:30
  • $\begingroup$ In the sonar you could look at target signatures - extraction/identification of frequency components. Radar tomography is well suited to compressive sensing since their are usually only a few measurements and they are at pretty much random positions. $\endgroup$ – David Nov 30 '16 at 13:53
  • 1
    $\begingroup$ @LaurentDuval Yes, you are correct; $l_0$ is not a norm or even quasi or pseudo. Unfortunately, referring to the $l_0$ norm appears quite frequently in the literature: here (see page 280), Chapter 5 here, or Ch2 here $\endgroup$ – David Apr 8 at 13:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.