Concepts

 

To allow for a better understanding of the compressive sensing framework, some of the most important concepts and challenges are presented.

 

   Signal Sparsity

 

A signal is sparse or sparsely approximated in a given basis when its representation has a very small number of non-zero coefficients.

 

One of the key components in the theoretical foundations of compressive sensing is that the target signal or class of signals are sparse in some basis (e.g. Fourier, Discrete Cosine Transform). The objective is then trying to find, from a set of M measurements much smaller than the N needed when using the traditional Shannon-Nyquist approach, the K coefficients needed to represent the target signal where K is smaller than M.

 

 

 

   Incoherent Sampling

 

Signal acquisition using compressive sensing is done through inner product operations between the target signal and a sensing matrix. With this operation, M measurements of the target signal are taken where each measurement may have a contribution of several components of the signal. There is a correlation between the number of measurements needed, the sparsity K, and the coherence between the measurement matrix and the basis where the signal is sparse. 

 

The coherence measures the correlation between any column of Ψ and any row of Φ and can be seen as an approximation of the degree of similarity between the sparsity and measurement systems. In order to be able to achieve a low minimum number of measurements, the rows of Φ must intersect as many dimensions of the basis space (Ψ) as possible. This will in turn allow for the discovery of the subset of dimensions where the signal lies with fewer attempts, or measurements.

 

Since the relation between the signal basis and the measurement matrix is so important in the decision of how many measurements are needed to achieve a perfect reconstruction, the construction of both has major repercussions on the global system. To allow for a simpler and universal sensing framework, most systems use a random sensing matrix, since these have been proven to show a low coherence with any fixed basis as long as having a sufficiently large dimensionality.

 

 

 

   Signal Reconstruction

 

Differently to what is seen in traditional, Nyquist-rate based systems where the major complexity is on the acquisition and the recovery of the signal is achieved by a simple sync-interpolation, when using Compressive Sensing the opposite occurs. While the acquisition step is extremely simple, the recovery of the original signal has several challenges. 

 

Since the number of measurements taken, M, is much smaller than the original dimensionality, N, of the signal, the recovery encompasses the solving of an undetermined system where the number of unknowns is larger than the number of measurements. This leads to a system where the number of feasible solutions is infinite. While this is true, the fact that the signal is sparse can be used to find the correct solution. Since the sparsity is what is expected, the correct solution is often the sparsest, meaning that the search should aim to find the solution with the least non-zero coefficients (using the l0-norm).

 

The straightforward approach would be to try and find, from all possible solutions the one with less non-zero coefficients but this would result in a combinatorial search and an NP-Hard problem. By relaxing the problem to using the l1-norm, it turns into a convex optimization problem for which extensive search has been done in many fields such as operations research. 

 

It is important to refer, though that while these are well defined problems and objectives, the exact recovery of a given signal from the set of incomplete measurements is always probabilistic. As the sensing matrix relies on the coherence with the signal model as well as the recovery algorithms trying to find the sparsest solution from an infinite set of possible ones, there are some signals that produce a full set of zeros as the result of the sensing operation. From this measurement vector, no recovery algorithm would be capable of finding the original signal. While this may seem a major problem, as long as the sampling size is sufficiently large, the probability of these cases occurring falls so close to zero that they can be seen as negligible.

 

Several algorithms have been developed over the years with the objective of solving the compressive sensing signal recovery problem, but this work will mainly focus on the orthogonal matching pursuit (OMP) and the iterative hard thresholding (IHT).