### 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 ∥·∥_{0} 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**

*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

### Spark Challenge Crowns Champions After Electrifying Grand Finale!

The Department of Electronic and Telecommunication Engineering at the University of Moratuwa buzzed excitedly on June 7th, 2023, as the Spark Challenge 2022/23 held its much-anticipated pitching Session. Teams brimming with innovative ideas battled it out, leaving the judges with a tough decision.

Five teams were chosen to advance to the Grand Finale following the session, marking the culmination of nearly a year of brainstorming and development. At the finale, which was held on the 11th of June 2023 at the Civil Auditorium, the top five competitors presented their final pitches. After an exciting final round, the winners were invited onto the stage. Team Spectro, who proposed a solution to the energy crisis where biological processes of green algae could be used to produce hydrogen power, emerged as the second runner-up of the challenge. Then the first runner-up award went to the team Techstatic, who implemented a product which had the capability of warning the farmers about the fertilizing requirements after analyzing the soil condition. Then, finally, the winner was the Team Pathfinders, who came up with a solution for picking up the right balance of chemical composition for different crops.

A true engineer must engage in professional-level projects that address real problems the world faces. The SPARK challenge will reward individuals and groups that create unique, innovative, socially, and environmentally responsible solutions to bring about significant positive transformative impact on society, industry and the wider environment. We had many students getting engaged with electronic-telecom projects over a period of one year under this challenge.

Congratulations to all the participants who poured their hearts into the competition! The Spark Challenge continues to be a breeding ground for Sri Lanka’s brightest minds, fostering solutions for a sustainable future. SPARK challenge will continue with another episode in 2024.

Read More### Graph Signal Processing

*Introduction*

*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*

*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