Tropp’s Exact Recovery Condition for Basis Pursuit

Yesterday, I looked at Tropp’s exact recovery condition (ERC) for orthogonal matching pursuit (OMP). Today, I continue with his extrapolation to basis pursuit (BP), otherwise known as the principle of relaxing the definition of strict sparsity by the \(\ell_1\)-norm.
Assume, as yesterday, we have a \(m\)-dimensional signal \(\vx\) with a unique and \(s\)-sparse representation in a dictionary \(\mathcal{D} = \{ \vd_i : i \in \Omega\} \) of \(N\) atoms, notated in matrix form as \(\MD\).
Also, all \(s\) atoms participating in this representation are the columns of the matrix \(\mathbf{\Phi}_\vx\);
and I notate the indices of the atoms not participating as \(\Psi\).
Assume for this signal \(s\) is as small as possible.

Theorem 3.3 in J. Tropp, “Greed is good: Algorithmic results for sparse approximation,” IEEE Trans. Info. Theory, vol. 50, pp. 2231-2242, Oct. 2004, states

\max_{i \in \Psi} ||\mathbf{\Phi}_\vx^\dagger \vd_i ||_1 < 1
is a sufficient condition for recovering the sparsest representation of \(\vx\) from a dictionary \(\mathcal{D}\) by solving the problem
\min_{\vs \in \mathcal{C}^N} || \vs ||_1 \; \textrm{subject to} \; \vx = \MD \vs.

It is amazing the same condition that applies to OMP also applies to BP — but I bet one is sharper than the other. Now, let’s look at the proof.

We start by assuming \(\vx\) has another representation \(\vx = \mathbf{\Phi}_\vx’ \vs_\vx’\) different from the ideal one \(\vx = \mathbf{\Phi}_\vx \vs_\vx\) — which is not an assumption if \(\MD\) is full rank. And no trivial solutions here: all elements in \(\vs_\vx’\) are non-zero.
As long as the coefficients in \(\vs_\vx’\) are different from \(\vs_\vx\) (the vectors cannot even be the same dimension with our assumption of an optimal \(s\) sparse representation of \(\vx\)),
then \(\mathbf{\Phi}_\vx’\) has at least one column (atom), call it \(\vh\) that is not in \(\mathbf{\Phi}_\vx\) (for instance, one that is a linear combination of two in \(\mathbf{\Phi}_\vx\)).
Now, looking at the \(\ell_1\)-norm of the optimal solution,
and using the fact that \(\mathbf{\Phi}_\vx^\dagger \mathbf{\Phi}_\vx \vs_\vx = \vs_\vx\),
we see that
|| \vs_\vx ||_1 & = || \mathbf{\Phi}_\vx^\dagger \mathbf{\Phi}_\vx \vs_\vx ||_1 \\
& = || \mathbf{\Phi}_\vx^\dagger \vx ||_1 \\
& = || \mathbf{\Phi}_\vx^\dagger \mathbf{\Phi}_\vx’ \vs_\vx’ ||_1.
We can bound this last expression. Assuming that all elements of the vector \(\vb\) are non-zero, and that each column of the matrix \(\MA\) has different \(\ell_1\) norms.
Then, we can say \(|| \MA\vb||_1 < ||\MA||_1 || \vb||_1\).
There is no equality here because we are assuming that all elements of \(\vb\) are non-zero,
and the columns of \(\MA\) are all different.
Applying this above, we find
|| \vs_\vx ||_1 & = || \mathbf{\Phi}_\vx^\dagger \mathbf{\Phi}_\vx' \vs_\vx' ||_1 \\
& < || \mathbf{\Phi}_\vx^\dagger \mathbf{\Phi}_\vx' ||_1 ||\vs_\vx' ||_1.
As long as the ERC holds, we can bound \(|| \mathbf{\Phi}_\vx^\dagger \mathbf{\Phi}_\vx' ||_1 < 1\),
and finally \( || \vs_\vx ||_1 < ||\vs_\vx' ||_1\).
In other words, by minimizing the \(\ell_1\)-norm of the solution, BP will skip past any other solution as long as the ERC holds.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s