Chapter 4 Pursuit Algorithm--Guarantees

1. We assume the system Ax=b with A in nxm space where n<<m, and let x0 is its sparest solution with ||x0||_0=ko<spark/2.
2. Question: Will the MP(Matching Pursuit) or BP(basis Pursuit) or the OMP(orthogonal matching pursuit) suceed in recovering the sparsest solution?
3. Clearly this success can not be expected for all ko and for all the matrices A since this would be conflict with the NP-hardness of the problem.
4. Howerever, if we have a sufficient sparse solution, then the success can be guaranteed.

4.1 back to 2-Ortho Case

4.1.1 OMP performance Guarantee

1) Let A=[P,Q], and b can be represented as a linear combinations of the first kp columns of P and kq columns of Q, thus k0=kp+kq. Thus
\[ b=Ax=\sum_{i=1}^kp xi^P p_i + \sum_{i=1}^kq xi^q q_i \] (4.1)
2) Denote respectively S_p and S_q the intersection of supp(x) with col(P) and col(Q). Then
\[ |S_p| =k_p, |S_q| =k_q. \]
3) Step 0(k=0): r^k=r0=b; and error of sweep is defined as
\[ eps(j)=min_zj ||ajzj-b||^2=||(aj^Tb)aj-b||^2 =||b||^2 - (aj^T b)^2 \geq 0 \] (4.2)
4) Suppose first that |x1^p|=max|x_j|, then we have
(i) |p_1'b|>|p_j'b| and (ii) |p_1'b|>|q_j'b| ;
Then we get
|\sum_{i=1}^kp xi^p p1'pi + \sum_{i=1}^kq xi^q p1'qi| >
|\sum_{i=1}^kp xi^p pj'pi + \sum_{i=1}^kq xi^q pj'qi | (4.3)
Note that
lhs of (4.3) \geq |x1^p| -\sum_{i=1}^kp |xi^p| mu(A)
\geq |x1^p|(1-kq \mu(A)) (4.4)
rhs of (4.3) \leq |x1^p| kq \mu(A) (4.5)
Combing (4.3-4.4), we get
kq< \frac{1}{2\mu(A)} (4.6)

5) Similar argument when x1^q =max{xj} yields
kp< \frac{1}{2\mu(A)} (4.7)

6) Theorem 4.1(Equivalence--OMP--2-ortho Case): For a system of linear system
Ax=[P,Q]x=b, where P,Q: nxn are two orthogonal matrices, if a solution x has respectively
kp and kq nonzero entries in its first and second half, and the two obey
\[ max(kp,kq)<\frac{1}{2\mu(A)} \] (4.
Then OMP run with threshold parameter eps0=0 is guaranteed to find it exactly in k0=kp+kq steps.

4.1.2 BP Performance Guarantee

We now turn to analyze the performance of the Basis-Pursuit in the 2-ortho cases.

Theorem 4.2 (Equivalence--Basis Pursuit--2-ortho case) For Ax=b with A=[P,Q] where
P,Q\in R^{nxn} are both orthogonal matrices. let $x=[x_p,x_q]^T$ be a solution with x-p,x_q\in R^n and ||x_p||_0 =kp, ||x_q||_0 =kq, k_p\geq k_q, which satisfy
\[ 2μ(A)^2 kpkq+ μ(A)kp -1<0, \] (4.10)
Then $x$ must be both the unique solution of (P0) and (P1).
A weak version of (4.10) is
\[ ||x||_0 = kp+kq <\frac{\sqrt(2)-1/2}{μ(A)} \] (4.11)

Proof. Define
\[ C={ y| y\neq x, ||y||_1\leq ||x||_1, ||y||_0>||x||_0, A(y-x)=0 } (4.12)

First we prove that (4.10) implies
\[ kp+kq <1/μ. \] (4.13)
For this purpose we denote X=μkp, Y=μkq. If conversely (4.13) does not hold, then we have
\[ X+Y ≥1, X≥ Y \] (4.14)
So Y≥1-X, and 1/2≤X<1 (otherwise, (4.13) holds). Put all these into (4.10), we get
the lhs of (4.10) =2XY+X-1 ≥ （1-X）（2X-1）>0 , which contradicts (4.10). Thus (4.13) holds.
Now ||x||_0=kp+kq <1/μ, and Th2.3 tells that x is the sparsest solution, i.e., it is the unique solution to (P0). Denote $e=y-x$, then we can rewrite C as
\[ C_s ={ e| e\neq 0, ||e+x||_1-||x||_1≤0, Ae=0 } \] (4.15)
We intend to prove that |C_s|=0, i.e., C_s is empty. This does mean that the unique sparsest solution to (P0) is also the unique solution to (P1). Thus we need only to solve (P1).

We partition x and e according to P and Q, and denote x'=[x^p', x^q'] and e'=[e^p', e^q']. Then
\[
0≥|e+x|_1 -|x|_1=\sum_{i=1}^n |ei^p+xi^p|-|xi^p| + \sum_{i=1}^n |ei^p+xi^p|-|xi^p|
=\sum_{i\notin S_p} |ei^p| + \sum_{i\notin S_q} |ei^q|
+\sum_{i\in S_p} |ei^p+xi^p|-|xi^p| + \sum_{i\in S_q} |ei^q+xi^q|-|xi^q|
≥\sum_{i\notin S_p} |ei^p| + \sum_{i\notin S_q} |ei^q|
-\sum_{i\in S_p} |ei^p| - \sum_{i\in S_q} |ei^q|
=|e^p|_1 +|e^q|_1 -2*1_p'|e^p|_1 -2*1_q'|e^q|_1
\]
Thus C_s contains the restriction
\[ |e^p|_1 +|e^q|_1 -2*1_p'|e^p|_1 -2*1_q'|e^q|_1≤0 \] (4.16)
Denote
\[ C_s^1 = { e| e\neq 0, Ae=0, with (4.16) . \]

Now we turn to Ae=0. Notice that A=[P,Q], thus we have
\[ [P,Q]x=Pe^p +Qe^q=0 => \]
\[ e^p +P'Qe^q=0, and Q'P e^p +e^q=0 \] (4.17)
Thus
\[ |e^p|=|P'Qe^q|≤μ*I*|e^q|, |e^q|=|Q'pe^p|≤μ*I*|e^p|, \] (4.18)
and denote
\[ C_s^2 ={e| e\neq 0, with (4.16) and (4.18) } \] (4.19)