21.3. Orthogonal Matching Pursuit

In this section, we consider the application of Orthogonal Matching Pursuit (OMP) for the problem of recovering a signal from its compressive measurements. This section is largely based on [80].

Please review the notation of compressing sensing process from Definition 18.24.

We will restrict our attention to the $N$ dimensional Euclidean space as our signal space for the moment.

1. $\mathbf{x}\in {\mathbb{R}}^N$ is a signal vector.

2. $\mathrm{\Phi }\in {\mathbb{R}}^{M\times N}$ is the real sensing matrix with $M\ll N$.

3. The measurement vector $\mathbf{y}\in {\mathbb{R}}^M$ is given by

   $$\mathbf{y}=\mathrm{\Phi }\mathbf{x}$$

   where ${\mathbb{R}}^M$ is our measurement space.

4. $\mathbf{y}$ is known, $\mathrm{\Phi }$ is known while $\mathbf{x}$ is unknown to the recovery algorithm.

5. $\mathbf{x}$ is assumed to be either $K$-sparse or $K$-compressible.

The sparse recovery problem can be written as

(21.5)$$\begin{array}{rlrl}& \underset{x}{\text{minimize }}& & \Vert \mathbf{y}-\mathrm{\Phi }\mathbf{x}{\Vert }_2\\ & \text{subject to}& & \Vert \mathbf{x}{\Vert }_0\le K.\end{array}$$

Though the problem looks similar to $(\mathcal{D},K)$-SPARSE approximation problem, but there are differences since $\mathrm{\Phi }$ is not a dictionary (see Sensing Matrices). In particular, we don’t require each column to be unit norm.

We will adapt OMP algorithm studied in Orthogonal Matching Pursuit for the problem of sparse recovery in compressed sensing framework. In the analysis of OMP for CS We will address following questions:

• How many measurements are required to recover $\mathbf{x}$ from $\mathbf{y}$ exactly if $\mathbf{x}$ is $K$-sparse?

• What kind of sensing matrices are admissible for OMP to work in CS framework?

• If $\mathbf{x}$ is not $K$-sparse, then how much maximum error is incurred?

21.3.1. The Algorithm

OMP algorithm adapted to CS is presented in Algorithm 21.1.

Algorithm 21.1 (Orthogonal matching pursuit for sparse recovery from compressive measurements)

Inputs:

• Sensing matrix $\mathrm{\Phi }\in {\mathbb{R}}^{M\times N}$

• Measurement vector $\mathbf{y}\in {\mathbb{R}}^M$

• Desired sparsity level $K$

Outputs:

• A $K$-sparse estimate $\hat{\mathbf{x}}\in {\mathrm{\Sigma }}_K\subseteq {\mathbb{R}}^N$ for the ideal signal $\mathbf{x}$

• An index set ${\mathrm{\Lambda }}^K\subset \{1,\dots ,N\}$ identifying the support of $\hat{\mathbf{x}}$

• An approximation ${\mathbf{y}}^K\in {\mathbb{R}}^M$ of $\mathbf{y}$

• A residual ${\mathbf{r}}^K=\mathbf{y}-{\mathbf{y}}^K\in {\mathbb{R}}^M$

Initialization:

1. $k\leftarrow 0$ # Iteration counter

2. ${\mathbf{x}}^0\leftarrow \mathbf{0}$ # Initial Estimate of $\mathbf{x}\in {\mathbb{R}}^N$

3. ${\mathbf{y}}^0\leftarrow \mathrm{\Phi }{\mathbf{x}}^0=\mathbf{0}$ # Approximation of $\mathbf{y}$

4. ${\mathbf{r}}^0\leftarrow \mathbf{y}-{\mathbf{y}}^0=\mathbf{y}$ # Residual $\mathbf{r}\in {\mathbb{R}}^M$

5. ${\mathrm{\Lambda }}^0\leftarrow \varnothing$ # Solution support $\mathrm{\Lambda }=\mathrm{supp}(\hat{\mathbf{x}})$

Algorithm:

1. If $k==K$ or ${\mathbf{r}}^k==\mathbf{0}$: break.

2. Increase the iteration count

   $$k\leftarrow k+1.$$

3. Sweep (find column with largest inner product)

   $${\lambda }_k=\text{arg}\underset{1\le j\le N}{max}|⟨{\mathbf{r}}^{k-1},{\varphi }_j⟩|.$$

4. Update support

   $${\mathrm{\Lambda }}^k\leftarrow {\mathrm{\Lambda }}^{k-1}\cup \{{\lambda }_k\}.$$

5. Update provisional solution

   $${\mathbf{x}}^k\leftarrow \underset{\mathbf{x}}{\arg \min }\Vert \mathrm{\Phi }\mathbf{x}-\mathbf{y}{\Vert }_2^2$$

   subject to $\mathrm{supp}(\mathbf{x})={\mathrm{\Lambda }}^k$.

6. Update residual

   $$\begin{array}{rl}& {\mathbf{y}}^k\leftarrow \mathrm{\Phi }{\mathbf{x}}^k;\\ & {\mathbf{r}}^k\leftarrow \mathbf{y}-{\mathbf{y}}^k.\end{array}$$

7. Go to step 1.

Finalization:

• $\hat{\mathbf{x}}\leftarrow {\mathbf{x}}^k$.

Some remarks are in order

1. The algorithm returns a $K$-term approximation of $\mathbf{x}$ given by $\hat{\mathbf{x}}$.

2. Each step of algorithm is identified by the iteration counter $k$ which runs from 0 to $K$.

3. At each step ${\mathbf{x}}^k$, ${\mathbf{y}}^k$ and ${\mathbf{r}}^k$ are computed where ${\mathbf{x}}^k$ is the $k$-term estimate of $\mathbf{x}$, ${\mathbf{y}}^k$ is corresponding measurement vector and ${\mathbf{r}}^k$ is the residual between actual measurement vector $\mathbf{y}$ and the estimated measurement vector ${\mathbf{y}}^k$.

4. The support for $\hat{\mathbf{x}}$ is maintained in an index set $\mathrm{\Lambda }$.

5. At each iteration we add one more new index ${\lambda }_k$ to ${\mathrm{\Lambda }}^{k-1}$ giving us ${\mathrm{\Lambda }}^k$.

6. We will use ${\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}\in {\mathbb{R}}^{M\times k}$ to denote the submatrix constructed from the columns indexed by ${\mathrm{\Lambda }}^k$. In other words, if ${\mathrm{\Lambda }}^k=\{{\lambda }_1,\dots ,{\lambda }_k\}$, then

   $${\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}=\left[\begin{array}{ccc}{\varphi }_{{\lambda }_1}& \dots & {\varphi }_{{\lambda }_k}\end{array}\right].$$

7. Similarly we will denote a vector ${\mathbf{x}}_{{\mathrm{\Lambda }}^k}^k\in {\mathbb{R}}^k$ to denote a vector consisting of only $k$ non-zero entries in $\mathbf{x}$.

8. We note that ${\mathbf{r}}^k$ is orthogonal to ${\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}$. This is true due to ${\mathbf{x}}^k$ being the least squares solution in the update provisional solution step.

9. This also ensures that in each iteration a new column from $\mathrm{\Phi }$ indexed by ${\lambda }_k$ will be chosen. OMP will never choose the same column again.

10. In case $\mathbf{x}$ has a sparsity level less than $K$ then ${\mathbf{r}}^k$ will become zero in the middle. At that point we halt. There is no point going forward.

11. An equivalent formulation of the least squares step is

    $$\mathbf{z}\leftarrow \text{arg }\underset{\mathbf{v}\in {\mathbb{R}}^k}{min}\Vert {\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}\mathbf{v}-\mathbf{y}{\Vert }_2^2$$

    followed by

    $${\mathbf{x}}_{{\mathrm{\Lambda }}^k}^k\leftarrow \mathbf{z}.$$

12. We solve the least squares problem for columns of $\mathrm{\Phi }$ indexed by ${\mathrm{\Lambda }}^k$ and then assign the $k$ entries in the resultant $\mathbf{z}$ to the entries in ${\mathbf{x}}^k$ indexed by ${\mathrm{\Lambda }}^k$ while keeping other entries as 0.

13. Least squares can be accelerated by using ${\mathbf{x}}^{k-1}$ as the starting estimate of ${\mathbf{x}}^k$ and carrying out a descent like Richardson’s iteration from there.

21.3.2. Exact Recovery using OMP with Random Sensing Matrices

The objective of this subsection is to prove theoretically that OMP can recover sparse signals from a small set of random linear measurements. In this subsection we discuss the conditions on the random sensing matrix $\mathrm{\Phi }$ under which they are suitable for signal recovery through OMP.

Definition 21.1 (Admissible sensing matrix)

An admissible sensing matrix for $K$-sparse signals in ${\mathbb{R}}^M$ is an $M\times N$ random matrix $\mathrm{\Phi }$ with following properties.

• [M0] Independence: The columns of $\mathrm{\Phi }$ are stochastically independent.

• [M1] Normalization: $\mathbb{E}(\Vert {\varphi }_j{\Vert }_2^2)=1$ for $j=1,\dots ,N$.

• [M2] Joint correlation:

  • Let $\{{\mathbf{u}}_k\}$ be a sequence of $K$ vectors whose ${\ell }_2$ norms do not exceed one.

  • Let $\varphi$ be a column of $\mathrm{\Phi }$ that is independent from this sequence.

  • Then

    $$\mathbb{P}(\underset{k}{max}|⟨\varphi ,{\mathbf{u}}_k⟩|\le ϵ)\ge 1-2K\exp (-c{ϵ}^{2}M).$$

• [M3] Smallest singular value: Given any $M\times K$ ($K<M$) submatrix $\mathbf{Z}$ from $\mathrm{\Phi }$, the smallest ($K$-th largest) singular value ${\sigma }_{min}(\mathbf{Z})$ satisfies

  $$\mathbb{P}({\sigma }_{min}(\mathbf{Z})\ge 0.5)\ge 1-\exp (-cM).$$

$c>0$ is some positive constant.

It can be shown Rademacher sensing matrices (Rademacher Sensing Matrices) and Gaussian sensing matrices (Gaussian Sensing Matrices) satisfy all the requirements of admissible sensing matrices for sparse recovery using OMP. Some of the proofs are included in the book. You may want to review corresponding sections.

Some remarks are in order to further explain the definition of admissible sensing matrices.

1. Typically all the columns of a sensing matrix are drawn from the same distribution. But (M0) doesn’t require so. It allows different columns of $\mathrm{\Phi }$ to be drawn from different distributions.

2. The joint correlation property (M2) depends on the decay of random variables $\Vert {\varphi }_j{\Vert }_2$. i.e. it needs the tails of $\Vert {\varphi }_j{\Vert }_2$ to be small.

3. A bound on the smallest (non-zero) singular value of $M\times K$-sub-matrices (M3) controls how much the sensing matrix can shrink $K$-sparse vectors.

4. I guess that the idea of admissible matrices came as follows. First OMP signal recovery guarantees were developed for Gaussian and Rademacher sensing matrices. Then the proofs were analyzed to identify the minimum requirements they imposed on the structure of random sensing matrices. This was extracted in the form of notion of admissible matrices. Finally the proof was reorganized to work for all random matrices which satisfy the admissibility criteria. It is important to understand this process of abstraction otherwise we just get surprised as to how the ideas like admissible matrices came out of the blue.

21.3.3. Signal Recovery Guarantees with OMP

We now show that OMP can be used to recover the original signal with high probability if the random measurements are taken using an admissible sensing matrix as described above.

Here we consider the case where $\mathbf{x}$ is known to be $K$-sparse.

Theorem 21.2

Fix some $\delta \in (0,1)$, and choose $M\ge CK\ln \left(\frac{N}{\delta }\right)$ where $C$ is an absolute constant. Suppose that $\mathbf{x}$ is an arbitrary $K$-sparse signal in ${\mathbb{R}}^N$ and draw an $M\times N$ admissible sensing matrix $\mathrm{\Phi }$ independent from $\mathbf{x}$.

Given the measurement vector $\mathbf{y}=\mathrm{\Phi }\mathbf{x}\in {\mathbb{R}}^M$, Orthogonal Matching Pursuit can reconstruct the signal with probability exceeding $1-\delta$.

Some remarks are in order. Specifically we compare OMP here with basis pursuit (BP).

1. The theorem provides probabilistic guarantees.

2. The theorem actually requires more measurements than the results for BP.

3. The biggest advantage is that OMP is a much simpler algorithm than BP and works very fast.

4. Results for BP show that a single random sensing matrix can be used for recovering all sparse signals.

5. This theorem says that any sparse signal independent from the sensing matrix can be recovered.

6. Thus this theorem is weaker than the results for BP. It can be argued that for practical situations, this limitation doesn’t matter much.

Proof. The main challenge here is to handle the issues that arise due to random nature of $\mathrm{\Phi }$. We start with setting up some notation for this proof.

1. We note that the columns that OMP chooses do not depend on the order in which they are stacked in $\mathrm{\Phi }$.

2. Thus without loss of generality we can assume that the first $K$ entries of $\mathbf{x}$ are non-zero and rest are zero.

3. If OMP picks up the first $K$ columns, then OMP has succeeded otherwise it has failed.

4. With this, support of $\mathbf{x}$ given by ${\mathrm{\Lambda }}_{\mathrm{opt}}=\{1,\dots ,K\}$.

We now partition the sensing matrix $\mathrm{\Phi }$ as

$$\mathrm{\Phi }=\left[\begin{array}{ccc}{\mathrm{\Phi }}_{\mathrm{opt}}& |& \mathrm{\Psi }\end{array}\right]$$

where ${\mathrm{\Phi }}_{\mathrm{opt}}$ consists of first $K$ columns of $\mathrm{\Phi }$ which correspond to ${\mathrm{\Lambda }}_{\mathrm{opt}}$. $\mathrm{\Psi }$ consists of remaining $(N-K)$ columns of $\mathrm{\Phi }$.

We recall from the proof of Theorem 20.17 that in order for OMP to make absolute progress at step $k+1$ we require the greedy selection ratio $\rho ({\mathbf{r}}^k)<1$ where

$$\rho ({\mathbf{r}}^k)=\frac{\Vert {\mathrm{\Psi }}^H{\mathbf{r}}^k{\Vert }_{\mathrm{\infty }}}{\Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H{\mathbf{r}}^k{\Vert }_{\mathrm{\infty }}}=\frac{\underset{\psi \in \mathrm{\Psi }}{max}|⟨\psi ,{\mathbf{r}}^k⟩|}{\Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H{\mathbf{r}}^k{\Vert }_{\mathrm{\infty }}}.$$

The proof is organized as follows:

1. We first construct a thought experiment in which $\mathrm{\Psi }$ is not present and OMP is run only with $\mathbf{y}$ and ${\mathrm{\Phi }}_{\mathrm{opt}}$.

2. We then run OMP with $\mathrm{\Psi }$ present under the condition $\rho ({\mathbf{r}}^k)<1$.

3. We show that the sequence of columns chosen and residual obtained in both cases is exactly the same.

4. We show that the residuals obtained in the thought experiment are stochastically independent from the columns of $\mathrm{\Psi }$.

5. We then describe the success of OMP as an event in terms of these residuals.

6. We compute a lower bound on the probability of the event of OMP success.

For a moment suppose that there was no $\mathrm{\Psi }$ and OMP is run with $\mathbf{y}$ and ${\mathrm{\Phi }}_{\mathrm{opt}}$ as input for $K$ iterations. Naturally OMP will choose $K$ columns in ${\mathrm{\Phi }}_{\mathrm{opt}}$ one by one.

1. Let the columns it picks up in each step be indexed by ${\omega }_1,{\omega }_2,\dots ,{\omega }_K$.

2. Let the residuals before each step be ${\mathbf{q}}^0,{\mathbf{q}}^1,{\mathbf{q}}^2,\dots ,{\mathbf{q}}^{K-1}$.

3. Since $\mathbf{x}\in \mathcal{C}({\mathrm{\Phi }}_{\mathrm{opt}})$, hence the residual after $K$ iterations ${\mathbf{q}}^K=\mathbf{0}$.

4. Since OMP is a deterministic algorithm, hence the two sequences are simply functions of $\mathbf{x}$ and ${\mathrm{\Phi }}_{\mathrm{opt}}$.

5. Clearly, we can say that the residual ${\mathbf{q}}^k$ are stochastically independent of the columns in $\mathrm{\Psi }$ (since columns of $\mathrm{\Psi }$ are independent of the columns of ${\mathrm{\Phi }}_{\mathrm{opt}}$).

6. We also know that ${\mathbf{q}}^k\in \mathcal{C}({\mathrm{\Phi }}_{\mathrm{opt}})$.

In this thought experiment we made no assumptions about $\rho ({\mathbf{q}}^k)$ since $\mathrm{\Psi }$ is not present. We now consider the full matrix $\mathrm{\Phi }$ and execute OMP with $\mathbf{y}$.

1. The actual sequence of residuals before each step is ${\mathbf{r}}^0,{\mathbf{r}}^1,\dots ,{\mathbf{r}}^{K-1}$.

2. The actual sequence of column indices is ${\lambda }_1,\dots ,{\lambda }_K$.

3. OMP succeeds in recovering $\mathbf{x}$ in $K$ steps if and only if it selects the first $K$ columns of $\mathrm{\Phi }$ in some order.

4. This can happen if and only if $\rho ({\mathbf{r}}^k)<1$ holds.

5. We are going to show inductively that this can happen if and only if ${\lambda }_k={\omega }_k$ and ${\mathbf{q}}^k={\mathbf{r}}^k$.

6. At the beginning of step 1, we have ${\mathbf{r}}^0={\mathbf{q}}^0=\mathbf{y}$.

7. Now OMP selects one column from ${\mathrm{\Phi }}_{\mathrm{opt}}$ if and only if $\rho ({\mathbf{r}}^0)<1$ which is identical to $\rho ({\mathbf{q}}^0)<1$.

8. So it remains to show at step 1 that ${\lambda }_1={\omega }_1$.

9. Because $\rho ({\mathbf{r}}^0)<1$, the algorithm selects the index ${\lambda }_1$ of the column from ${\mathrm{\Phi }}_{\mathrm{opt}}$ whose inner product with ${\mathbf{r}}^0$ is the largest (in absolute value).

10. Also since $\rho ({\mathbf{q}}^0)<1$ with ${\mathbf{r}}^0={\mathbf{q}}^0$, ${\omega }_1$ is the index of column in ${\mathrm{\Phi }}_{\mathrm{opt}}$ whose inner product with ${\mathbf{q}}^0$ is largest.

11. Thus ${\omega }_1={\lambda }_1$.

12. We now assume that for the first $k$ iterations, real OMP chooses the same columns as our imaginary thought experiment.

13. Thus we have

    $${\lambda }_j={\omega }_j\mathrm{\forall }1\le j\le k$$

    and

    $${\mathbf{r}}^j={\mathbf{q}}^j\mathrm{\forall }0\le j\le k.$$

    This is valid since the residuals at each step depend solely on the set of columns chosen so far and input $\mathbf{y}$ which are same for both cases.

14. OMP chooses a column in ${\mathrm{\Phi }}_{\mathrm{opt}}$ at $(k+1)$-th step if and only if $\rho ({\mathbf{r}}^k)<1$ which is same as $\rho ({\mathbf{q}}^k)<1$.

15. Moreover since ${\mathbf{r}}^k={\mathbf{q}}^k$ hence the column chosen by maximizing the inner product is same for both situations.

16. Thus

    $${\lambda }_{k+1}={\omega }_{k+1}.$$

17. Therefore the criteria for success of OMP can be stated as $\rho ({\mathbf{q}}^k)<1$ for all $0\le k\le K-1$.

We now recall that ${\mathbf{q}}^k$ is actually a random variable (depending upon the random vectors which comprise the columns of ${\mathrm{\Phi }}_{\mathrm{opt}}$).

1. Thus the event on which the algorithm succeeds in sparse recovery of $\mathbf{x}$ from $\mathbf{y}$ is given by

   $$E_{\mathrm{succ}}\triangleq \{\underset{0\le k<K}{max}\rho ({\mathbf{q}}^k)<1\}.$$

2. In a particular instance of OMP execution if the event $E_{\mathrm{succ}}$ happens, then OMP successfully recovers $\mathbf{x}$ from $\mathbf{y}$.

3. Otherwise OMP fails.

4. Hence the probability of success of OMP is same as the probability of event $E_{\mathrm{succ}}$.

5. We will be looking for some sort of a lower bound on $\mathbb{P}(E_{\mathrm{succ}})$.

6. We note that we have $\{{\mathbf{q}}^k\}$ as a sequence of random vectors in the column span of ${\mathrm{\Phi }}_{\mathrm{opt}}$ and they are stochastically independent from columns of $\mathrm{\Psi }$.

7. It is difficult to compute $\mathbb{P}(E_{\mathrm{succ}})$ directly.

8. We consider another event

   $$\mathrm{\Gamma }=\{{\sigma }_{min}({\mathrm{\Phi }}_{\mathrm{opt}})\ge 0.5\}.$$

9. Clearly

   $$\mathbb{P}(E_{\mathrm{succ}})\ge \mathbb{P}(\underset{0\le k<K}{max}\rho ({\mathbf{q}}^k)<1\text{ and }\mathrm{\Gamma }).$$

10. Using conditional probability we can rewrite

    $$\mathbb{P}(E_{\mathrm{succ}})\ge \mathbb{P}(\underset{0\le k<K}{max}\rho ({\mathbf{q}}^k)<1|\mathrm{\Gamma })\mathbb{P}(\mathrm{\Gamma }).$$

11. Since $\mathrm{\Phi }$ is an admissible matrix hence it satisfies (M3) which gives us

    $$\mathbb{P}(\mathrm{\Gamma })\ge 1-\exp (-cM).$$

12. We just need a lower bound on the conditional probability.

13. We assume that $\mathrm{\Gamma }$ occurs.

14. For each step index $k=0,1,\dots ,K-1$, we have

    $$\rho ({\mathbf{q}}^k)=\frac{\underset{\psi }{max}|⟨\psi ,{\mathbf{q}}^k⟩|}{\Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H{\mathbf{q}}^k{\Vert }_{\mathrm{\infty }}}.$$

15. Since ${\mathrm{\Phi }}_{\mathrm{opt}}^H{\mathbf{q}}^k\in {\mathbb{R}}^K$, we have

    $$\sqrt{K}\Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H{\mathbf{q}}^k{\Vert }_{\mathrm{\infty }}\ge \Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H{\mathbf{q}}^k{\Vert }_2.$$

16. This gives us

    $$\rho ({\mathbf{q}}^k)\le \frac{\sqrt{K}\underset{\psi }{max}|⟨\psi ,{\mathbf{q}}^k⟩|}{\Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H{\mathbf{q}}^k{\Vert }_2}.$$

17. To simplify this expression, we define a vector

    $${\mathbf{u}}^k\triangleq \frac{0.5{\mathbf{q}}^k}{\Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H{\mathbf{q}}^k{\Vert }_2}.$$

18. This lets us write

    $$\rho ({\mathbf{q}}^k)\le 2\sqrt{K}\underset{\psi }{max}|⟨\psi ,{\mathbf{u}}^k⟩|.$$

19. Thus

    $$\mathbb{P}(\rho ({\mathbf{q}}^k)<1|\mathrm{\Gamma })\ge \mathbb{P}(2\sqrt{K}\underset{\psi }{max}|⟨\psi ,{\mathbf{u}}^k⟩|<1|\mathrm{\Gamma })=\mathbb{P}(\underset{\psi }{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}|\mathrm{\Gamma }).$$

20. From the basic properties of singular values we recall that

    $$\frac{\Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H\mathbf{q}{\Vert }_2}{\Vert \mathbf{q}{\Vert }_2}\ge {\sigma }_{min}({\mathrm{\Phi }}_{\mathrm{opt}})\ge 0.5$$

    for all vectors $\mathbf{q}$ in the range of ${\mathrm{\Phi }}_{\mathrm{opt}}$.

21. This gives us

    $$\frac{0.5\Vert \mathbf{q}{\Vert }_2}{\Vert {\mathrm{\Phi }}_{\mathrm{opt}}^H\mathbf{q}{\Vert }_2}\le 1.$$

22. Since ${\mathbf{q}}^k$ is in the column space of ${\mathrm{\Phi }}_{\mathrm{opt}}$, for ${\mathbf{u}}^k$ defined above we have

    $$\Vert {\mathbf{u}}^k{\Vert }_2\le 1.$$

    This is valid under the assumption that the event $\mathrm{\Gamma }$ has happened.

23. From the above we get

    $$\mathbb{P}(\underset{k}{max}\rho ({\mathbf{q}}^k)<1|\mathrm{\Gamma })\ge \mathbb{P}(\underset{k}{max}\underset{\psi }{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}|\mathrm{\Gamma })$$

24. In the R.H.S. we can exchange the order of two maxima. This gives us

    $$\mathbb{P}(\underset{k}{max}\underset{\psi }{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}|\mathrm{\Gamma })=\mathbb{P}(\underset{\psi }{max}\underset{k}{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}|\mathrm{\Gamma }).$$

25. We also note that columns of $\mathrm{\Psi }$ are independent.

26. Thus in above we require that for each column of $\mathrm{\Psi }$ $\underset{k}{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}$ should hold independently.

27. Hence we can say

    $$\mathbb{P}(\underset{\psi }{max}\underset{k}{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}|\mathrm{\Gamma })=\prod _{\psi }\mathbb{P}(\underset{k}{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}|\mathrm{\Gamma }).$$

28. We recall that event $\mathrm{\Gamma }$ depends only on columns of ${\mathrm{\Phi }}_{\mathrm{opt}}$.

29. Hence columns of $\mathrm{\Psi }$ are independent of $\mathrm{\Gamma }$.

30. Thus

    $$\prod _{\psi }\mathbb{P}(\underset{k}{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}|\mathrm{\Gamma })=\prod _{\psi }\mathbb{P}(\underset{k}{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}}).$$

31. Since the sequence $\{{\mathbf{u}}^k\}$ depends only on columns of ${\mathrm{\Phi }}_{\mathrm{opt}}$, hence columns of $\mathrm{\Psi }$ are independent of $\{{\mathbf{u}}^k\}$.

32. Thus we can take help of (M2) to get

    $$\prod _{\psi }\mathbb{P}(\underset{k}{max}|⟨\psi ,{\mathbf{u}}^k⟩|<\frac{1}{2\sqrt{K}})\ge {(1-2K\exp (-\frac{cM}{4K}))}^{N-K}.$$

33. This gives us the lower bound

    $$\mathbb{P}(\underset{k}{max}\rho ({\mathbf{q}}^k)<1|\mathrm{\Gamma })\ge {(1-2K\exp (-\frac{cM}{4K}))}^{N-K}.$$

34. Finally plugging in the lower bound for $\mathbb{P}(\mathrm{\Gamma })$ we get

    (21.6)$$\mathbb{P}(E_{\mathrm{succ}})\ge {(1-2K\exp (-\frac{cM}{4K}))}^{N-K}(1-\exp (-cM)).$$

    All that is remaining now is to simplify this expression.

35. We recall that we assumed in the theorem statement

    $$\begin{array}{rl}& M\ge CK\ln \left(\frac{N}{\delta }\right)\\ ⟹& \frac{M}{CK}\ge \ln \left(\frac{N}{\delta }\right)\\ ⟹& \exp \left(\frac{M}{CK}\right)\ge \frac{N}{\delta }\\ ⟹& \frac{\delta }{N}\ge \exp (-\frac{M}{CK})\\ ⟹& \delta \ge N\exp (-\frac{M}{CK}).\end{array}$$

36. But we assumed that $0<\delta <1$.

37. Thus

    $$N\exp (-\frac{M}{CK})<1.$$

38. If we choose $C\ge \frac{4}{c}$ then

    (21.7)$$\begin{array}{rl}& -\frac{1}{C}\ge -\frac{c}{4}\\ ⟹& -\frac{M}{CK}\ge -\frac{cM}{4K}\\ ⟹& \exp (-\frac{M}{CK})\ge \exp (-\frac{cM}{4K})\\ ⟹& N\exp (-\frac{M}{CK})\ge 2K\exp (-\frac{cM}{4K})\\ ⟹& 1>\delta \ge 2K\exp (-\frac{cM}{4K})\end{array}$$

    where we assumed that $N\gg 2K$.

39. We recall that

    $$(1-x{)}^k\ge 1-kx\text{ if }k\ge 1\text{ and }x\le 1.$$

40. Applying on (21.6) we get

    (21.8)$$\mathbb{P}(E_{\mathrm{succ}})\ge 1-2K(N-K)\exp (-\frac{cM}{4K})-\exp (-cM).$$

    We ignored the 4-th term in this expansion.

41. Now we can safely assume that $K(N-K)\ge \frac{N^2}{4}$ giving us

    $$\mathbb{P}(E_{\mathrm{succ}})\ge 1-\frac{N^2}{2}\exp (-\frac{cM}{4K})-\exp (-cM).$$

42. If we choose $C\ge \frac{8}{c}$ then following (21.7) we can get

    $$\begin{array}{rl}& N\exp (-\frac{M}{CK})\ge N\exp (-\frac{cM}{8K})\\ ⟹& \delta \ge N\exp (-\frac{cM}{8K})\\ ⟹& {\delta }^2\ge N^2\exp (-\frac{cM}{4K})\\ ⟹& 1-\frac{{\delta }^2}{2}\le 1-\frac{N^2}{2}\exp (-\frac{cM}{4K}).\end{array}$$

43. Thus

    $$\mathbb{P}(E_{\mathrm{succ}})\ge 1-\frac{{\delta }^2}{2}-\exp (-cM).$$

44. Some further simplification can give us

    $$\mathbb{P}(E_{\mathrm{succ}})\ge 1-\delta .$$

45. Thus with a suitable choice of the constant $C$, a choice of $M\ge CK\ln \left(\frac{N}{\delta }\right)$ with $\delta \in (0,1)$ is sufficient to reduce the failure probability below $\delta$.

21.3.4. Analysis of OMP using Restricted Isometry Property

In this subsection we present an alternative analysis of OMP algorithm using the Restricted Isometry Property of the matrix $\mathrm{\Phi }$ [25].

21.3.4.1. A re-look at the OMP Algorithm

Before we get into the RIP based analysis of OMP, it would be useful to get some new insights into the behavior of OMP algorithm. These insights will help us a lot in performing the analysis later.

1. We will assume throughout that whenever $|\mathrm{\Lambda }|\le K$, then ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$ is full rank.

2. The pseudo-inverse is given by

   $${\mathrm{\Phi }}_{\mathrm{\Lambda }}^{†}={\left({\mathrm{\Phi }}_{\mathrm{\Lambda }}^H{\mathrm{\Phi }}_{\mathrm{\Lambda }}\right)}^{-1}{\mathrm{\Phi }}_{\mathrm{\Lambda }}^H.$$

3. The orthogonal projection operator to the column space for ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$ is given by

   $${\mathbf{P}}_{\mathrm{\Lambda }}={\mathrm{\Phi }}_{\mathrm{\Lambda }}{\mathrm{\Phi }}_{\mathrm{\Lambda }}^{†}.$$

4. The orthogonal projection operator onto the orthogonal complement of $\mathcal{C}({\mathrm{\Phi }}_{\mathrm{\Lambda }})$ (column space of ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$) is given by

   $${\mathbf{P}}_{\mathrm{\Lambda }}^{\perp }=\mathbf{I}-{\mathbf{P}}_{\mathrm{\Lambda }}.$$

5. Both ${\mathbf{P}}_{\mathrm{\Lambda }}$ and ${\mathbf{P}}_{\mathrm{\Lambda }}^{\perp }$ satisfy the standard properties like $\mathbf{P}={\mathbf{P}}^H$ and ${\mathbf{P}}^2=\mathbf{P}$.

6. We further define

   $${\mathrm{\Psi }}_{\mathrm{\Lambda }}={\mathbf{P}}_{\mathrm{\Lambda }}^{\perp }\mathrm{\Phi }.$$

7. We are orthogonalizing the atoms in $\mathrm{\Phi }$ against $\mathcal{C}({\mathrm{\Phi }}_{\mathrm{\Lambda }})$, i.e. taking the component of the atom which is orthogonal to the column space of ${\mathrm{\Phi }}_{\mathrm{\Lambda }}$.

8. The atoms in ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ corresponding to the index set $\mathrm{\Lambda }$ would be $\mathbf{0}$.

9. We will make some further observations on the behavior of OMP algorithm [25].

10. Recall that the approximation after the $k$-th iteration is given by

    $${\mathbf{x}}_{{\mathrm{\Lambda }}^k}^k={\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}^{†}\mathbf{y}\text{ and }{\mathbf{x}}_{{{\mathrm{\Lambda }}^k}^c}^k=\mathbf{0}.$$

11. The residual after $k$-th iteration is given by

    $${\mathbf{r}}^k=\mathbf{y}-\mathrm{\Phi }{\mathbf{x}}^k$$

    and by construction ${\mathbf{r}}^k$ is orthogonal to ${\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}$.

12. We can write

    $$\mathrm{\Phi }{\mathbf{x}}^k={\mathrm{\Phi }}_{\mathrm{\Lambda }}{\mathbf{x}}_{{\mathrm{\Lambda }}^k}^k+{\mathrm{\Phi }}_{{{\mathrm{\Lambda }}^k}^c}{\mathbf{x}}_{{\mathrm{\Lambda }}^c}^k={\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}{\mathbf{x}}_{{\mathrm{\Lambda }}^k}^k.$$

13. Thus,

    $$\begin{array}{rl}{\mathbf{r}}^k& =\mathbf{y}-{\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}{\mathbf{x}}_{{\mathrm{\Lambda }}^k}^k\\ & =\mathbf{y}-{\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}{\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}^{†}\mathbf{y}\\ & =(\mathbf{I}-{\mathbf{P}}_{{\mathrm{\Lambda }}^k})\mathbf{y}={\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}.\end{array}$$

14. In summary

    $${\mathbf{r}}^k={\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}.$$

15. This shows that it is not actually necessary to compute ${\mathbf{x}}^k$ in order to find ${\mathbf{r}}^k$. An equivalent way of writing OMP algorithm could be as in Algorithm 21.2.

Algorithm 21.2 (Sketch of OMP without intermediate ${\mathbf{x}}^k$ computation)

Algorithm:

1. If halting criteria is satisfied, then break.

2. ${\mathbf{h}}^{k+1}\leftarrow {\mathrm{\Phi }}^H{\mathbf{r}}^k$ # Match

3. ${\lambda }^{k+1}\leftarrow \underset{j\notin {\mathrm{\Lambda }}^k}{\text{arg}max}|{\mathbf{h}}_j^{k+1}|$ # Identify

4. ${\mathrm{\Lambda }}^{k+1}\leftarrow {\mathrm{\Lambda }}^k\cup \{{\lambda }^{k+1}\}$ # Update support

5. ${\mathbf{r}}^{k+1}\leftarrow {\mathbf{P}}_{{\mathrm{\Lambda }}^{k+1}}^{\perp }\mathbf{y}$ # Update residual

6. $k\leftarrow k+1$.

7. Go back to step 1.

Finalization:

1. ${\hat{\mathbf{x}}}_{{\mathrm{\Lambda }}^k}\leftarrow {\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}^{†}\mathbf{y}$.

2. ${\hat{\mathbf{x}}}_{{{\mathrm{\Lambda }}^k}^c}\leftarrow \mathbf{0}$.

1. In the matching step, we are correlating ${\mathbf{r}}^k$ with columns of $\mathrm{\Phi }$.

2. Since ${\mathbf{r}}^k$ is orthogonal to column space of ${\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}$, hence this correlation is identical to correlating ${\mathbf{r}}^k$ with ${\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}$.

3. To see this, observe that

   $${\mathbf{r}}^k={\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}={\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }{\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}=({\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }{)}^H{\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}.$$

4. Thus,

   $$\begin{array}{rl}{\mathbf{h}}^{k+1}& ={\mathrm{\Phi }}^H{\mathbf{r}}^k\\ & ={\mathrm{\Phi }}^H({\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }{)}^H{\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}\\ & ={\left({\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathrm{\Phi }\right)}^H{\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}\\ & ={\left({\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}\right)}^H{\mathbf{r}}^k.\end{array}$$

5. On similar lines, we can also see that

   $${\mathbf{h}}^{k+1}={\mathrm{\Phi }}^H{\mathbf{r}}^k={\mathrm{\Phi }}^H{\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}={\mathrm{\Phi }}^H{\left({\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\right)}^H\mathbf{y}={\left({\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}\right)}^H\mathbf{y}.$$

6. In other words, we have

   (21.9)$${\mathbf{h}}^{k+1}={\left({\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}\right)}^H{\mathbf{r}}^k={\left({\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}\right)}^H\mathbf{y}.$$

7. Thus, we can observe that OMP can be further simplified and we don’t even need to compute ${\mathbf{r}}^k$ in order to compute ${\mathbf{h}}^{k+1}$.

8. There is one catch though. If the halting criterion depends on the need to compute the residual energy, then we certainly need to compute ${\mathbf{r}}^k$. If the halting criteria is simply the number of $K$ iterations, then we don’t need to compute ${\mathbf{r}}^k$.

9. The revised OMP algorithm sketch is presented in Algorithm 21.3.

Algorithm 21.3 (Sketch of OMP without intermediate ${\mathbf{x}}^k$ computation)

Algorithm:

1. If halting criteria is satisfied, then break.

2. ${\mathbf{h}}^{k+1}\leftarrow {\left({\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}\right)}^H\mathbf{y}$ # Match

3. ${\lambda }^{k+1}\leftarrow \underset{i\notin {\mathrm{\Lambda }}^k}{\text{arg}max}|{\mathbf{h}}_i^{k+1}|$ # Identify

4. ${\mathrm{\Lambda }}^{k+1}\leftarrow {\mathrm{\Lambda }}^k\cup \{{\lambda }^{k+1}\}$ # Update support

5. $k\leftarrow k+1$

6. Go back to step 1.

Finalization:

1. ${\hat{\mathbf{x}}}_{{\mathrm{\Lambda }}^k}\leftarrow {\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}^{†}\mathbf{y}$.

2. ${\hat{\mathbf{x}}}_{{{\mathrm{\Lambda }}^k}^c}\leftarrow \mathbf{0}$.

With this the OMP algorithm is considerably simplified from the perspective of analyzing its recovery guarantees.

1. Coming back to ${\mathbf{h}}^{k+1}$, note that the columns of ${\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}$ indexed by ${\mathrm{\Lambda }}^k$ are all $\mathbf{0}$s.

2. Thus

   $$h_j^{k+1}=\mathbf{0}\mathrm{\forall }j\in {\mathrm{\Lambda }}^k.$$

3. This makes it obvious that ${\lambda }^{k+1}\notin \mathrm{\Lambda }$ and consequently $|{\mathrm{\Lambda }}^k|=k$ (inductively).

4. Lastly for the case of noise free model $\mathbf{y}=\mathrm{\Phi }\mathbf{x}$, we may write

   $${\mathbf{r}}^k={\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathbf{y}={\mathbf{P}}_{{\mathrm{\Lambda }}^k}^{\perp }\mathrm{\Phi }\mathbf{x}={\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}\mathbf{x}.$$

5. Since columns of ${\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}$ indexed by ${\mathrm{\Lambda }}^k$ are $\mathbf{0}$, hence when $\mathrm{supp}(\mathbf{x})\subseteq {\mathrm{\Lambda }}^k$, then ${\mathbf{r}}^k=\mathbf{0}$.

6. In this case ${\mathbf{x}}^k=\mathbf{x}$ exactly since it is a least squares estimate over ${\mathrm{\Phi }}_{{\mathrm{\Lambda }}^k}$.

7. For the same reason, if we construct a vector ${\tilde{\mathbf{x}}}^k$ by zeroing out the entries indexed by ${\mathrm{\Lambda }}^k$ i.e.

   (21.10)$${\tilde{\mathbf{x}}}_{{\mathrm{\Lambda }}^k}^k=0\text{ and }{\tilde{\mathbf{x}}}_{{{\mathrm{\Lambda }}^k}^c}={\mathbf{x}}_{{{\mathrm{\Lambda }}^k}^c}$$

   then

   (21.11)$${\mathbf{r}}^k={\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}{\tilde{\mathbf{x}}}^k.$$

8. If $\Vert \mathbf{x}{\Vert }_0=K$, then $\Vert {\tilde{\mathbf{x}}}^k{\Vert }_0=K-k$.

9. Lastly putting ${\mathbf{r}}^k$ back in (21.9), we obtain

   (21.12)$${\mathbf{h}}^{k+1}={\left({\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}\right)}^H{\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}{\tilde{\mathbf{x}}}^k.$$

10. In this version, we see that ${\mathbf{h}}^{k+1}$ is computed by applying the matrix ${\left({\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}\right)}^H{\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}$ to the $(K-k)$ sparse vector ${\tilde{\mathbf{x}}}^k$.

11. We are now ready to carry out RIP based analysis of OMP.

21.3.4.2. RIP based Analysis of OMP

Our analysis here will focus on the case for real signals and real matrices i.e. $\mathrm{\Phi }\in {\mathbb{R}}^{M\times N}$ and $\mathbf{x}\in {\mathbb{R}}^N$. We will attack the noise free case.

Some results for matrices that satisfy RIP will be useful in the upcoming analysis. Please refer to Restricted Isometry Property for an extensive treatment of RIP based results.

Theorem 18.64 applies to approximate preservation of the inner product of sparse signals $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^N$.

Let $\mathbf{u},\mathbf{v}\in {\mathbb{R}}^N$ and $K\ge max(\Vert \mathbf{u}+\mathbf{v}{\Vert }_0,\Vert \mathbf{u}-\mathbf{v}{\Vert }_0)$. Then

(21.13)$$|⟨\mathrm{\Phi }\mathbf{u},\mathrm{\Phi }\mathbf{v}⟩-⟨\mathbf{u},\mathbf{v}⟩|\le {\delta }_K\Vert \mathbf{u}{\Vert }_2\Vert \mathbf{v}{\Vert }_2.$$

Theorem 18.66 shows that the matrix ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ also satisfies a modified version of RIP. Let $|\mathrm{\Lambda }|<K$. Then

(21.14)$$(1-\frac{{\delta }_K}{1-{\delta }_K})\Vert \mathbf{y}{\Vert }_2^2\le \Vert {\mathrm{\Psi }}_{\mathrm{\Lambda }}\mathbf{y}{\Vert }_2^2\le (1+{\delta }_K)\Vert \mathbf{y}{\Vert }_2^2$$

whenever $\Vert \mathbf{y}{\Vert }_0\le K-|\mathrm{\Lambda }|$ and $\mathrm{supp}(\mathbf{y})\cap \mathrm{\Lambda }=\varnothing$.

If $\mathrm{\Phi }$ satisfies RIP of order $K$, then ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ acts as an approximate isometry on every $(K-|\mathrm{\Lambda }|)$-sparse vector supported on ${\mathrm{\Lambda }}^c$.

From (21.11) recall that the residual vector ${\mathbf{r}}^k$ is formed by applying ${\mathrm{\Psi }}_{{\mathrm{\Lambda }}^k}$ to ${\tilde{\mathbf{x}}}^k$ which is a $K-k$ sparse vector supported on ${{\mathrm{\Lambda }}^k}^c$.

Our interest is in combining above two results and get some bound on the inner products ${\mathbf{h}}_j^{k+1}$. Exactly what kind of bound? When ${\mathrm{\Lambda }}^k$ has been identified, our interest is in ensuring that the next index is chosen from the set $\mathrm{supp}(\mathbf{x})\setminus {\mathrm{\Lambda }}^k$. A useful way to ensure this would be to verify if the entries in ${\mathbf{h}}^{k+1}$ are close to ${\tilde{\mathbf{x}}}^k$. If they are, then they would be 0 over ${\mathrm{\Lambda }}^k$ , they would be pretty high over $\mathrm{supp}(\mathbf{x})\setminus {\mathrm{\Lambda }}^k$ and lastly, very small over $\mathrm{supp}(\mathbf{x}{)}^c$ which is what we want.

The next result develops these bounds around (21.12).

Lemma 21.1

Let $\mathrm{\Lambda }\subset \{1,\dots ,N\}$ and suppose $\tilde{\mathbf{x}}\in {\mathbb{R}}^N$ with $\mathrm{supp}(\tilde{\mathbf{x}})\cap \mathrm{\Lambda }=\varnothing$. Define

(21.15)$$\mathbf{h}={\mathrm{\Psi }}_{\mathrm{\Lambda }}^T{\mathrm{\Psi }}_{\mathrm{\Lambda }}\tilde{\mathbf{x}}.$$

Then if $\mathrm{\Phi }$ satisfies the RIP of order $K\ge \Vert \tilde{\mathbf{x}}{\Vert }_0+|\mathrm{\Lambda }|+1$ with isometry constant ${\delta }_K$, we have

(21.16)$$|h_j-{\tilde{x}}_j|\le \frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2\mathrm{\forall }j\notin \mathrm{\Lambda }.$$

Note that $|\mathrm{\Lambda }|$ is the number of entries in the the discovered part of the support at any iteration in OMP and $\Vert \tilde{\mathbf{x}}{\Vert }_0$ is the number of entries in not yet discovered part of the support.

Proof. .

1. We have $|\mathrm{\Lambda }|<K$ and $\Vert \tilde{\mathbf{x}}{\Vert }_0<K-|\mathrm{\Lambda }|$.

2. Thus, from (21.14), we obtain

   $$(1-\frac{{\delta }_K}{1-{\delta }_K})\Vert \tilde{\mathbf{x}}{\Vert }_2^2\le \Vert {\mathrm{\Psi }}_{\mathrm{\Lambda }}\tilde{\mathbf{x}}{\Vert }_2^2\le (1+{\delta }_K)\Vert \tilde{\mathbf{x}}{\Vert }_2^2.$$

3. We can make a statement saying ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ satisfies a RIP of order

   $$(\Vert \tilde{\mathbf{x}}{\Vert }_0+|\mathrm{\Lambda }|+1)-|\mathrm{\Lambda }|=\Vert \tilde{\mathbf{x}}{\Vert }_0+1$$

   with a RIP constant $\frac{{\delta }_K}{1-{\delta }_K}$.

4. By the definition of $\mathbf{h}$, we have

   $$h_j=⟨{\mathrm{\Psi }}_{\mathrm{\Lambda }}\tilde{\mathbf{x}},{\mathrm{\Psi }}_{\mathrm{\Lambda }}{\mathbf{e}}_j⟩$$

   where $h_j$ is the $j$-th entry in $\mathbf{h}$ and ${\mathbf{e}}_j$ denotes the $j$-th vector from the identity basis.

5. We already know that $h_j=0$ for all $j\in \mathrm{\Lambda }$.

6. Consider $j\notin \mathrm{\Lambda }$ and take the two vectors $\tilde{\mathbf{x}}$ and ${\mathbf{e}}_j$.

7. We can see that

   $$\Vert \tilde{\mathbf{x}}\pm {\mathbf{e}}_j{\Vert }_0\le \Vert \tilde{\mathbf{x}}{\Vert }_0+1$$

   and

   $$\mathrm{supp}(\tilde{\mathbf{x}}\pm {\mathbf{e}}_j)\cap \mathrm{\Lambda }=\varnothing .$$

8. Applying (21.13) on the two vectors with ${\mathrm{\Psi }}_{\mathrm{\Lambda }}$ as our RIP matrix, we see that

   $$|⟨{\mathrm{\Psi }}_{\mathrm{\Lambda }}\tilde{\mathbf{x}},{\mathrm{\Psi }}_{\mathrm{\Lambda }}{\mathbf{e}}_j⟩-⟨\tilde{\mathbf{x}},{\mathbf{e}}_j⟩|\le \frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2\Vert {\mathbf{e}}_j{\Vert }_2.$$

9. But

   $$|⟨{\mathrm{\Psi }}_{\mathrm{\Lambda }}\tilde{\mathbf{x}},{\mathrm{\Psi }}_{\mathrm{\Lambda }}{\mathbf{e}}_j⟩-⟨\tilde{\mathbf{x}},{\mathbf{e}}_j⟩|=|h_j-{\tilde{x}}_j|.$$

10. Noting that $\Vert {\mathbf{e}}_j{\Vert }_2=1$, we get our desired result.

With this bound in place, we can develop a sufficient condition under which the identification step of OMP (which identifies the new index ${\lambda }^{k+1}$) will succeed.

The following corollary establishes a lower bound on the largest entry in $\tilde{\mathbf{x}}$ which will ensure that OMP indeed chooses the next index ${\lambda }^k$ from the support of $\tilde{\mathbf{x}}$.

Corollary 21.1

Suppose that $\mathrm{\Lambda }$, $\mathrm{\Phi }$, $\tilde{\mathbf{x}}$ meet the assumptions in Lemma 21.1, and let $\mathbf{h}$ be as defined in (21.15). If

(21.17)$$\Vert \tilde{\mathbf{x}}{\Vert }_{\mathrm{\infty }}>\frac{2{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2,$$

we are guaranteed that

$$\underset{j\notin \mathrm{\Lambda }}{\text{arg}max}|h_j|\in \mathrm{supp}(\tilde{\mathbf{x}}).$$

Proof. .

1. If (21.16) is satisfied, then for indices $j\notin \mathrm{supp}(\tilde{\mathbf{x}})$, we will have

   $$|h_j|\le \frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2.$$

2. We already know that $h_j=0$ for all $j\in \mathrm{\Lambda }$.

3. If (21.17) is satisfied, then there exists $j\in \mathrm{supp}(\tilde{\mathbf{x}})$ with

   $$|{\tilde{\mathbf{x}}}_j|>\frac{2{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2.$$

4. For this particular $j$, applying triangular inequality on (21.16)

   $$\frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2\ge |h_j-{\tilde{x}}_j|\ge |{\tilde{x}}_j|-|h_j|.$$

5. Thus

   $$\begin{array}{rl}|h_j|& \ge |{\tilde{x}}_j|-\frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2\\ & >\frac{2{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2-\frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2\\ =\frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2.\end{array}$$

6. We have established that there exists some $j\in \mathrm{supp}(\tilde{\mathbf{x}})$ for which

   $$|h_j|>\frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2$$

   and for every $j\notin \mathrm{supp}(\tilde{\mathbf{x}})$

   $$|h_j|\le \frac{{\delta }_K}{1-{\delta }_K}\Vert \tilde{\mathbf{x}}{\Vert }_2.$$

7. Together, they establish that OMP will indeed choose an index from the correct set.

All we need to do now is to make sure that (21.17) is satisfied by choosing ${\delta }_K$ small enough. The following result from [25] guarantees that.

Theorem 21.3

Suppose that $\mathrm{\Phi }$ satisfies the RIP of order $K+1$ with isometry constant $\delta <\frac{1}{2\sqrt{K}+1}$. Then for any $\mathbf{x}\in {\mathbb{R}}^N$ with $\Vert \mathbf{x}{\Vert }_0\le K$, OMP will recover $\mathbf{x}$ exactly from $\mathbf{y}=\mathrm{\Phi }\mathbf{x}$ in $K$ iterations.

The upper bound on $\delta$ can be simplified can be simplified as $\delta <\frac{1}{3\sqrt{K}}$.

Proof. The proof works by induction. We show that under the stated conditions, ${\lambda }^1\in \mathrm{supp}(\mathbf{x})$. Then we show that whenever ${\lambda }^k\in \mathrm{supp}(\mathbf{x})$ then ${\lambda }^{k+1}$ also $\in \mathrm{supp}(\mathbf{x})$.

1. For the first iteration, we have

   $${\mathbf{h}}^1={\mathrm{\Phi }}^T\mathrm{\Phi }\mathbf{y}.$$

2. Note that $\mathrm{\Phi }={\mathrm{\Psi }}_{\varnothing }$.

3. It is given that $\Vert \mathbf{x}{\Vert }_0\le K$.

4. Thus due to Theorem 18.17:

   $$\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}\ge \frac{\Vert \mathbf{x}{\Vert }_2}{\sqrt{K}}.$$

5. Now $\delta <\frac{1}{3\sqrt{K}}$ or $\delta <\frac{1}{2\sqrt{K}+1}$ implies that

   (21.18)$$\frac{2\delta }{1-\delta }<\frac{1}{\sqrt{K}}.$$

6. This can be seen as follows. Assuming $K\ge 1$, we have:

   $$\begin{array}{rl}& 3\sqrt{K}\ge 2\sqrt{K}+1\\ ⟹& \frac{1}{3\sqrt{K}}\le \frac{1}{2\sqrt{K}+1}\\ ⟹& \delta <\frac{1}{2\sqrt{K}+1}\\ ⟹& 2\delta \sqrt{K}+\delta <1\\ ⟹& 2\delta \sqrt{K}<1-\delta \\ ⟹& \frac{2\delta }{1-\delta }<\frac{1}{\sqrt{K}}.\end{array}$$

7. Therefore

   $$\Vert \mathbf{x}{\Vert }_{\mathrm{\infty }}>\frac{2\delta }{1-\delta }\Vert \mathbf{x}{\Vert }_2$$

   and (21.17) is satisfied and ${\lambda }^1$ will indeed be chosen from $\mathrm{supp}(\mathbf{x})$ due to Corollary 21.1.

8. We now assume that OMP has correctly discovered indices up to ${\lambda }^1,\dots ,{\lambda }^k$. i.e.

   $${\mathrm{\Lambda }}^k\subset \mathrm{supp}(\mathbf{x}).$$

9. We have to show that it will also correctly discover ${\lambda }^{k+1}$.

10. From the definition of $\tilde{\mathbf{x}}$ in (21.10), we know that $\mathrm{supp}\left({\tilde{\mathbf{x}}}^k\right)\cap {\mathrm{\Lambda }}^k=\varnothing$.

11. Thus

    $$\Vert {\tilde{\mathbf{x}}}^k{\Vert }_0\le K-k.$$

12. We also know that $|{\mathrm{\Lambda }}^k|=k$. By assumption $\mathrm{\Phi }$ satisfies RIP of order $K+1=(K-k)+k+1$.

13. Thus

    $$K+1\ge \Vert {\tilde{\mathbf{x}}}^k{\Vert }_0+|{\mathrm{\Lambda }}^k|+1.$$

14. Also due to Theorem 18.17:

    $$\Vert {\tilde{\mathbf{x}}}^k{\Vert }_{\mathrm{\infty }}\ge \frac{\Vert {\tilde{\mathbf{x}}}^k{\Vert }_2}{\sqrt{K-k}}\ge \frac{\Vert {\tilde{\mathbf{x}}}^k{\Vert }_2}{\sqrt{K}}.$$

15. Using (21.18), we get

    $$\Vert {\tilde{\mathbf{x}}}^k{\Vert }_{\mathrm{\infty }}>\frac{2\delta }{1-\delta }\Vert {\tilde{\mathbf{x}}}^k{\Vert }_2.$$

16. This is the sufficient condition for Corollary 21.1 in (21.17) giving us

    $${\lambda }^{k+1}=\underset{j\notin {\mathrm{\Lambda }}^k}{\text{arg}max}|{\mathbf{h}}_j^{k+1}|\in \mathrm{supp}({\tilde{\mathbf{x}}}^k).$$

17. Hence ${\mathrm{\Lambda }}^{k+1}\subseteq \mathrm{supp}(\mathbf{x})$.