Sparse Signal Processing

What are Sparse Signals?

A sparse signal is a signal which has a representation in some domain where the number of non-zero elements in that domain is significantly lower than the signal length . In other words, these signals can be represented digitally with a high degree of accuracy by relatively few non-zero coefficients. Many of the signals occurring in nature related to human life are sparse. In signal processing, this constraint can be exploited for a diverse range of applications using the concept of compressive sensing, which reconstructs the sparse signal from a reduced set of measurements. This field is of much interest among researchers and engineers due to the algorithms and applications involved and the continuing expansion of the boundaries of its capabilities.

What are the Algorithms?

To this end, we consider the following data acquisition model.

y=Ax+z,

Here, the observation vector of length k is given by y and x is the sparse signal of length m. Our objective is to estimate x from the noisy measurements y. The matrix A is a linear operator (also known as Dictionary), that maps the vector space ℜm to vector space ℜk with m k.  The additive observation noise is given by z. Since  x is sparse, that property can be utilized to estimate x  as follows [Nat95],

In the above equation, the L0-norm of a vector is represented by ∥·∥₀ and it is equivalent to the  number of nonzero elements in the vector. Also, the the noise bound is given by ϵ. The above optimization problem is non-convex and NP-hard [Nat95]. The most common approach to tackle above NP-hard problem is replacing the L0-norm with  L1-norm (absolute sum of elements) [CRT06a] and the new transformed problem is known as basis pursuit denoising (BPD) [CDS01] or least absolute shrinkage and selection operator (LASSO) [Tib96]. 

Further, under reasonable conditions, an NP-problem could be solved numerically. Some examples are the direct search method, matching pursuit approaches [MZ93], base pursuit approaches, and thresholding approaches like iterative soft thresholding algorithm (ISTA) [DDDM04] and fast ISTA [BT09].

It is worth considering how the demand for real-life applications means that very efficient algorithms are needed for time critical applications. This also includes developing new algorithms which are capable of obtaining signal reconstructions from even fewer data and which have a better tolerance to noise and signal non-sparsity.

What are the Applications?

The applications in sparse signal processing are numerous, including signal processing, image processing, computer vision, machine learning, and data compression. It is useful not only in compression but also in cases where obtaining a complete number of samples of a signal is either expensive, inconvenient, or even impossible. The incomplete signal can be used to reconstruct the original sparse signal. Applications of this nature include image and audio reconstruction and in Radar signals, and ECG signals. 

Images can generally be assumed to be sparse in their two-dimensional discrete cosine transform representation. The pixels of an image may be corrupted due to noise. These corrupted pixels can be detected and removed. The image can be reconstructed later using the reduced set of measurements. This is possible by exploiting the sparsity property of common images. The reconstruction of a corrupted image by using the gradient algorithm is shown in the figures below.

(Original image)(Figure 1)

‘

(Corrupted image)(Figure 2)

(Reconstructed image)(Figure 3)

Image is adapted from “A Tutorial on Sparse Signal Reconstruction and its Applications in Signal Processing” by Ljubiša Stankovic, Ervin Sejdic, Srdjan Stankovic, Miloš Dakovic, and Irena Orovic

In Inverse Synthetic Aperture Radar(ISAR), a two-dimensional Fourier transform of the received signal is used to construct the image of a target body. The image is a highly concentrated two-dimensional function. It has peaked at the target range and cross-range positions of the body. The number of non-zero pixel values in the image is much lower than the total number of pixels present. Hence it can be considered sparse. Therefore, any unavailable or corrupted data can be compensated by reconstructing the signal from received error-free data. The usage of a reduced set of radar signals to reconstruct the original radar signal is shown in Figure (4).

Figure (4) – A single iteration based algorithm applied to the simulated radar signal applied to a simulated radio signal. Image is adapted from “A Tutorial on Sparse Signal Reconstruction and its Applications in Signal Processing” by Ljubiša Stankovic, Ervin Sejdic, Srdjan Stankovic, Miloš Dakovic, and Irena Orovic

Where to next?

Even though many such applications and algorithms have been developed, there are many unsolved questions existing in this field. For example, there is a need for computationally efficient uniqueness tests and optimal testing strategies. The context behind compressive sensing has also been changed in newer models as the constraints involved in sparse signal reconstruction are relaxed to allow inaccurate data measurements. Examples included modifications for dealing with wideband analog signals and reconstruction methods that adapt as new measurements are obtained.

Compressive sensing is especially exciting due to its interdisciplinary nature. There are many papers considering multiple aspects such as algorithm development, theoretical problems and possible applications. The discoveries and inventions made in the fields of applied mathematics, pure mathematics, and engineering act together to propel the frontiers of compressive sensing forward. The field continues to be of great interest as more applications and algorithms are yet to be discovered.

References

[Nat95] B. K. Natarajan, “Sparse approximate solutions to linear systems,” SIAM J. Comput., vol. 24, no. 2, pp. 227–234, 1995.

[CRT06a] E. J. Candes, J. K. Romberg, and T. Tao, “Stable signal recovery from incomplete and inaccurate measurements,” Commun. Pure Appl. Math.: A Journal Issued by the Courant Institute of Math. Sci., vol. 59, no. 8, pp. 1207–1223, 2006

[CDS01] S. S. Chen, D. L. Donoho, and M. A. Saunders, “Atomic decomposition by basis pursuit,” SIAM review, vol. 43, no. 1, pp. 129–159, 2001.

[Tib96] R. Tibshirani, “Regression shrinkage and selection via the LASSO,” J. R. Stat. Soc.: Series B (Methodological), vol. 58, no. 1, pp. 267– 288, 1996.

[MZ93] S. Mallat and Z. Zhang, “Matching pursuits with time-frequency dictionaries,” IEEE Trans. Signal Process., vol. 41, no. 12, pp. 3397– 3415, 1993

[DDDM04] I. Daubechies, M. Defrise, and C. De Mol, “An iterative thresholding algorithm for linear inverse problems with a sparsity constraint,” Commun. on Pure and Applied Math.: A Journal Issued by the Courant Institute of Math. Sci., vol. 57, no. 11, pp. 1413–1457, 2004.

[BT09] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM journal on imaging Sci., vol. 2, no. 1, pp. 183–202, 2009.