I am trying to find a sparse representation of a signal consisting of a single sinusoid and a single spike (delta function), via what I think is traditionally called "basis pursuit", using $L_1$ norm minimization. Specifically, I have a discrete-time signal $y$, and I solve the following problem:
minimize ${||x||}_1$, s.t. $Dx = y$
Consider the following cases that I have tried, in MATLAB, using a convex optimization package (CVX):
Case 1: Here, $y$ is a single sinusoid, and $D$ is the inverse discrete Fourier transform (IDFT) matrix. In this case, I am able to recover the DFT of $y$ (i.e., if I solve the above problem, the $x$ I get is indeed the DFT of $y$). The solution is indeed sparse, since there is only one non-zero coefficient. Everything works well here.
Case 2: Here, $y$ is the sum of the same sinusoid as that used in Case 1, and a spike/delta function. That is, somewhere in the middle, there is a spike in $y$. Thus, $y$ is no longer sparse in the Fourier domain. Some other dictionary $D$ must be chosen in the above problem in order to find a sparse $x$. The introduction of the spike brings to mind the trivial basis (kronekcer delta). However, $y$ is not sparse in this basis either, since it contains a sinusoid too. So, I tried the following overcomplete dictionary:
$D = [\Psi~ I]$
where $\Psi$ is again the IDFT matrix ($n \times n$), and $I$ is a ($n \times n$) identity matrix (where $n$ is the length of the signal $y$). In this case, $x$ would be a vector of length $2n$.
What I expected to find as the solution $x$ was a sparse solution where in the first $n$ elements of $x$ contain the DFT coefficients, and the last $n$ elements contain the delta-basis coefficients (i.e., the spike). However, this was NOT what I got.
What I got as the solution for $x$ was in fact the following: the first $n$ elements are all zero, and the last $n$ elements contain the signal $y$ itself. Thus, the optimal $x$ was not sparse at all. At first I thought the solver was not giving me the optimal point. But I verified that this was indeed the minimum $L_1$ solution. The $L_1$ norm of $y$ (and thus, the $L_1$ of the solution $x$ I got, which contained $y$ in the second half corresponding to the delta basis) was less than the $L_1$ norm of the sparse $x$ (the one with the DFT coefficients in the first half and the time-domain spike in the second half) that I would have expected to get.
Thus, my conclusion here was that in this problem, with the specific overcomplete $D$ that I had chosen, minimizing the $L_1$ norm was not a good enough proxy for minimizng the $L_0$ norm.
I then modified $D$ a bit, by removing some of the columns at the end from the identity matrix part of it (but not the column corresponding to the spike location!). In particular, I tried the following (using some MATLAB notation):
$\tilde{D} = [\Psi~~ I(:,~1:n-p]$, where $p$ is small integer, such as 2.
I then got the sparse solution I wanted!
Here is my question finally:
What is wrong with my choice of $D = [\Psi~ I]$ (where $I$ is the full identity matrix, thus $D$ has size $n \times 2n$)? Why does $\tilde{D}$ work? Does $D$ not satisfy some properties (incoherence?) needed for $L_1$ minimization to be sufficient?
I suspect that the answer has something to with the 'incoherence' requirement, but don't quite understand that. Is this true? If so, can you explain what the requirements on $D$ are?
Thanks!
It may be the case that your columns aren't normalized. In order for basis pursuit to work, the columns need to all be roughly the same length ($\ell_2$ norm).
The columns of the inverse DFT are usually of magnitude $1/\sqrt{n}$, whereas the columns of identity matrix are of unit magnitude. So if $n$ is large, then this could prevent finding the sparse solution.