This is a followup 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:
1


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 zeroknowledge 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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 

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.
1 2 3 4 5 6 7 

We first try a leastsquare 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 pseudoinverse here. Furthermore, as A is othornormal, its transpose is the same as pseudoinverse.
1 2 3 4 5 6 7 8 9 10 11 

As we can see, there are lots of nonzeros in the coefficients, and the recovered signal is very different from the original signal.
Finally, we use L1minimization for reconstruction. I used lasso
to perform a L1regualarized minimization. Another package that performs various L1minimization is l1magic.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

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