# Sparse Signal Reconstruction via L1-minimization

This is a follow-up of the previous post on applications of L1 minimization.

As we know, any signal can be decomposed into a linear combination of basis, and the most famous one is Fourier Transform. For simplicity, let’s assume that we have a signal that is a superposition of some sinusoids. For example, the following:

With *discrete consine transform* (DCT), we can easily find the coefficients of
corresponding sinusoid components. The above example’s coefficients (in
frequency domain) and signal in time domain are shown in the post figure.

Now, let’s assume we do not know the signal and want to reconstruct it by sampling. Theorectically, the number of samples required is at least two times the signal frequency, according to the famous Nyquist–Shannon sampling theorem.

However, this assume zero-knowledge about the signal. If we know some structure
of the signal, e.g., the DCT coefficients are sparse in our case, we can
further reduce the number of samples required. ^{1}

The following code snippet demonstrates how this works. We generate the original signal in time domain and then perform a DCT to obtain the coefficients.

Let’s assume that we have a device that can sample from the frequency domain.
To do this, we create a *random measurement matrix* to obtain the samples.
We use 80 samples here. Note that we normalize the measurement matrix
to have orthonormal basis, i.e., the norm of each row is 1, and the dot product
of different row is 0.

We first try a least-square approach, which boils down to inverse the matrix
and obtain \(\hat{x}=A^{-1} b\). Note that as A is not square, we are
using its *pseudo-inverse* here. Furthermore, as A is othornormal, its
transpose is the same as pseudo-inverse.

As we can see, there are lots of non-zeros in the coefficients, and the recovered signal is very different from the original signal.

Finally, we use L1-minimization for reconstruction. I used `lasso`

to perform a L1-regualarized minimization. Another package that performs various
L1-minimization is l1-magic.

The above shows that L1-minimization successfully recovered the original signal. A complete code snippet can be found here.

## Comments