June 2023

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.

Read More

Graph Signal Processing

Introduction

Signals are everywhere. In the present world, signal processing is likely to be changing into information processing with the introduction of new research trends like Topological signal processing, Graph signal processing, Data-Driven approaches for imaging systems (including neural networks), Data-Driven beamforming techniques for 6G and Beyond communication systems, latest video compression standard VVC and some new ones to many models like Multimodal Speech recognition. Thanks to some ground-breaking inventions such as the Fast-Fourier Transform, linear filters, and Kalman filter, which are distinctive to open the pathway of such overwhelming trends. Here, we are going to do a brief discussion on Graph signal processing. 

First of all, what is signal processing? Why is it considered to be one of the pioneering fields for research? The answers to these questions lead us to the following discussion. The representation, analysis, and manipulation of signals are dealt with within the field of engineering and applied mathematics, known as signal processing. Any quantity that carries information is a signal, including time-varying voltages, sound waves, and images. Signal processing’s objective is to extract information from signals and portray it in a more practical and understandable manner. Filtering, Fourier analysis, compression, and feature extraction methods are used to achieve this. Numerous industries, including telecommunication, voice and image processing, control systems, and biomedical engineering, use signal processing in various ways. Signal processing uses mathematical techniques and models to analyze and alter signals to extract useful information, enhance signal quality, or decrease the quantity of data required to describe the signal. As the requirements and capacities of different application areas evolve, new approaches are continually being created in the sector. 

Graph Signal Processing

Data is everywhere in massive quantities in the present technological world. Almost every aspect of our day-to-day life is recorded at one or many different kinds of levels. Our personal health data are recorded and processed through health monitoring devices and apps, various types of financial and banking data, our web searches, our social networks, and our mobility by traffic patterns. Each of these data is being recorded by any means. The complexity of such networks and interactions means that the data now resides in more irregular and complex structures. So to process these kinds of complex data into precise, meaningful information, we need new tools.

In Simple words, Graph signal processing (GSP) can be briefly described as a branch of signal processing, concerned with the study and control of signals defined on graphs. The interactions between the signal samples in GSP are modeled as graphs, which may subsequently be examined using graph spectral theory, graph filters, and other graph-based processing methods. In order to handle signals with underlying structures such as those that emerge in social networks, brain connections, and other complex systems, GSP aims to expand the capabilities of conventional signal processing techniques.

Graph Signal. Source: https://link.springer.com/chapter/10.1007/978-3-030-03574-7_1

For example, let us consider a state which has 8 cities. Suppose we need to represent the number of automobiles in each city. As shown in the figure, we can represent this information as a graph. Each light green vertex represents a city and its location in the state. The route between the two connected cities might be interpreted as the boundaries separating the cities. The number of vehicles, a scalar value, is represented by the red vertical line. Therefore, as the red line rises, so does the city’s automotive population.

Graphs offer the ability to model such complex data and interactions between them. The data can be modeled into nodes and edges. Graph signal processing introduces exploration and analysis of such nodes and edges by adding attributes and modeling those as signals on a graph. For example, the  temperature in a given city on a given day in a weather network. Representing such data into graphs requires us to extend classical signal processing concepts and tools such as Fourier Transform, Filtering, and frequency response to data residing on Graphs. It also leads us to tackle complex tasks such as sampling in a principled way.

Classical signal processing signals can stem from various domains. However, the underlying graphs can tell a fair amount about those signals through their structure. Different types of Graphs model different types of data and complex networks. Such graphs include Erdos-Renyi graphs, ring graphs, random geometric graphs, small-world graphs, and scale-free graphs. As in classical signal processing, graph signals can have properties such as smoothness that needs to be appropriately defined. They can also have spectral representation. In particular, the Graph Fourier Transform allows us to develop intuition gathered in the classical setting and extend it to graphs; we can talk about the notions of frequency band limitedness, for example, we can filter graph signals. They can be sampled, we can denoise graph signals, learn their underlying structure, and model them.

Additionally, there is a lot of promise for Graph Signal Processing to be used in sensor networks, smart grids, medical neural networks, the internet of cars, and other areas. Graph Signal Processing techniques are frequently implemented on the network using a single processing center in a centralized fashion. The centralized processing solution offers the benefits of being simple to implement and flexible when scheduling resources.

However, when the scale of the network grows, the centralized approach’s computational complexity quickly rises, necessitating more expensive gear. Additionally, the network as a whole may become paralyzed if the central node is attacked from the outside.

References

[1] A. Ortega, P. Frossard, J. Kovačević, P. Vandergheynst, and J. M. F. Moura, “Graph Signal Processing: Overview, challenges, and applications.” [Online], 2018. Available: https://ieeexplore.ieee.org/document/8347162.

Read More