# Greedy Sparse Signal Recovery with Tree Pruning

Jaeseok Lee, Suhyuk Kwon, Jun Won Choi, and Byonghyo Shim
J. Lee, S. Kwon and B. Shim are with Dept. of Electrical and Computer
Engineering, Seoul National University, Seoul, Korea, and J. Choi is with
Dept. of Electrical Engineering, Hanyang University, Seoul, Korea. This work
was sponsored by Communications Research Team (CRT), DMC R$\&$D Center,
Samsung Electronics Co. Ltd, the MSIP (Ministry of Science, ICT $\&$ Future
Planning), Korea in the ICT R$\&$D Program 2013 (KCA-12-911-01-110) and the
NRF grant funded by the Korea government (MEST) (No. 2012R1A2A2A01047510). A
part of this paper was presented in International Symposium on Information
Theory (ISIT) 2014.

###### Abstract

Recently, greedy algorithm has received much attention as a cost-effective
means to reconstruct the sparse signals from compressed measurements. Much of
previous work has focused on the investigation of a single candidate to
identify the support (index set of nonzero elements) of the sparse signals.
Well-known drawback of the greedy approach is that the chosen candidate is
often not the optimal solution due to the myopic decision in each iteration.
In this paper, we propose a greedy sparse recovery algorithm investigating
multiple promising candidates via the tree search. Two key ingredients of the
proposed algorithm, referred to as the matching pursuit with a tree pruning
(TMP), to achieve efficiency in the tree search are the pre-selection to put a
restriction on columns of the sensing matrix to be investigated and the tree
pruning to eliminate unpromising paths from the search tree. In our
performance guarantee analysis and empirical simulations, we show that TMP is
effective in recovering sparse signals in both noiseless and noisy scenarios.

###### Index Terms:

Compressive sensing, greedy tree search, sparse signal recovery, restricted
isometry property.

##  I Introduction

In recent years, compressive sensing (CS) has received much attention as a
means to recover sparse signals in underdetermined system [1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13]. Key finding of the CS paradigm is that one can
recover signals with far fewer measurements than traditional approaches use as
long as the signals to be recovered are sparse and the sensing mechanism
roughly preserves the energy of signals of interest.

It is now well known that the problem to recover the sparest signal
$\mathbf{x}$ using the measurements $\mathbf{y}=\mathbf{\Phi x}$ is formulated
as the $\ell_{0}$-minimization problem

$\displaystyle\min_{\mathbf{x}}\|\mathbf{x}\|_{0}\,\,\,\,\,\,\,\,\text{subject
to}\,\,\,\mathbf{y}=\mathbf{\Phi x}$ (1)

where $\mathbf{\Phi}\in\mathbb{R}^{M\times N}$ is often called sensing matrix.
Since solving this problem is combinatoric in nature and known to be NP-
hard[1], early works focused on the $\ell_{1}$-relaxation method, such as
Basis Pursuit (BP)[1], BP denoising (BPDN) [14] (also known as Lasso [5]), and
Dantzig selector [6]. Another line of research receiving much attention in
recent years is a greedy approach. In a nutshell, greedy algorithm attempts to
find the support (index set of nonzero entries) in an iterative fashion,
returning a sequence of estimates of the sparse input vector. Although the
greedy algorithm, such as orthogonal matching pursuit (OMP) [7], is relatively
simple to implement and also computationally efficient, performance is in
general not so appealing, in particular for the noisy scenario.

Figure 1: Illustration of the proposed TMP algorithm. Path with dotted box is
pruned from the tree since the magnitude of the residual is larger than the
threshold $\epsilon$.

The aim of this paper is to introduce an efficient tree search algorithm to
recover the sparse signal referred to as the _matching pursuit with a tree
pruning_ (TMP). Our approach significantly reduces the computational burden of
the exhaustive search yet achieves excellent recovery performance in both
noiseless and noisy scenarios. Two key ingredients of the TMP algorithm
accomplishing this mission are the pre-selection to put a restriction on
columns of $\mathbf{\Phi}$ to be investigated and the tree pruning to
eliminate unpromising paths from the search tree. In the pre-selection stage,
we choose a small number of promising columns in the sensing matrix using a
conventional greedy algorithm. If we denote the set of column indices obtained
in the pre-selection stage as $\Theta$, then we set $N\gg|\Theta|>K$ where $K$
is the sparsity of the input vector ($\|\mathbf{x}\|_{0}=K$). When we
construct the tree for the search, we only use elements of $\Theta$ as a child
node in the branching process so that relentless growth of the tree can be
prevented. In our empirical results, we show that TMP achieves near best
performance only with $|\Theta|\approx 2K$. Once the pre-selection is
finished, a tree search is performed to find best estimate of support using
the pre-selected set $\Theta$. As mentioned, when we select the child node
(new estimate of the support element), we only consider the elements of
$\Theta$. As a result, the number of all possible paths in the tree is reduced
from $\binom{N}{K}$ to $\binom{|\Theta|}{K}$. While this reduction is
phenomenal, searching all of these is still computationally demanding, in
particular for large $N$ and nontrivial $K$. In order to alleviate
computational burden and at the same time maintain the effectiveness of the
search, we introduce an aggressive tree pruning strategy by which unpromising
paths are removed from the tree. Note that to perform the tree pruning, we
need to compare the cost function
$J(\Lambda)=\|\mathbf{y}-\mathbf{\Phi}_{\Lambda}\hat{\mathbf{x}}_{\Lambda}\|_{2}$
of the full-blown candidate $\Lambda$ ($\|\Lambda\|_{0}=K$) against a pruning
threshold. However, direct evaluation of $J(\Lambda)$ is not possible in the
middle of search due to the causality of the search process so that we combine
already selected indices (henceforth dubbed as the _causal set_) and roughly
estimated indices (_noncausal set_). If this roughly estimated cost function
is greater than the deliberately designed pruning threshold $\epsilon$ (i.e.,
$J(\Lambda)>\epsilon$), further investigation of the path is hopeless and
hence we prune the path from the tree immediately.

In our analysis, we show that the proposed method can accurately identify the
support of $K$-sparse signal and hence reconstruct the original sparse signal
accurately in the noiseless setting if the sensing matrix satisfies the
property so called restricted isometry property (RIP) (Theorem III.9). In the
noisy setting, we show that the accurate identification of support is possible
if the signal power is sufficiently larger than the noise power (Theorem
III.18). In our empirical simulations, we confirm that TMP performs close to
an ideal estimator111The estimator that has a prior knowledge on the support
(which component of the sparse vector is zero or not) is often called Oracle
estimator. (often called Oracle estimator [15]) in the high SNR regime.

The rest of this paper is organized as follows. In Section II, we introduce
the proposed TMP algorithm. In Section III, we analyze the recovery condition
under which TMP identifies the support accurately in the noiseless and noisy
scenarios. In Section IV, we provide the empirical results and then conclude
the paper in Section V.

TABLE I: The TMP algorithm

Input: measurement $\mathbf{y}$, sensing matrix $\mathbf{\Phi}$, sparsity $K$,
initial threshold $\epsilon_{1}$
---
Output: Estimated signal $\hat{\mathbf{x}}$
Initialization: $i:=0$, $S^{0}:=\emptyset$
$\Theta=f_{\text{preselection}}\left(\mathbf{y},\,\mathbf{\Phi},\,p\right)$ | (preselection)
while $i<K$ do
$i:=i+1$, $S^{i}:=\emptyset$, $\epsilon_{i+1}:=\epsilon_{i}$
for $l=1$ to $|S^{i-1}|$ do
$\theta:=\Theta\setminus\hat{s}_{1}^{i-1}(l)$
for $j=1$ to $|\theta|$ do
$\hat{s}_{1}^{i}:=\hat{s}_{1}^{i-1}(l)\cup\left\\{s_{i}(j)\right\\}$ | (update $j$-th path)
if $\hat{s}_{1}^{i}\not\in S^{i}$ then | (check the duplicated path)
$\tilde{s}_{i+1}^{K}\\!=\\!\arg\\!\mathop{\max}\limits_{\mathop{s\subset\Omega,}\limits_{|s|=K-i}}\\!\|\mathbf{\Phi}_{s}^{\prime}\\!\mathbf{r}_{\hat{s}_{1}^{i}}\\!\\!\|_{2}$ | (support estimation)
$\bar{s}_{1}^{K}=\hat{s}_{1}^{i}\cup\tilde{s}_{i+1}^{K}$,
$\mathbf{r}_{\bar{s}_{1}^{K}}=\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{y}$
if $\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}\leq\epsilon_{i}$ then | (pruning decision)
$S^{i}:=S^{i}\cup\hat{s}_{1}^{i}$, $I^{*}:=\bar{s}_{1}^{K}$
if $\|\mathbf{r}_{I^{*}}\|_{2}\leq\epsilon_{i+1}$ then
$\epsilon_{i+1}:=\left\|\mathbf{r}_{I^{*}}\right\|_{2}$ | (update pruning threshold)
end if
end if
end if
end for
end for
end while
return $\hat{\mathbf{x}}^{*}=\mathbf{\Phi}^{\dagger}_{I^{*}}\mathbf{y}$ | (signal reconstruction)

The $f_{\text{preselection}}(\cdot)$ is a function to choose multiple
promising indices (see Section II.A).

##  II Matching pursuit with a tree pruning

The proposed TMP algorithm consists of two steps: pre-selection and tree
search. We first describe the pre-selection process and then discuss the
efficient greedy tree search.

###  II-A Pre-selection: A First Stage Pruning

The purpose of the pre-selection is to estimate indices that are highly likely
to be the elements of support $T$. Alternatively put, we do our best guess to
choose columns of sensing matrix that are associated with nonzero elements of
the sparse vector. Denoting the set of indices as $\Theta$, then the search
set is reduced from $\Omega=\\{1,2,\cdots,N\\}$ to $\Theta$, a small subset of
$\Omega$. When we perform the tree search, we only use elements of the pre-
selected set $\Theta$ as a new element in the child paths so that we can limit
the number of paths in the tree and eventually reduce the search complexity.
In the construction of $\Theta$, one can basically use any sparse recovery
algorithm returning more than $K$ indices. Well-known examples include the OMP
algorithm running more than K-iterations [16] or the generalized OMP algorithm
[17].

###  II-B Tree Search with Pruning

Once the pre-selection is finished, we perform the tree search to identify the
support. In this setting, the tree has a maximum depth $K$, and the goal is to
find a path with depth $K$ (i.e., candidate with cardinality $K$) that has the
smallest cost function
$J(\Lambda)=\|\mathbf{y}-\mathbf{\Phi}_{\Lambda}\hat{\mathbf{x}}_{\Lambda}\|_{2}$.
This cost function is often referred to as $\ell_{2}$-norm of the residual
$\mathbf{r}_{\Lambda}=\mathbf{y}-\mathbf{\Phi}_{\Lambda}\hat{\mathbf{x}}_{\Lambda}$.
In each iteration, new child path is generated by adding new element to the
existing path. If we denote the path222In this paper, we use path and
candidate interchangeably. In particular, we denote a full-blown path
$\bar{s}_{1}^{K}$ by candidate. at layer (iteration) $i$ as $\hat{s}_{1}^{i}$,
then $\hat{s}_{1}^{i}=\\{s_{1},s_{2},\cdots s_{i}\\}$ is the causal set chosen
in the first $i$ iterations. Since visiting all possible child nodes to find
out the optimal solution is clearly prohibitive, we introduce an aggressive
pruning strategy to remove unpromising paths from the tree. This pruning
decision is done by comparing the cost function of the path and the pruning
threshold chosen by the smallest cost function of all paths visited.

Figure 2: The pruning operation of TMP in the $i$-th layer where $j$ is the
index of column in $\Theta\setminus\hat{s}_{1}^{i-1}$. Note that TMP
investigates each path $\hat{s}_{1}^{i}$ and performs the pruning of the path
if $\|\mathbf{r}_{\hat{s}_{1}^{i}\cup\tilde{s}_{i+1}^{K}}\|_{2}>\epsilon$.

It is worth mentioning that in contrast to typical tree search problems, it is
not easy, and in fact not possible, to decide the pruning of a path using the
causal set only. We note that in many tree search problems, the cost function
of the path increases monotonically with the iteration (e.g., Viterbi decoding
algorithm for maximum-likelihood detection) [18, 19, 20]. Therefore, if a path
whose partial cost function generated by the contributions of causal path only
exceeds the cost function of already visited full-blown path, the path under
investigation cannot be the solution of the problem and hence can be pruned
immediately from the tree (see Fig. 3).

Figure 3: Cost function of the path: (a) conventional tree search and (b)
proposed tree search.

This pruning strategy, unfortunately, cannot be applied to the problem at hand
since the partial cost function, which corresponds to the magnitude of the
residual, is a monotonic decreasing function of the iteration333If
$\hat{s}_{1}^{i}\subset\hat{s}_{1}^{i+1}$, then
$\|\mathbf{r}_{\hat{s}_{1}^{i}}\|_{2}\geq\|\mathbf{r}_{\hat{s}_{1}^{i+1}}\|_{2}$..
To make a proper decision, therefore, we have no way but to consider the cost
function of full-blown path and hence need a noncausal set
$\tilde{s}_{i+1}^{K}=\\{s_{i+1},\,s_{i+2},\,\cdots,\,s_{K}\\}$ in the pruning
process. This noncausal set $\tilde{s}_{i+1}^{K}$ is temporarily needed for
the pruning operation and can be easily obtained by choosing $K-i$ indices of
columns in $\Omega\setminus\hat{s}_{1}^{i}$ whose magnitude of the correlation
with the residual $\mathbf{r}_{\hat{s}_{1}^{i}}$ is maximal444Instead of a
single-shot process choosing $K-i$ indices simultaneously, noncausal set
$\tilde{s}_{i+1}^{K}$ can be chosen by running multiple iterations for better
judgement.. That is,

$\displaystyle\tilde{s}_{i+1}^{K}=\arg\mathop{\max_{s\subset\Omega\setminus\hat{s}_{1}^{i},}}\limits_{|s|=K-i}\left\|\mathbf{\Phi}_{s}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}\right\|_{2}$
(2)

where

$\displaystyle\mathbf{r}_{\hat{s}_{1}^{i}}$ $\displaystyle=$
$\displaystyle\mathbf{y}-\mathbf{\Phi}_{\hat{s}_{1}^{i}}\hat{\mathbf{x}}_{\hat{s}_{1}^{i}},$
$\displaystyle\hat{\mathbf{x}}_{\hat{s}_{1}^{i}}$ $\displaystyle=$
$\displaystyle\mathbf{\Phi}^{\dagger}_{\hat{s}_{1}^{i}}\mathbf{y}.$

For example, if $K-i=2$,
$\Omega\setminus\hat{s}_{1}^{i}=\\{5,7,9,11,\cdots\\}$, and

$|\mathbf{\phi}_{7}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|>|\mathbf{\phi}_{11}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|>|\mathbf{\phi}_{5}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|>|\mathbf{\phi}_{9}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|>\cdots,$

then the noncausal set is $\tilde{s}_{i+1}^{K}=\\{7,11\\}$.

Once roughly estimated candidate
$\bar{s}_{1}^{K}=\hat{s}_{1}^{i}\cup\tilde{s}_{i+1}^{K}$ is obtained, we
compute the residual
$\mathbf{r}_{\bar{s}_{1}^{K}}=\mathbf{y}-\mathbf{\Phi}_{\bar{s}_{1}^{K}}\hat{\mathbf{x}}_{\bar{s}_{1}^{K}}$
($\hat{\mathbf{x}}_{\bar{s}_{1}^{K}}=\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\dagger}\mathbf{y}$)
to decide whether to prune this path or not. To be specific, if the
$\ell_{2}$-norm of the residual is greater than the threshold $\epsilon$
(i.e., $\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}>\epsilon$), then the path has
little hope to survive and hence is pruned immediately (see Fig. 1). Note that
the pruning threshold $\epsilon$ is initialized to a large number and whenever
the search of a layer is finished, updated to the minimum $\ell_{2}$-norm of
the residual among all survived paths
($\epsilon=\min\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}$). Once the search is
finished, a path with the minimum cost function is chosen as the final output
of TMP. We summarize the proposed TMP algorithm in Table I.

##  III Performance Analysis

In this section, we analyze the recovery conditions under which TMP can
accurately identify $K$-sparse signals in noiseless and noisy scenarios. In
our analysis, we use the restricted isometry property (RIP) of the sensing
matrix.

###### Definition III.1

The sensing matrix $\mathbf{\Phi}$ is said to satisfy the RIP of order $K$ if
there exists a constant $\delta(\mathbf{\Phi})\in(0,1)$ such that

$(1-\delta(\mathbf{\Phi}))\|\mathbf{x}\|_{2}^{2}\leq\|\mathbf{\Phi}\mathbf{x}\|_{2}^{2}\leq(1+\delta(\mathbf{\Phi}))\|\mathbf{x}\|_{2}^{2}$

for any $K$-sparse vector $\mathbf{x}$.

In particular, the minimum of all constants $\delta(\mathbf{\Phi})$ satisfying
Definition III.1 is called the restricted isometry constant (RIC) and denoted
by $\delta_{K}(\mathbf{\Phi})$. In the sequel, we use $\delta_{K}$ instead of
$\delta_{K}(\mathbf{\Phi})$ for brevity.

In our analysis, we use the generalized OMP (gOMP) as a pre-selection
algorithm. The gOMP algorithm chooses $L$ ($>1$) indices in each iteration and
hence $LK$ indices are chosen in total. Due to the selection of multiple
indices, more than one true indices (indices in the support) can be chosen in
each iteration and the chance of identifying the support increases
substantially [17].

The following lemmas are useful in our analysis.

###### Lemma III.2

(Lemma 3 in [2]): If the sensing matrix $\mathbf{\Phi}$ satisfies the RIP of
both orders $K_{1}$ and $K_{2}$, then $\delta_{K_{1}}<\delta_{K_{2}}$ for any
$K_{1}<K_{2}$.

###### Lemma III.3

(Consequences of RIP [2, 9]): If $0<\delta_{|I|}<1$ exists for
$I\subset\Omega$, then for any vector $\mathbf{x}\in\mathbb{R}^{|I|}$,

$\displaystyle\left(1-\delta_{|I|}\right)\|\mathbf{x}\|_{2}\leq\|\mathbf{\Phi}_{I}^{\prime}\mathbf{\Phi}_{I}\mathbf{x}\|_{2}\leq\left(1+\delta_{|I|}\right)\|\mathbf{x}\|_{2},$
$\displaystyle\frac{1}{1+\delta_{|I|}}\|\mathbf{x}\|_{2}\leq\|\left(\mathbf{\Phi}_{I}^{\prime}\mathbf{\Phi}_{I}\right)^{-1}\mathbf{x}\|_{2}\leq\frac{1}{1-\delta_{|I|}}\|\mathbf{x}\|_{2}.$

###### Lemma III.4

(Lemma 2.1 in [4]): Let $I_{1},\,I_{2}\subset\Omega$ and $I_{1}\cap
I_{2}=\emptyset$. If $0<\delta_{|I_{1}|+|I_{2}|}<1$ exists, then

$\displaystyle\|\mathbf{\Phi}_{I_{1}}^{\prime}\mathbf{\Phi}_{I_{2}}\mathbf{x}\|_{2}\leq\delta_{|I_{1}|+|I_{2}|}\|\mathbf{x}\|_{2}.$

###  III-A Recovery from Noiseless Measurements

In this subsection, we analyze a condition ensuring that TMP recovers the
original sparse signal accurately from the noiseless measurements. As
mentioned, TMP consists of pre-selection and tree search. In our analysis, we
show that the recovery condition of TMP is not much different from the
condition of the pre-selection only and in fact guaranteed under more relaxed
RIP bound (see Theorem III.9).

In order to ensure the accurate identification of the support, TMP should
satisfy the following two conditions:

  1. 1.

At least one support index should be selected in the pre-selection process
(i.e., $T\cap\Theta\neq\emptyset$).

  2. 2.

At least one true path555If $\hat{s}_{1}^{i}$ is a true path, it contains
indices only in $T$ ($\hat{s}_{1}^{i}\subset T$). should be survived in the
tree pruning process.

The following Theorem describes the condition ensuring that at least one
support is identified by the pre-selection stage.

######  Theorem III.5 (Recovery condition in first iteration for noiseless
scenario [17])

The gOMP algorithm identifies at least one support index in the first
iteration if the sensing matrix $\mathbf{\Phi}$ satisfies

$\delta_{L+K}<\frac{\sqrt{L}}{\sqrt{L}+\sqrt{K}}.$ (3)

We next analyze the condition ensuring that the final candidate
$\bar{s}_{1}^{K}$ of the tree search equals the support $T$. In order to
guarantee $\bar{s}_{1}^{K}=T$, at least one true path should be survived in
each layer and further a true index should be added to this path.

Before we proceed, we provide definitions useful in our analysis. Let
$\lambda_{i}$ be the smallest correlation in magnitude between the residual
$\mathbf{r}_{\hat{s}_{1}^{i}}$ and columns associated with correct indices.
That is,

$\lambda^{i}=\mathop{\min}\limits_{u\in
T\setminus\hat{s}_{1}^{i}}\left|\phi_{u}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}\right|.$

Further, let $\gamma^{i}$ be the largest correlation in magnitude between
$\mathbf{r}_{\hat{s}_{1}^{i}}$ and columns associated with incorrect indices.
That is,

$\gamma^{i}=\mathop{\max}\limits_{u\in
T^{c}}\left|<\phi_{u},\mathbf{r}_{\hat{s}_{1}^{i}}>\right|.$

In the following lemmas, we provide a lower bound of $\lambda^{i}$ and an
upper bound of $\gamma^{i}$.

###### Lemma III.6

Suppose a path $\hat{s}_{1}^{i}$ is contained in $T$ (i.e.,
$\hat{s}_{1}^{i}\subset T$), then

$\lambda^{i}\geq\frac{1-\delta_{K}-\delta_{M}}{1-\delta_{K}}\left\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\right\|_{2}.$
(4)

###### Proof:

See Appendix A. ∎

###### Lemma III.7

Suppose a path $\hat{s}_{1}^{i}$ is contained in $T$, then

$\gamma^{i}\leq\frac{\delta_{K+1}}{1-\delta_{K}}\left\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\right\|_{2}.$
(5)

###### Proof:

See Appendix B. ∎

As mentioned, in order to recover the original sparse signals, at least one
true path should be survived in each layer. In other words, when a path
$\hat{s}_{1}^{i}$ is contained in $T$ ($\hat{s}_{1}^{i}\subset T$), then the
noncausal set $\tilde{s}_{i+1}^{K}$ should also be contained in $T$ (i.e.,
$\tilde{s}_{i+1}^{K}\subset T$) and further this path should not be pruned for
the accurate reconstruction of the sparse signals. That is,

$\|\mathbf{r}_{\hat{s}_{1}^{i}\cup\tilde{s}_{i+1}^{K}}\|=\|\mathbf{r}_{T}\|<\epsilon.$
(6)

Since $\|\mathbf{r}_{T}\|_{2}=0$ for the noiseless scenario, the condition (6)
always holds for any positive $\epsilon$. Thus, what we essentially need is a
condition ensuring that the noncausal set chosen from (2) is contained in $T$
(i.e., $\tilde{s}_{i+1}^{K}\subset T$).

Figure 4: Comparison between $\lambda^{i}$ and $\gamma^{i}$ for the true path
$\hat{s}_{1}^{i}$ (i.e., $\hat{s}_{1}^{i}\subset T$). $\lambda_{i}$ is the
smallest correlation (in magnitude) between the residual
$\mathbf{r}_{\hat{s}_{1}^{i}}$ and columns associated with
$T\setminus\hat{s}_{1}^{i}$ and $\gamma^{i}$ is the largest correlation (in
magnitude) between $\mathbf{r}_{\hat{s}_{1}^{i}}$ and columns associated with
$T^{c}$. One can observe that, if $\lambda^{i}>\gamma^{i}$, then the noncausal
set $\bar{s}_{1}^{K}$ is contained in $T$
($\bar{s}_{1}^{K}=T\setminus\hat{s}_{1}^{i}$).

###### Theorem III.8

If the causal path $\hat{s}_{1}^{i}$ contains correct indices only, then the
noncausal set $\tilde{s}_{i+1}^{K}$ of TMP consist only of correct ones under

$\delta_{M}<\frac{1}{3}.$ (7)

for any $i$ ($0\leq i\leq K-1$). In other words,
$\bar{s}_{1}^{K}(=\hat{s}_{1}^{i}\cup\tilde{s}_{i+1}^{K})=T$ under
$\delta_{M}<\frac{1}{3}$.

###### Proof:

Since the indices of columns highly correlated with
$\mathbf{r}_{\hat{s}_{1}^{i}}$ are chosen as elements of $\tilde{s}_{i+1}^{K}$
(see (2)), if $\lambda^{i}$ is larger than $\gamma^{i}$, then the noncausal
set $\tilde{s}_{i+1}^{K}$ is contained in $T$
($\tilde{s}_{i+1}^{K}=T\setminus\hat{s}_{1}^{i}$). In other words,
$\bar{s}_{1}^{K}=T$ under

$\lambda^{i}>\gamma^{i}.$ (8)

Using Lemma III.6 and III.7, (8) holds under

$\frac{1-\delta_{K}-\delta_{M}}{1-\delta_{K}}\left\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\right\|_{2}>\frac{\delta_{K+1}}{1-\delta_{K}}\left\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\right\|_{2},$

and hence $\delta_{K}+\delta_{K+1}+\delta_{M}<1$. Further, using Lemma III.2,
we have $3\delta_{M}<1$, which is the desired result. ∎

If Theorem III.5 and III.8 are jointly satisfied, $\tilde{s}_{i+1}^{K}\subset
T$ for any true path $\hat{s}_{1}^{i}$ ($\hat{s}_{1}^{i}\subset T$) so that
$\bar{s}_{1}^{K}=\hat{s}_{1}^{i}\cup\tilde{s}_{i+1}^{K}=T$ and thus
$\hat{s}_{1}^{i}$ will not be pruned from the tree (we recall that
$\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}=0<\epsilon$ for any positive
$\epsilon$). Therefore, overall recovery condition of TMP for the noiseless
scenario can be obtained by combining Theorem III.5 and III.8.

######  Theorem III.9 (Recovery condition of TMP)

The TMP algorithm identifies the support of any $K$-sparse signal from
$\mathbf{y}=\mathbf{\Phi x}$ accurately if the sensing matrix $\mathbf{\Phi}$
satisfies the RIP with

$\displaystyle\delta_{Q}<\frac{1}{3}$ $\displaystyle\text{if }K<4L,$ (9)
$\displaystyle\delta_{Q}<\frac{\sqrt{L}}{\sqrt{L}+\sqrt{K}}$ otherwise (10)

where $Q=\max\\{M,L+K\\}$.

###### Proof:

The conditions (9) and (10) are obtained by choosing stricter condition
between Theorem III.5 and III.8. Specifically,

$\displaystyle\text{if }\frac{\sqrt{L}}{\sqrt{L}+\sqrt{K}}>\frac{1}{3}$
$\displaystyle\rightarrow$ $\displaystyle\delta_{Q}<\frac{1}{3}$ otherwise
$\displaystyle\rightarrow$
$\displaystyle\delta_{Q}<\frac{\sqrt{L}}{\sqrt{L}+\sqrt{K}},$

which is the desired result. ∎

Recall that the exact recovery condition of the original gOMP algorithm is
[17]

$\displaystyle\delta_{LK}<\frac{\sqrt{L}}{\sqrt{L}+2\sqrt{K}}.$ (11)

From (9)-(11), it is clear that TMP provides more relaxed upper bound for any
$L<K$ since
$\frac{\sqrt{L}}{\sqrt{L}+2\sqrt{K}}<\min\\{\frac{1}{3},\,\frac{\sqrt{L}}{\sqrt{L}+\sqrt{K}}\\}$.
Even if $L=K$, TMP is effective since the exact recovery conditions of gOMP
and TMP are

$\delta_{K^{2}}<\frac{1}{3}$

and

$\delta_{\max\\{M,2K\\}}<\frac{1}{3},$

respectively. One can observe that in the large dimensional system satisfying
$K^{2}>M$, recovery condition of TMP is better (more relaxed) than the
condition of gOMP. Similar argument holds for other sparse recovery algorithm
(e.g., CoSaMP [9]).

###  III-B Reconstruction from Noisy Measurements

Now, we turn to the noisy scenario and analyze the condition of TMP to
accurately identify the support in the presence of noise. Even though the
details are a bit cumbersome, main architecture of the proof is reminiscent of
the argument in the noiseless scenario. In fact, two requirements of TMP to
identify the support are 1) at least one support element should be chosen in
the pre-selection process (i.e., $T\cap\Omega\neq\emptyset$), and 2) true path
($\bar{s}_{1}^{K}=T$) should be survived in the pruning process.

Before we proceed, we provide useful definitions in our analysis. First, let
$\rho$ be the largest correlation (in magnitude) between the observation
$\mathbf{y}$ and the columns associated with true indices. That is,

$\displaystyle\rho=\max_{j\in T}|\phi_{j}^{\prime}\mathbf{y}|.$

Next, let $\eta$ be the $L$-th largest correlation (in magnitude) between the
observation $\mathbf{y}$ and the columns associated with incorrect indices.
Then $\eta$ is expressed as

$\displaystyle\eta=\min_{j\in I_{L}}|\phi_{j}^{\prime}\mathbf{y}|.$

where $I_{L}=\arg\mathop{\max}\limits_{|I|=L,I\subset
T^{c}}\|\mathbf{\Phi}_{I}^{\prime}\mathbf{r}_{\Lambda}\|_{2}$.

In the following lemmas, we provide the lower bound of $\rho$ and the upper
bound of $\eta$.

###### Lemma III.10

$\rho$ satisfies

$\displaystyle\rho\geq\frac{1}{\sqrt{K}}\left[\left(1-\delta_{K}\right)\|\mathbf{x}_{T}\|_{2}-\sqrt{1+\delta_{K}}\|\mathbf{v}\|_{2}\right]$
(12)

###### Proof:

See Appendex C. ∎

###### Lemma III.11

$\eta$ satisfies

$\displaystyle\eta\leq\frac{1}{\sqrt{L}}\left[\delta_{L+K}\|\mathbf{x}_{T}\|_{2}+\sqrt{1+\delta_{L}}\|\mathbf{v}\|_{2}\right].$
(13)

###### Proof:

See Appendex D. ∎

The following theorem provides the condition ensuring that at least one
support element is identified by the pre-selection stage.

###### Theorem III.12

The gOMP algorithm identifies at least one support element if the nonzero
coefficients of the original sparse signal $\mathbf{x}$ satisfy

$\displaystyle\min_{j\in
T}|x_{j}|>\frac{(\sqrt{K}+\sqrt{L})\sqrt{1+\delta_{L+K}}}{\sqrt{L}(1-\delta_{K})-\sqrt{K}\delta_{L+K}}\|\mathbf{v}\|_{2}.$
(14)

###### Proof:

From definitions of $\rho$ and $\eta$, it is clear that gOMP selects at least
one true index in the first iteration if

$\displaystyle\rho>\eta.$ (15)

Using the lower bound of $\rho$ and the upper bound of $\eta$, we obtain the
sufficient condition of (15) as

$\displaystyle\frac{1}{\sqrt{K}}\left[\left(1-\delta_{K}\right)\|\mathbf{x}_{T}\|_{2}-\sqrt{1+\delta_{K}}\|\mathbf{v}\|_{2}\right]>\frac{1}{\sqrt{L}}\left[\delta_{L+K}\|\mathbf{x}_{T}\|_{2}+\sqrt{1+\delta_{L}}\|\mathbf{v}\|_{2}\right].$
(16)

After some manipulations, we have

$\displaystyle\|\mathbf{x}_{T}\|_{2}>\frac{(\sqrt{K}+\sqrt{L})\sqrt{1+\delta_{L+K}}}{\sqrt{L}(1-\delta_{K})-\sqrt{K}\delta_{L+K}}\|\mathbf{v}\|_{2}.$
(17)

Since $\|\mathbf{x}_{T}\|_{2}\geq\mathop{\min}\limits_{j\in T}|x_{j}|$, (17)
is guaranteed under

$\displaystyle\min_{j\in
T}|x_{j}|>\frac{(\sqrt{K}+\sqrt{L})\sqrt{1+\delta_{L+K}}}{\sqrt{L}(1-\delta_{K})-\sqrt{K}\delta_{L+K}}\|\mathbf{v}\|_{2},$
(18)

which completes the proof. ∎

We next analyze the condition under which the true path is survived by the
tree pruning stage. In order to meet this requirement, 1) under the condition
that a causal set is true ($\hat{s}_{1}^{i}\subset T$), corresponding
noncausal set should also be true ($\tilde{s}_{i+1}^{K}\subset T$) and further
2) this true path should not be removed by the tree pruning (i.e., if
$\bar{s}_{1}^{K}=T$, then $\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}<\epsilon$).

Before we proceed, we introduce two useful definitions in our analysis. Let
$\beta^{i}$ be the smallest correlation in magnitude between $\phi_{j}$ ($j\in
T\setminus\hat{s}_{1}^{i}$) and $\mathbf{r}_{\hat{s}_{1}^{i}}$:

$\displaystyle\beta^{i}=\arg\min_{j\in
T\setminus\hat{s}_{1}^{i}}|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|.$

Similarly, let $\alpha^{i}$ be the largest correlation in magnitude between
$\phi_{j}$ ($j\in T^{c}$) and the residual $\mathbf{r}_{\hat{s}_{1}^{i}}$:

$\displaystyle\alpha^{i}=\arg\max_{j\in
T^{c}}|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|.$

The following two lemmas provide the lower and upper bounds of $\beta^{i}$ and
$\alpha^{i}$, respectively.

###### Lemma III.13

If $\hat{s}_{1}^{i}$ contains true indices exclusively, then $\beta^{i}$
satisfies

$\displaystyle\beta^{i}\geq\left(1-\delta_{M}-\frac{\delta_{K+1}\delta_{K}}{1-\delta_{K}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}$
(19)

###### Proof:

See Appendix E. ∎

###### Lemma III.14

If $\hat{s}_{1}^{i}$ contains true indices exclusively, then $\alpha^{i}$
satisfies

$\displaystyle\alpha^{i}\leq\left(\delta_{K+1}+\frac{\delta_{K+1}\delta_{K}}{1-\delta_{K}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}$
(20)

###### Proof:

See Appendix F. ∎

Using these lemmas, we can identify the condition guaranteeing that the
noncausal set $\tilde{s}_{i+1}^{K}$ of a true path ($\hat{s}_{1}^{i}\subset
T$) is also true.

###### Lemma III.15

Suppose a causal path $\hat{s}_{1}^{i}$ consists of true indices exclusively
(i.e., $\hat{s}_{1}^{i}\subset T$), then the noncausal set
$\tilde{s}_{i+1}^{K}$ also contains the true ones
($\tilde{s}_{i+1}^{K}=T\setminus\hat{s}_{1}^{i}$) under

$\displaystyle\min_{j\in
T}|x_{j}|>\frac{2(1-\delta_{K})\sqrt{1+\delta_{M}}}{1-\delta_{K}-\delta_{K+1}-\delta_{M}}\|\mathbf{v}\|_{2}.$
(21)

###### Proof:

One can easily show that the noncausal set of any true path $\hat{s}_{1}^{i}$
contains only true indices if

$\displaystyle\beta^{i}>\alpha^{i}.$ (22)

Using Lemma III.13 and III.14, we obtain the sufficient condition of (22) as

$\displaystyle\left(1-\delta_{M}-\frac{\delta_{M}\delta_{K}}{1-\delta_{K}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}$
(23) $\displaystyle\hskip
85.35826pt>\left(\delta_{K+1}+\frac{\delta_{K+1}\delta_{K}}{1-\delta_{K}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}.$

After some manipulations, we have

$\displaystyle\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}>\frac{2(1-\delta_{K})\sqrt{1+\delta_{M}}}{1-\delta_{K}-\delta_{K+1}-\delta_{M}}\|\mathbf{v}\|_{2}.$
(24)

Since
$\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}\geq\mathop{\min}\limits_{j\in
T}|x_{j}|$, we get the desired result. ∎

Next, we turn to the analysis of the condition under which the magnitude of
$\mathbf{r}_{T}$ becomes the minimum among all combinations of $K$ indices.

###### Lemma III.16

The candidate whose residual is minimum (in magnitude) becomes the support if

$\min_{j\in
T}|x_{j}|>\frac{2(1-\delta_{K})}{1-3\delta_{2K}}\|\mathbf{v}\|_{2}.$ (25)

In other words, $\|\mathbf{r}_{T}\|_{2}<\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}$
for any $\bar{s}_{1}^{K}\neq T$ under (25).

###### Proof:

One can notice that the hypothesis is satisfied if the upper bound of
$\|\mathbf{r}_{T}\|_{2}$ is smaller than the lower bound of
$\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}$. First, we obtain the upper bound of
$\|\mathbf{r}_{T}\|_{2}$ as

$\displaystyle\|\mathbf{r}_{T}\|_{2}$ $\displaystyle=$
$\displaystyle\|\mathbf{P}_{T}^{\bot}\mathbf{y}\|_{2}$ (26) $\displaystyle=$
$\displaystyle\|\mathbf{P}_{T}^{\bot}\left(\mathbf{\Phi}_{T}\mathbf{x}_{T}+\mathbf{v}\right)\|_{2}$
$\displaystyle=$ $\displaystyle\|\mathbf{P}_{T}^{\bot}\mathbf{v}\|_{2}$
$\displaystyle\leq$ $\displaystyle\|\mathbf{v}\|_{2}$

where
$\mathbf{P}_{T}^{\bot}=\mathbf{I}-\mathbf{\Phi}_{T}\left(\mathbf{\Phi}_{T}^{\prime}\mathbf{\Phi}_{T}\right)^{-1}\mathbf{\Phi}_{T}^{\prime}$
is the projection onto the orthogonal complement of $T$ and (26) is because
$\mathbf{P}_{T}^{\bot}\mathbf{\Phi}_{T}\mathbf{x}_{T}=\mathbf{0}$.

Next, we obtain the lower bound of $\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}$. For
any $\bar{s}_{1}^{K}\neq T$, we have

$\displaystyle\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}$ $\displaystyle=$
$\displaystyle\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{y}\|_{2}$ (27)
$\displaystyle=$
$\displaystyle\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}(\mathbf{\Phi
x}+\mathbf{v})\|_{2}$ $\displaystyle=$
$\displaystyle\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}(\mathbf{\Phi}_{\bar{s}_{1}^{K}}\mathbf{x}_{\bar{s}_{1}^{K}}+\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}+\mathbf{v})\|_{2}$
$\displaystyle=$
$\displaystyle\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}(\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}+\mathbf{v})\|_{2}$
$\displaystyle\geq$
$\displaystyle\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}-\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{v}\|_{2}$
(28)

where the inequality in (27) is because
$\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{x}_{\bar{s}_{1}^{K}}^{\bot}=\mathbf{0}$
and the inequality in (28) is due to the triangle inequality. The first term
in the right-hand side of (28) is lower bounded as

$\displaystyle\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle=$
$\displaystyle\|(\mathbf{I}-\mathbf{\Phi}_{\bar{s}_{1}^{K}}(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime})\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(30) $\displaystyle\geq$
$\displaystyle\|\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}-\|\mathbf{\Phi}_{\bar{s}_{1}^{K}}(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{|T\setminus\bar{s}_{1}^{K}|}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle-\sqrt{1+\delta_{|\bar{s}_{1}^{K}|}}\|(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{|T\setminus\bar{s}_{1}^{K}|}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}-\frac{\sqrt{1+\delta_{|\bar{s}_{1}^{K}|}}}{1-\delta_{|\bar{s}_{1}^{K}|}}\|\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(31) $\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{|T\setminus\bar{s}_{1}^{K}|}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}-\frac{\sqrt{1+\delta_{|\bar{s}_{1}^{K}|}}\delta_{K+|T\setminus\bar{s}_{1}^{K}|}}{1-\delta_{|\bar{s}_{1}^{K}|}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(32) $\displaystyle>$
$\displaystyle\sqrt{1-\delta_{2K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}-\frac{\sqrt{1+\delta_{K}}\delta_{2K}}{1-\delta_{K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(33)

where (30) is from Definition III.1, (31) is from from Lemma III.3, and (32)
and (33) are from Lemma III.4 and III.2, respectively. Using this together
with
$\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{v}\|_{2}\leq\|\mathbf{v}\|_{2}$,
we have

$\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}>\sqrt{1-\delta_{2K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}-\frac{\sqrt{1+\delta_{K}}\delta_{2K}}{1-\delta_{K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}-\|\mathbf{v}\|_{2}.$
(34)

for any $\bar{s}_{1}^{K}\neq T$. Since
$\|\mathbf{r}_{T}\|_{2}<\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}$ always holds if
the upper bound of $\|\mathbf{r}_{T}\|_{2}$ is smaller than the lower bound of
$\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}$, it is clear from (26) and (34) that
the hypothesis is satisfied under

$\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}>\frac{2(1-\delta_{K})}{1-3\delta_{2K}}\|\mathbf{v}\|_{2}.$
(35)

Noting that
$\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}\geq\mathop{\min}\limits_{j\in
T}|x_{j}|$, we get the desired result. ∎

Thus far, we investigated the condition under which the noncausal set is true
when the causal path is true (Lemma III.15) and the condition ensuring that
the true path has the minimum residual (in magnitude) and hence survives
during the tree pruning (Lemma III.16). Recalling that the pruning threshold
is updated by the minimum value of the residual (in magnitude) in each layer
($\epsilon=\min\|\mathbf{r}_{\bar{s}_{1}^{K}}\|_{2}$) and a path whose
residual magnitude is larger than $\epsilon$ is pruned, the support $T$ will
never be pruned if the conditions of Lemma III.15 and III.16 are jointly
satisfied. Formal description of our findings is as follows.

###### Theorem III.17

The true path $\hat{s}_{1}^{i}\subset T$ survives in the pruning process for
any $i$ under

$\displaystyle\min_{j\in T}|x_{j}|>\max(\mu,\omega)\|\mathbf{v}\|_{2}$ (36)

where $\mu=\frac{2(1-\delta_{K})}{1-3\delta_{2K}}$ and
$\omega=\frac{2(1-\delta_{K})\sqrt{1+\delta_{M}}}{1-\delta_{K}-\delta_{K+1}-\delta_{M}}$.

###### Proof:

Immediate from Lemma III.15 and III.16. ∎

By combining the results of pre-selection (Theorem III.12) and tree search
(Theorem III.17), we obtain the main result for the noisy setting.

###### Theorem III.18

The TMP algorithm accurately identifies the support from the noisy measurement
$\mathbf{y}=\mathbf{\Phi}\mathbf{x}+\mathbf{v}$ under

$\displaystyle\min_{j\in T}|x_{j}|>\gamma\|\mathbf{v}\|_{2}$ (37)

$\gamma=\max(\nu,\mu,\omega)$ and
$\mu=\frac{2(1-\delta_{K})}{1-3\delta_{2K}}$,
$\omega=\frac{2(1-\delta_{K})\sqrt{1+\delta_{M}}}{1-\delta_{K}-\delta_{K+1}-\delta_{M}}$,
and
$\nu=\frac{(\sqrt{K}+\sqrt{L})\sqrt{1+\delta_{L+K}}\|\mathbf{v}\|_{2}}{\sqrt{L}(1-\delta_{K})-\sqrt{K}\delta_{L+K}}$.

###### Proof:

Immediate from Theorem III.12 and III.17. ∎

It is worth noting that under (37), which essentially corresponds to the high
signal-to-noise ratio (SNR) regime, we can identify the exact support
information so that we can simply remove all non-support elements (zero
entries in $\mathbf{x}$) and columns associated with these from the system
model. In doing so, we can obtain the overdetermined system
$\mathbf{y}=\mathbf{\Phi}_{T}\mathbf{x}_{T}+\mathbf{v}$ and the reconstructed
signal becomes equivalent to the output of the best possible estimator
referred to as Oracle estimator
$\hat{\mathbf{x}}=\mathbf{\Phi}^{\dagger}_{T}\mathbf{y}$.

Using the part of analysis we obtained, we can also show the stability of the
TMP algorithm. By stability, we mean that the $\ell_{2}$-norm of the
estimation error
$\|\mathbf{x}-\hat{\mathbf{x}}_{\bar{s}_{1}^{K}}\|_{2}=\|\mathbf{x}-\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\dagger}\mathbf{y}\|_{2}$
is upper bounded by the constant multiple of the noise power.

###### Theorem III.19

The output $\hat{\mathbf{x}}_{\bar{s}_{1}^{K}}$ of the TMP algorithm satisfies

$\displaystyle\left\|\mathbf{x}-\hat{\mathbf{x}}_{\bar{s}_{1}^{K}}\right\|_{2}<\tau\|\mathbf{v}\|_{2}$
(38)

where
$\tau=\frac{(\gamma+1)(1-\delta_{K})+2\gamma\delta_{2K}}{(1-\delta_{K})\sqrt{1-\delta_{2K}}}$.

###### Proof:

From Definition III.1, it is clear that

$\displaystyle\|\mathbf{x}-\hat{\mathbf{x}}_{\bar{s}_{1}^{K}}\|_{2}\leq\frac{\|\mathbf{\Phi}(\mathbf{x}-\hat{\mathbf{x}}_{\bar{s}_{1}^{K}})\|_{2}}{\sqrt{1-\delta_{|T\cup\bar{s}_{1}^{K}|}}}.$
(39)

Since $\mathbf{x}-\hat{\mathbf{x}}$ is at most $2K$-sparse, we further have

$\displaystyle\|\mathbf{x}-\hat{\mathbf{x}}_{\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle\leq$
$\displaystyle\frac{\|\mathbf{\Phi}(\mathbf{x}-\hat{\mathbf{x}}_{\bar{s}_{1}^{K}})\|_{2}}{\sqrt{1-\delta_{|T\cup\bar{s}_{1}^{K}|}}}$
(40) $\displaystyle=$
$\displaystyle\frac{\|\mathbf{\Phi}(\mathbf{x}-(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{y})\|_{2}}{\sqrt{1-\delta_{2K}}}$
$\displaystyle=$
$\displaystyle\frac{\|\mathbf{\Phi}\mathbf{x}-\mathbf{\Phi}_{\bar{s}_{1}^{K}}(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}(\mathbf{\Phi
x}+\mathbf{v})\|_{2}}{\sqrt{1-\delta_{2K}}}$ $\displaystyle=$
$\displaystyle\frac{\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}-\mathbf{P}_{\bar{s}_{1}^{K}}\mathbf{v}\|_{2}}{\sqrt{1-\delta_{2K}}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}+\|\mathbf{P}_{\bar{s}_{1}^{K}}\mathbf{v}\|_{2}}{\sqrt{1-\delta_{2K}}}$
$\displaystyle\leq$
$\displaystyle\frac{\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}+\|\mathbf{v}\|_{2}}{\sqrt{1-\delta_{2K}}}$

where
$\mathbf{P}_{\bar{s}_{1}^{K}}=\mathbf{\Phi}_{\bar{s}_{1}^{K}}(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}$.
Also,

$\displaystyle\|\mathbf{P}_{\bar{s}_{1}^{K}}^{\bot}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle=$
$\displaystyle\|(\mathbf{I}-\mathbf{\Phi}_{\bar{s}_{1}^{K}}(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime})\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(42) $\displaystyle\leq$
$\displaystyle\|\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}+\|\mathbf{\Phi}_{\bar{s}_{1}^{K}}(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle\leq$
$\displaystyle\sqrt{1+\delta_{|T\setminus\bar{s}_{1}^{K}|}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle+\sqrt{1+\delta_{|\bar{s}_{1}^{K}|}}\|(\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{\bar{s}_{1}^{K}})^{-1}\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
$\displaystyle\leq$
$\displaystyle\sqrt{1+\delta_{|T\setminus\bar{s}_{1}^{K}|}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}+\frac{\sqrt{1+\delta_{|\bar{s}_{1}^{K}|}}}{1-\delta_{|\bar{s}_{1}^{K}|}}\|\mathbf{\Phi}_{\bar{s}_{1}^{K}}^{\prime}\mathbf{\Phi}_{T\setminus\bar{s}_{1}^{K}}\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(43) $\displaystyle\leq$
$\displaystyle\sqrt{1+\delta_{|T\setminus\bar{s}_{1}^{K}|}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}+\frac{\sqrt{1+\delta_{|\bar{s}_{1}^{K}|}}\delta_{K+|T\setminus\bar{s}_{1}^{K}|}}{1-\delta_{|\bar{s}_{1}^{K}|}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(44) $\displaystyle\leq$
$\displaystyle\sqrt{1+\delta_{K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}+\frac{\sqrt{1+\delta_{K}}\delta_{2K}}{1-\delta_{K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(45) $\displaystyle<$
$\displaystyle\sqrt{1+\delta_{2K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}+\frac{\sqrt{1+\delta_{K}}\delta_{2K}}{1-\delta_{K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(46) $\displaystyle<$
$\displaystyle\frac{1-\delta_{K}+2\delta_{2K}}{1-\delta_{K}}\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}$
(47)

where (42) is from Definition III.1, and (43) and (44) are from Lemma III.3
and III.4, respectively. Plugging (47) into (40), we have

$\displaystyle\|\mathbf{x}-\hat{\mathbf{x}}_{\bar{s}_{1}^{K}}\|_{2}<\frac{(1-\delta_{K}+2\delta_{2K})\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}}{(1-\delta_{K})\sqrt{1-\delta_{2K}}}+\frac{\|\mathbf{v}\|_{2}}{\sqrt{1-\delta_{2K}}}.$
(48)

Note that when the support is chosen accurately, $\bar{s}_{1}^{K}=T$ and thus

$\displaystyle\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}=0.$ (49)

Whereas, if $\bar{s}_{1}^{K}\neq T$, then by the contraposition of Theorem
III.18666Here, we need to use slightly modified version of Theorem III.18,
which says that if
$\|\mathbf{x}_{\bar{s}_{1}^{K}}\|_{2}>\gamma\|\mathbf{v}\|_{2}$, then
$\bar{s}_{1}^{K}=T$., we have

$\displaystyle\|\mathbf{x}_{T\setminus\bar{s}_{1}^{K}}\|_{2}\leq\gamma\|\mathbf{v}\|_{2}.$
(50)

for any $\bar{s}_{1}^{K}\neq T$. By combining (49) and (50), we obtain the
desired result. ∎

##  IV Simulation and Discussions

###  IV-A Simulation Setup

In this section, we observe the performance of sparse recovery algorithms
including TMP through empirical simulations. In our simulations, we generate
$K$-sparse vector $\mathbf{x}$ whose nonzero locations and coefficients are
randomly chosen and the sensing matrix $\mathbf{\Phi}$ of size $100\times 256$
whose entries are from the independent Gaussian distribution
$\mathcal{N}(0,\frac{1}{M})$. In each point of the individual recovery
algorithm, we perform at least $n=5,000$ independent trials. In the noiseless
setting, we use the exact recovery ratio (ERR) as a performance measure. In
the noisy setting, we use the mean squared error (MSE) of the recovery
algorithms which is defined as

$MSE=\frac{1}{n}\mathop{\sum}\limits_{\ell=1}^{n}\frac{\|\mathbf{x}(\ell)-\hat{\mathbf{x}}(\ell)\|^{2}}{N}$

where $\hat{\mathbf{x}}(\ell)$ is the estimate of the original sparse signal
$\mathbf{x}(\ell)$.

We test simulations on the following algorithms:

  1. 1.

OMP algorithm [7]

  2. 2.

BP algorithm [5]: we use BP in noiseless setting and basis pursuit denoising
(BPDN) in noisy setting.

  3. 3.

CoSaMP algorithm [9]: we set the maximal number of iterations to $40$.

  4. 4.

gOMP algorithm [17]: we choose two indices ($L=2$) in each iteration.

  5. 5.

TMP: we use gOMP ($L=2$) in the pre-selection stage.

  6. 6.

TMP with limited branching: we set the maximum number of branches in each
layer ($N_{\max}=10$ and $100$).

###  IV-B Simulation Results

Figure 5: ERR performance as a function of the sparsity $K$ in the noiseless
setting. We measure the performance before the tree search (pre-selection) and
after the tree search (TMP).

We first compare the ERR performance of sparse recovery algorithms in the
noiseless setting. Main purpose of this simulation is to observe how much
performance gain can be achieved by the tree search. Since we use the
conventional sparse recovery algorithm in the pre-selection process,
effectiveness of the proposed TMP algorithm can be checked by comparing the
recovery performance before the tree search (pre-selection only) and after the
tree search.

Figure 6: MSE performance of sparse recovery algorithms ($K=20$) in $100\times
256$ system.

In Fig. 5, we plot the ERR of TMP with various pre-selection algorithms as a
function of the sparsity $K$. Overall, we observe that the addition of tree
search process provides substantial gain in performance. In particular, when
$K$ is large, performance gain obtained by the tree search stage is
noticeable. When OMP is used as a pre-selection algorithm, for example, the
ERR of TMP before and after the tree search at $K=35$ are $0.23$ and $0.89$,
respectively.

In Fig. 6, we plot the MSE performance of the sparse recovery algorithms as a
function of signal-to-noise ratio (SNR) in the noisy setting. Note that the
decibel (dB) scale of SNR is defined as
$\mbox{SNR}=10\log_{10}\frac{\|\mathbf{\Phi x}\|^{2}}{\|\mathbf{v}\|^{2}}$. In
this test, we set the sparsity level to $K=20$ so that $8\%$ of entries in the
input vector are nonzero. Overall, we observe that the performance gain of TMP
improves with SNR. While the performance gap between the conventional sparse
recovery algorithms and Oracle estimator is maintained across the board, the
performance gap between TMP and Oracle estimator gets smaller as SNR
increases.

Figure 7: MSE performance of sparse recovery algorithms in the noisy setting
($K=30$).

In Fig. 7, a similar simulation as before but with large $K$ is performed. In
this simulation, we set $K=30$ so that $12\%$ of entries are nonzero. In this
case, we clearly see that TMP outperforms conventional sparse recovery
algorithms and the performance gain improves with SNR. For example, the gain
at $MSE=10^{-2}$ is around $2$ dB but the gain at $MSE=10^{-3}$ is more than
$10$ dB. Also, as it can be seen from the figure and also in accordance with
Theorem III.18, the performance of TMP is asymptotically optimal in high SNR
regime in the sense that it approaches the MSE performance of Oracle
estimator.

Figure 8: Average running time of sparse signal recovery algorithms in
$100\times 256$ system.

Fig. 8 shows the running time complexity of the sparse recovery algorithms as
a function of the sparsity level $K$. All algorithms under test are coded by
MATLAB software package and run by a personal computer with Intel Core i$5$
processor and Microsoft Windows $7$ environment. As seen in the figure, among
greedy algorithms under test, OMP exhibits the smallest running time. Since
TMP performs tree search to investigate multiple promising paths, it is no
wonder that the running time complexity of TMP is higher than the rest of
greedy algorithms. However, by limiting the number of branching operations,
computational burden of TMP can be reduced dramatically. Due to the reduction
in number of investigated paths, we can observe that the running time
complexity of TMP with limited branching is much smaller than that without
limitation. In particular, if $N_{\max}=10$, TMP achieves two order of
magnitude reduction over the original TMP algorithm with only slight loss in
performance.

##  V Conclusions

In this paper, we proposed a tree search based sparse signal recovery
algorithm referred to as matching pursuit with a tree pruning (TMP). In order
to overcome the shortcoming of greedy algorithm in choosing short-sighted
candidates, the TMP algorithm performs the tree search and investigates
multiple promising candidates. The complexity overhead caused by the tree
search is controlled by the pre-selection and tree pruning. In our empirical
simulation, we observed that TMP provides excellent recovery performance in
both noiseless and noisy scenarios. While TMP is promising algorithm in terms
of the recovery performance, its complexity is a bit higher than existing
greedy algorithms and further study is needed. Our future work will address
the complexity reduction issue of greedy tree search algorithm to achieve
better tradeoff between complexity and performance.

##  Appendix A Proof of Lemma III.6

Let $\hat{s}_{1}^{i}\subset T$ and $\lambda^{i}=\mathop{\min}\limits_{j\in
T\setminus\hat{s}_{1}^{i}}|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$,
then by using the triangular inequality, we have

$\displaystyle|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}\|_{2}$ (51)
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{y}\|_{2}$
(52) $\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(53) $\displaystyle\geq$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(54)

where
$\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}=\mathbf{I}-\mathbf{\Phi}_{\hat{s}_{1}^{i}}(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}$.
From Definition III.1, we have

$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
$\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{M}}\|\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(55) $\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{M}}\sqrt{1-\delta_{|T\setminus\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}.$
(56)

Also,

$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}}(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(57) $\displaystyle\geq$
$\displaystyle\delta_{|\hat{s}_{1}^{i}|+1}\|(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(58) $\displaystyle\geq$
$\displaystyle\frac{\delta_{|\hat{s}_{1}^{i}|+1}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(59) $\displaystyle\geq$
$\displaystyle\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(60)

where (56) is from Definition III.1, (55) and (60) are from Lemma III.4, and
(59) is from Lemma III.3. Using (54), (56), and (60), we have

$\displaystyle|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
$\displaystyle\geq$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(61) $\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{M}}\sqrt{1-\delta_{|T\setminus\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}.$

Since (61) holds for any $j\in T\setminus\hat{s}_{1}^{i}$ and $0\leq i\leq K$,
we have

$\displaystyle\lambda^{i}$ $\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{M}}\sqrt{1-\delta_{|T\setminus\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(62) $\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{M}}\sqrt{1-\delta_{M}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\frac{\delta_{K+1}\delta_{K}}{1-\delta_{K}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(63) $\displaystyle\geq$
$\displaystyle\left(1-\delta_{M}-\frac{\delta_{M}\delta_{K}}{1-\delta_{K}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(64) $\displaystyle=$
$\displaystyle\frac{1-\delta_{K}-\delta_{M}}{1-\delta_{K}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2},$
(65)

which is the desired result.

##  Appendix B Proof of Lemma III.7

Let $\hat{s}_{1}^{i}\subset T$ and $\gamma^{i}=\mathop{\max}\limits_{j\in
T^{c}}|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$, then by using the
triangle inequality, we have

$\displaystyle|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}\|_{2}$ (66)
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{y}\|_{2}$
(67) $\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(68) $\displaystyle\leq$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}.$
(69)

Since $j\in T^{c}$, we have

$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
$\displaystyle\leq$
$\displaystyle\delta_{|T\setminus\hat{s}_{1}^{i}|+1}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(70)

where (70) is from Lemma III.4. Also,

$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}}(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(71) $\displaystyle\leq$
$\displaystyle\delta_{|\hat{s}_{1}^{i}|+1}\|(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(72) $\displaystyle\leq$
$\displaystyle\frac{\delta_{|\hat{s}_{1}^{i}|+1}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(73) $\displaystyle\leq$
$\displaystyle\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(74)

where (72) and (74) are from Lemma III.4 and (73) is from Lemma III.3. Using
(69), (70), and (74), we have

$\displaystyle|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
$\displaystyle\leq$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(75) $\displaystyle\leq$
$\displaystyle\left(\delta_{|T\setminus\hat{s}_{1}^{i}|+1}+\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(76) $\displaystyle\leq$
$\displaystyle\left(\delta_{K+1}+\frac{\delta_{K+1}\delta_{K}}{1-\delta_{K}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(77) $\displaystyle=$
$\displaystyle\frac{\delta_{K+1}}{1-\delta_{K}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2},$
(78)

which is the desired result.

##  Appendix C Proof of Lemma III.10

From the definition of $\rho$ in (III-B), we have

$\displaystyle\rho$ $\displaystyle=$ $\displaystyle\max_{j\in
T}|\phi_{j}^{\prime}\mathbf{y}|$ (79) $\displaystyle=$
$\displaystyle\|\mathbf{\Phi}_{T}^{\prime}\mathbf{y}\|_{\infty}$ (80)
$\displaystyle\geq$
$\displaystyle\frac{1}{\sqrt{|T|}}\|\mathbf{\Phi}_{T}^{\prime}\mathbf{y}\|_{2}$
(81) $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{K}}\|\mathbf{\Phi}_{T}^{\prime}(\mathbf{\Phi}_{T}\mathbf{x}_{T}+\mathbf{v})\|_{2}$
(82) $\displaystyle\geq$
$\displaystyle\frac{1}{\sqrt{K}}\left(\|\mathbf{\Phi}_{T}^{\prime}\mathbf{\Phi}_{T}\mathbf{x}_{T}\|_{2}-\|\mathbf{\Phi}_{T}^{\prime}\mathbf{v}\|_{2}\right)\\!$
(83)

where (81) is from the inequality
$\|\mathbf{u}\|_{\infty}\geq\frac{1}{\sqrt{\|\mathbf{u}\|_{0}}}\|\mathbf{u}\|_{2}$
for any vector $\mathbf{u}$. Note that

$\displaystyle\|\mathbf{\Phi}_{T}^{\prime}\mathbf{\Phi}_{T}\mathbf{x}_{T}\|_{2}\geq(1-\delta_{K})\|\mathbf{x}_{T}\|_{2}$
(84)

and

$\displaystyle\|\mathbf{\Phi}_{T}^{\prime}\mathbf{v}\|_{2}\leq\sqrt{1+\delta_{K}}\|\mathbf{v}\|_{2}$
(85)

and thus $\rho$ is lower bounded as

$\displaystyle\rho\geq\frac{1}{\sqrt{K}}\left[(1-\delta_{K})\|\mathbf{x}_{T}\|_{2}-\sqrt{1+\delta_{K}}\|\mathbf{v}\|_{2}\right],$
(86)

which is the desired result.

##  Appendix D Proof of Lemma III.11

From the definition of $\eta$ in (III-B), we have

$\displaystyle\sqrt{L}\eta\leq\sqrt{\sum_{j\in
I_{L}}|\phi_{j}^{\prime}\mathbf{y}|^{2}}=\|\mathbf{\Phi}_{I_{L}}^{\prime}\mathbf{y}\|_{2}$
(87)

where $I_{L}=\arg\mathop{\max}\limits_{|I|=L,I\subset
T^{c}}\|\mathbf{\Phi}_{I}^{\prime}\mathbf{y}\|_{2}$. Using the triangle
inequality, we have

$\displaystyle\|\mathbf{\Phi}_{I_{L}}^{\prime}\mathbf{y}\|_{2}$
$\displaystyle=$
$\displaystyle\|\mathbf{\Phi}_{I_{L}}^{\prime}(\mathbf{\Phi}_{T}\mathbf{x}_{T}+\mathbf{v})\|_{2}$
(88) $\displaystyle\leq$
$\displaystyle\|\mathbf{\Phi}_{I_{L}}^{\prime}\mathbf{\Phi}_{T}\mathbf{x}_{T}\|_{2}+\|\mathbf{\Phi}_{I_{L}}^{\prime}\mathbf{v}\|_{2}.$
(89)

Since $I_{L}$ and $T$ are disjoint ($I_{L}\subset T^{c}$), we have

$\displaystyle\|\mathbf{\Phi}_{I_{L}}^{\prime}\mathbf{\Phi}_{T}\mathbf{x}_{T}\|_{2}\leq\delta_{L+K}\|\mathbf{x}_{T}\|_{2}$
(90)

and

$\displaystyle\|\mathbf{\Phi}_{I_{L}}^{\prime}\mathbf{v}\|_{2}$
$\displaystyle\leq$ $\displaystyle\sqrt{1+\delta_{L}}\|\mathbf{v}\|_{2}.$ (91)

Using (90) and (91), we have

$\displaystyle\|\mathbf{\Phi}_{I_{L}}^{\prime}\mathbf{y}\|_{2}\leq\delta_{L+K}\|\mathbf{x}_{T}\|_{2}+\sqrt{1+\delta_{L}}\|\mathbf{v}\|_{2}$
(92)

and since $\|\mathbf{\Phi}_{I_{L}}^{\prime}\mathbf{y}\|_{2}\geq\sqrt{L}\eta$,
we have

$\displaystyle\eta\leq\frac{1}{\sqrt{L}}\left[\delta_{L+K}\|\mathbf{x}_{T}\|_{2}+\sqrt{1+\delta_{L}}\|\mathbf{v}\|_{2}\right],$
(93)

which is the desired result.

##  Appendix E Proof of Lemma III.13

Suppose $\hat{s}_{1}^{i}\subset T$ and $\beta^{i}=\mathop{\min}\limits_{j\in
T\setminus\hat{s}_{1}^{i}}|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$,
then

$\displaystyle|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}\|_{2}$ (94)
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{y}\|_{2}=\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}(\mathbf{\Phi}_{T}\mathbf{x}_{T}+\mathbf{v})\|_{2}$
(95) $\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}+\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(96) $\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}-\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}+\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(97) $\displaystyle\geq$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}.$
(98)

where (94) is because
$\|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}\|_{2}=\sqrt{|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|^{2}}=|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
and (98) is from the triangle inequality. Since (98) is satisfied for any
$j\in T\setminus\hat{s}_{1}^{i}$, we have

$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
$\displaystyle\geq$
$\displaystyle\sqrt{1-\delta_{M}}\sqrt{1-\delta_{|T\setminus\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2},$
(99)
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}}(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(100) $\displaystyle\leq$
$\displaystyle\delta_{|\hat{s}_{1}^{i}|+1}\|(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(101) $\displaystyle\leq$
$\displaystyle\frac{\delta_{|\hat{s}_{1}^{i}|+1}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(102) $\displaystyle\leq$
$\displaystyle\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(103)

and

$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
$\displaystyle\leq$
$\displaystyle\sqrt{1+\delta_{M}}\|\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(104) $\displaystyle\leq$
$\displaystyle\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}.$ (105)

where (99) and (104) are from Definition III.1, (101) and (103) are from Lemma
III.4, and (102) is from Lemma III.3. Finally, since (98) is satisfied for any
$j\in T\setminus\hat{s}_{1}^{i}$, we have

$\displaystyle\beta^{i}$ $\displaystyle=$
$\displaystyle\mathop{\min}\limits_{j\in
T\setminus\hat{s}_{1}^{i}}|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
(106) $\displaystyle\geq$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(107) $\displaystyle\geq$
$\displaystyle\left(\sqrt{1-\delta_{M}}\sqrt{1-\delta_{|T\setminus\hat{s}_{1}^{i}|}}-\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}$
(108) $\displaystyle\geq$
$\displaystyle\left(1-\delta_{M}-\frac{\delta_{K+1}\delta_{K}}{1-\delta_{K}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}-\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}$
(109)

where (109) is from Lemma III.2.

##  Appendix F Proof of Lemma III.14

Suppose $\hat{s}_{1}^{i}\subset T$ and let
$\alpha^{i}=\mathop{\max}\limits_{j\in
T^{c}}|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$, then

$\displaystyle|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}\|_{2}$ (110)
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{y}\|_{2}=\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}(\mathbf{\Phi}_{T}\mathbf{x}_{T}+\mathbf{v})\|_{2}$
(111) $\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}+\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(112) $\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}-\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}+\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(113) $\displaystyle\leq$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(114)

where (110) is because
$\|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}\|_{2}=\sqrt{|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|^{2}}=|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$,
$\mathbf{P}_{\hat{s}_{1}^{i}}=\mathbf{\Phi}_{\hat{s}_{1}^{i}}(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}$
in (113),
$\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}=\mathbf{I}-\mathbf{P}_{\hat{s}_{1}^{i}}$,
and (114) follows the triangle inequality. Since $j\in T^{c}$, we have

$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
$\displaystyle\leq$
$\displaystyle\delta_{|T\setminus\hat{s}_{1}^{i}|+1}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2},$
(115)
$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
$\displaystyle=$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}}(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(116) $\displaystyle\leq$
$\displaystyle\delta_{|\hat{s}_{1}^{i}|+1}\|(\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{\hat{s}_{1}^{i}})^{-1}\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(117) $\displaystyle\leq$
$\displaystyle\frac{\delta_{|\hat{s}_{1}^{i}|+1}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{\Phi}_{\hat{s}_{1}^{i}}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}$
(118) $\displaystyle\leq$
$\displaystyle\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}.$
(119)

Also,

$\displaystyle\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
$\displaystyle=$
$\displaystyle\sqrt{1+\delta_{M}}\|\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(120) $\displaystyle=$ $\displaystyle\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}.$
(121)

Using (115), (119), and (121), we have

$\displaystyle|\phi_{j}^{\prime}\mathbf{r}_{\hat{s}_{1}^{i}}|$
$\displaystyle\leq$
$\displaystyle\|\phi_{j}^{\prime}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}\mathbf{\Phi}_{T\setminus\hat{s}_{1}^{i}}\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\|\phi_{j}^{\prime}\mathbf{P}_{\hat{s}_{1}^{i}}^{\bot}\mathbf{v}\|_{2}$
(122) $\displaystyle\leq$
$\displaystyle\left(\delta_{|T\setminus\hat{s}_{1}^{i}|+1}+\frac{\delta_{|\hat{s}_{1}^{i}|+1}\delta_{K}}{1-\delta_{|\hat{s}_{1}^{i}|}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}$
(123) $\displaystyle\leq$
$\displaystyle\left(\delta_{K+1}+\frac{\delta_{K+1}\delta_{K}}{1-\delta_{K}}\right)\|\mathbf{x}_{T\setminus\hat{s}_{1}^{i}}\|_{2}+\sqrt{1+\delta_{M}}\|\mathbf{v}\|_{2}.$
(124)

## References

  * [1] E. J. Candes, J. Romberg, and T. Tao,  “Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information,”  IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 489–509, Feb. 2006\.
  * [2] E. J. Candes and T. Tao,  “Decoding by linear programming,”  IEEE Trans. Inf. Theory, vol. 51, no. 12, pp. 4203–4215, Dec. 2005.
  * [3] E. Liu and V. N. Temlyakov,  “The orthogonal super greedy algorithm and applications in compressed sensing,”  IEEE Trans. Inf. Theory, vol. 58, no. 4, pp. 2040–2047, April 2012.
  * [4] E. J. Candes,  “The restricted isometry property and its implications for compressed sensing,”  Comptes Rendus Mathematique, vol. 346, no. 9-10, pp. 589–592, May 2008.
  * [5] R. Tibshirani,  “Regression shrinkage and selection via the lasso,”  J. Royal Stat. Soc. Series B, vol. 58, no. 1, pp. 267–288, 1996\.
  * [6] E. Candes and T. Tao,  “The Dantzig selector: statistical estimation when p is much larger than n,”  The Annal. Stat., vol. 35, no. 6, pp. 2313–2351, Dec. 2007.
  * [7] T. Tony Cai and L. Wang,  “Orthogonal matching pursuit for sparse signal recovery with noise,”  IEEE Trans. Inf. Theory, vol. 57, no. 7, pp. 4680–4688, July 2011\.
  * [8] J. Wang and B. Shim,  “On the recovery limit of sparse signals using orthogonal matching pursuit,”  IEEE Trans. Signal Process., vol. 60, no. 9, pp. 4973–4976, Sept. 2012.
  * [9] D. Needell and J. A. Tropp,  “CoSaMP: iterative signal recovery from incomplete and inaccurate samples,”  Commun. ACM, vol. 53, no. 12, pp. 93–100, Dec. 2010.
  * [10] W. Dai and O. Milenkovic,  “Subspace pursuit for compressive sensing signal reconstruction,”  IEEE Trans. Inf. Theory, vol. 55, no. 5, pp. 2230–2249, May 2009\.
  * [11] M. Raginsky, R. M. Willett, Z. T. Harmany, and R. F. Marcia,  “Compressed sensing performance bounds under poisson noise,”  IEEE Trans. Signal Process., vol. 58, no. 8, pp. 3990–4002, Aug. 2010.
  * [12] K. Gao, S. N. Batalama, D. A. Pados, and B. W. Suter,  “Compressive sampling with generalized polygons,”  IEEE Trans. Signal Process., vol. 59, no. 10, pp. 4759–4766, Oct. 2011.
  * [13] M. A. Khajehnejad, A. G. Dimakis, W. Xu, and B. Hassibi,  “Sparse recovery of nonnegative signals with minimal expansion,”  IEEE Trans. Signal Process., vol. 59, no. 1, pp. 196–208, Jan. 2011\.
  * [14] S. S. Chen, D. L. Donoho, and Michael A. Saunders,  “Atomic decomposition by basis pursuit,”  SIAM Journal on Scientific Computing, vol. 20, no. 1, pp. 33–61, 1998.
  * [15] W. Chen, M. R. D. Rodrigues, and I. J. Wassell,  “Projection design for statistical compressive sensing: A tight frame based approach,”  IEEE Trans. Signal Process., vol. 61, no. 8, pp. 2016–2029, April 2013.
  * [16] T. Zhang,  “Sparse recovery with orthogonal matching pursuit under rip,”  IEEE Trans. Inf. Theory, vol. 57, no. 9, pp. 6215–6221, Sept. 2011.
  * [17] J. Wang, S. Kwon, and B. Shim,  “Generalized orthogonal matching pursuit,”  IEEE Trans. Signal Process., vol. 60, no. 12, pp. 6202–6216, Dec. 2012.
  * [18] G. D. Forney Jr.,  “The Viterbi algorithm,”  Proceedings of the IEEE, vol. 61, no. 3, pp. 268–278, March 1973\.
  * [19] E. Viterbo and J. Boutros,  “A universal lattice code decoder for fading channels,”  IEEE Trans. Inf. Theory, vol. 45, no. 5, pp. 1639–1642, July 1999\.
  * [20] B. Shim and I. Kang,  “Sphere decoding with a probabilistic tree pruning,”  IEEE Trans. Signal Process., vol. 56, no. 10, pp. 4867–4878, Oct. 2008.