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.


  Bob L. Sturm
  Sofia Dahl
  Stefania Serafin


CRISSP @ Medialogy

↑ Grab this Headline Animator

Powered by Movable Type 4.34-en