# 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
The ERC $$\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 \begin{align} || \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. \end{align} 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 \begin{align} || \vs_\vx ||_1 & = || \mathbf{\Phi}_\vx^\dagger \mathbf{\Phi}_\vx' \vs_\vx' ||_1 \\ & < || \mathbf{\Phi}_\vx^\dagger \mathbf{\Phi}_\vx' ||_1 ||\vs_\vx' ||_1. \end{align} 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.

CRISSP is a research group in ADMT at Aalborg University Copenhagen (AAU-KBH), Denmark.

Authors: Bob L. Sturm Sofia Dahl Stefania Serafin

### Archives 