# Dynamic Orthogonal Matching Pursuit for Sparse Data Reconstruction††thanks:
MSC2010 Subject Classification: Primary: 90C25, 90C26, 90C30, 65K05;
secondary: 68T09, 68T10, 94A12, 94A16

Yun-Bin Zhao and Zhi-Quan Luo Shenzhen Research Institute of Big Data, Chinese
University of Hong Kong, Shenzhen, Guangdong Province, China (Email:
yunbinzhao@cuhk.edu.cn). The study of this author was supported by the
National Natural Science Foundation of China (NSFC) under Grant 12071307. Part
of the work was done while the author worked at the School of Mathematics,
University of Birmingham, Birmingham B15 2TT, United Kingdom.Shenzhen Research
Institute of Big Data, Chinese University of Hong Kong, Shenzhen, Guangdong
Province, China (Email: luozq@cuhk.edu.cn). The work of this author was
supported by the National Natural Science Foundation of China (NSFC) under
Grants 61571384 and 61731018.

Abstract. The orthogonal matching pursuit (OMP) is one of the mainstream
algorithms for sparse data reconstruction or approximation. It acts as a
driving force for the development of several other greedy methods for sparse
data reconstruction, and it also plays a vital role in the development of
compressed sensing theory for sparse signal and image reconstruction. In this
paper, we propose the so-called dynamic orthogonal matching pursuit (DOMP)
algorithm and an enhanced version of this method which are more efficient than
the OMP algorithm for sparse data reconstruction from a numerical point of
view. We perform a rigorous analysis and establish the reconstruction error
bounds for the two algorithms in terms of the restricted isometry property of
the measurement matrix. The main results claim that the reconstruction error
via the two algorithms can be controlled and measured in terms of the number
of iterations, sparsity level of data, and the noise level of measurements.
Moveover, the finite convergence of the proposed algorithms for a class of
large-scale compressed sensing problems is also shown.

Key words. Sparse optimization, data reconstruction, error bound, orthogonal
matching pursuit, dynamic orthogonal matching pursuit, restricted isometry
property

##  1 Introduction

Data reconstruction/recovery is a common request in various information
processing such as signal denoising, imaging reconstruction, statistical model
selection, pattern recognition, streaming data tracking, wireless channel
estimation, and so on (see, e.g., [18, 19, 21, 3, 26]). For instance,
reconstruction of a sparse signal from limited measurements (observations) is
a central task in compressed-sensing-based signal processing [7, 16, 18, 19,
20]. Thus developing fast and robust algorithms for data reconstruction is
significantly important in these practical scenarios. Without loss of
generality, let $x\in\mathbb{R}^{n}$ denote the data (e.g., signal or image)
which admits some sparsity structure in the sense that $x$ is either
$k$-sparse (i.e., $x$ has at most $k\ll n$ nonzero components) or
$k$-compressible (i.e., $x$ can be approximated by a $k$-sparse vector). In
this paper, the unknown data $x\in\mathbb{R}^{n}$ to be reconstructed is
called the target data. To reconstruct the data, one may first collect a few
measurements

$y_{i}:=(a^{i})^{T}x+\nu_{i},~{}i=1,\cdots,m,$ (1)

where $m\ll n,$ $a^{i}$ is a given measurement vector, and $\nu_{i}$ denotes
the measurement error. Let $A$ be the $m\times n$ matrix whose row vectors
consist of $(a^{i})^{T},i=1,\dots,m,$ and let $y=(y_{1},\dots,y_{m})^{T}$ and
$\nu=(\nu_{1},\dots,\nu_{m})^{T}$ be the vectors of measurements and errors,
respectively. Then the system (1) can be written as $y:=Ax+\nu.$ Under the
assumption that the target data $x$ is $k$-sparse or $k$-compressible, the
reconstruction of $x\in\mathbb{R}^{n}$ from the measurements $y$ can be
formulated as the sparse optimization problem:

$\min_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}:~{}\|z\|_{0}\leq k\\},$ (2)

where $\|z\|_{0}$ denotes the number of nonzero entries of $z.$ Essentially,
the model (2) is a combinatorial optimization problem. The vectors satisfying
the constraint of (2) are $k$-sparse. In this paper, we assume that $k\ll n$
which is a typical assumption for compressed-sensing-based signal and image
reconstruction [18, 19, 20, 29]. The algorithms for (2) and similar problems
have experienced a significant development over the past decades. The most
widely used algorithms are convex and nonconvex optimization (e.g., [10, 5, 6,
2, 1, 55]), hard thresholding and greedy methods (see [18, 19, 20, 24] and
references therein). The orthogonal matching pursuit (OMP) is one of the
popular greedy methods for the problem (2). Before recalling such a method,
let us first introduce some notations used in the paper.

###  1.1 Notation

Throughout the paper, all vectors are column vectors unless otherwise
specified. The transpose of the vector $z$ and matrix $A$ are denoted by
$z^{T}$ and $A^{T},$ respectively. The support of the vector $z$ is denoted by
$\textrm{supp}(z)=\\{i:z_{i}\not=0\\}.$ We use ${\cal H}_{k}(\cdot)$ to denote
the hard thresholding operator which retains the $k$ largest magnitudes and
zeros out the other entries of a vector, and we use $L_{q}(\cdot)$ to denote
the index set of the $q$ largest magnitudes of a vector. When at least two
entries of $z$ are equal in absolute value, ${\cal H}_{k}(z)$ and $L_{q}(z)$
might not be uniquely determined, in which case we select the entry with the
smallest index. The complement set of $S\subseteq\\{1,2,\dots,n\\}$ with
respect to $\\{1,\dots,n\\}$ is denoted by
$\overline{S}=\\{1,2,\dots,n\\}\backslash S,$ and the cardinality of $S$ is
denoted by $|S|.$ Given $x\in\mathbb{R}^{n}$ and
$S\subseteq\\{1,2,\dots,n\\},$ the vector $x_{S}\in\mathbb{R}^{n}$ denotes the
vector obtained from $x$ by retaining the entries of $x$ supported on $S$ and
setting other entries of $x$ to be zeros. $\|x\|_{2}=\sqrt{x^{T}x}$ and
$\|x\|_{\infty}=\max_{1\leq i\leq n}|x_{i}|$ are the $\ell_{2}$-norm and
$\ell_{\infty}$-norm, respectively.

###  1.2 Traditional OMP algorithm

Referred to as stagewise regression, the OMP algorithm first appeared in the
area of statistics several decades ago. It was introduced to signal processing
community around 1993 (see, e.g., [38, 13, 31]) and later to approximation
theory (e.g., [14, 15, 44]).

Algorithm 1 Orthogonal Matching Pursuit (OMP)

  * S1

Initialization: $x^{(0)}=0,$ $S^{(0)}=\emptyset.$

  * S2

Given $x^{(p)}$ and $S^{(p)},$ let

$S^{(p+1)}=S^{(p)}\cup L_{1}(A^{T}(y-Ax^{(p)})),$
$x^{(p+1)}=\mathop{\arg\min}_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}:~{}\textrm{supp}(z)\subseteq
S^{(p+1)}\\}.$

Replace $p+1$ with $p,$ and redo S2 until a certain stopping criterion is
satisfied.

The OMP algorithm iteratively selects a vector basis that is best correlated
to the residual at the current iterate. The advantage of OMP lies in its
simple structure allowing a fast implementation at a low computational cost.
OMP has stimulated the development of several other compressed sensing
algorithms, including the subspace pursuit (SP) [11], compressive sampling
matching pursuit (CoSaMP) [37], multipath matching pursuit [25], stagewise
orthogonal matching pursuit (StOMP) [17], regularized orthogonal matching
pursuit (ROMP) [35, 36], general orthogonal matching pursuit (gOMP) [50], weak
orthogonal matching pursuit (WOMP) [45], and constrained matching pursuit
[42]. The gOMP algorithm is a direct generalization of OMP, allowing $N$
indices to be selected simultaneously in every iteration, where $1\leq N<k$ is
a prescribed integer number. These algorithms are often referred to as the
OMP-type algorithms.

###  1.3 Existing results for OMP

The theoretical performance of OMP-type methods can be analyzed in terms of
coherence tools (e.g., [22, 46, 47, 48, 18]). However, the restricted isometry
property (RIP) of the measurement matrix becomes relatively more popular than
coherence for the analysis of various compressed sensing algorithms including
OMP. The RIP is defined as follows.

###### Definition 1.1

_[5]_ Let $A$ be an $m\times n$ matrix. The restricted isometry constant (RIC)
denoted by $\delta_{q}$ is the smallest number $\delta\geq 0$ such that

$(1-\delta)\|z\|^{2}_{2}\leq\|Az\|^{2}_{2}\leq(1+\delta)\|z\|^{2}_{2}$

for any $q$-sparse vector $z\in\mathbb{R}^{n}.$ $A$ is said to satisfy the
restricted isometry property (RIP) of order $q$ if $\delta_{q}<1.$

It was shown in [12] that OMP can identify the exact support of a $k$-sparse
signal in exact $k$ iterations if $\delta_{k+1}<1/(3\sqrt{k}).$ This condition
was relaxed to $\delta_{k+1}<1/(1+\sqrt{2k})$ in [23] and

$\delta_{k+1}<1/(\sqrt{k}+1)$ (3)

in [34] and [51]. The condition (3) was further improved to

$\delta_{k+1}<(\sqrt{4k+1}-1)/(2k)$ (4)

in [8], which is situated between $1/(\sqrt{k}+1)$ and $1/\sqrt{k}.$ Examples
are given in [34, 51] to show that the OMP algorithm might fail to achieve the
correct support identification in exact $k$ iterations when
$\delta_{k+1}=1/\sqrt{k}.$ In noiseless situations (i.e., the measurements are
accurate), it was eventually shown that the condition
$\delta_{k+1}<1/\sqrt{k+1}$ is sharp to guarantee the success of OMP for
$k$-sparse data reconstruction in exact $k$ iterations [33]. In noisy settings
(the measurements are inaccurate), the guaranteed performance of OMP has been
shown in [4] and [53] under the condition (3) and a certain assumption on the
signal to recover. A similar result was also established in [8] under the
condition (4). Another improvement was achieved recently in [52], and it was
shown that the condition $\delta_{k+1}<1/\sqrt{k+1}$ together with a condition
on the signal is sufficient for OMP to correctly identify the support of a
$k$-sparse vector in exact $k$ iterations. Moreover, the stability of OMP was
also studied under the RIP in the literature (e.g., [54]).

While CoSaMP and SP are also motivated by OMP, the two algorithms equipped
with a hard thresholding operator are very different from OMP. The interested
readers can find the latest development of CoSaMP and SP algorithms in such
reference as [9, 20, 43, 58], and can also find the development and results
for other modifications of OMP such as StOMP, MMP, ROMP and gOMP. Here we only
mention some results for gOMP since it includes OMP as a special case and it
is the closest kin to OMP. The gOMP algorithm was introduced first in [50]
(see also [28, 30]). It was shown in [50] that the condition
$\delta_{Nk}<\sqrt{N}/(\sqrt{k}+3\sqrt{N})$ is sufficient for the gOMP
algorithm to reconstruct the $k$-sparse signal in $k$ iterations. This
condition was relaxed in [28] and [39] and was further relaxed to
$\delta_{Nk}<\sqrt{N}/(\sqrt{k}+1.27\sqrt{N})$ in [40]. The reconstruction
error via gOMP in noisy scenarios has been investigated in [27] under the
condition $\delta_{Nk+1}<\sqrt{N}/(\sqrt{k}+\sqrt{N}).$ This condition for
guaranteed performance of gOMP can be relaxed to $\sqrt{N}/\sqrt{k+N}$
together with a condition based on signal-to-noise or minimum-to-average ratio
(see, e.g., [49, 52].

In each iteration, the OMP algorithm only select one index corresponding to
the largest magnitude of $A^{T}(y-Az)$, the gradient of the error metric
$\|y-Az\|_{2}^{2}/2.$ Thus the OMP algorithm does not utilize the gradient
information efficiently when the gradient vector possesses several large
magnitudes whose absolute values are close to each other. In addition, if one
of the first $k$ iterations fails to pick a correct basis, then OMP would
largely fail to reconstruct the target data in exact $k$ iterations. As a
modification of OMP, the gOMP algorithm may select a fixed number ($N>1$) of
bases at each iteration, but such a selection rule remains very rigid, and it
might significantly increase the chance for a wrong basis being selected. For
instance, if $r^{(p)}$ is $\tau$-compressible, where $\tau<N,$ then the $N$
indices selected by gOMP would include an index corresponding to a vanished or
insignificant entry of $r^{(p)}.$

###  1.4 Contribution of the paper

The purpose of this paper is to propose a new framework of the modification of
OMP called dynamic orthogonal matching pursuit (DOMP) together with an
enhanced counterpart of this method. Specifically, the work carried out in the
paper includes three aspects:

  * (a)

The DOMP algorithm and an enhanced version called enhanced dynamic orthogonal
matching pursuit (EDOMP) are proposed in this paper. The two algorithms
dynamically select vector bases to reconstruct the target data according to
the major gradient information of the error metric at every iteration.

  * (b)

The reconstruction error bounds via DOMP and EDOMP are established under the
RIP assumption. These results imply the guaranteed performance of the two
algorithms in sparse data reconstruction and the finite convergence of the two
algorithms in large-scale compressed sensing scenarios.

  * (c)

The numerical performance of the proposed algorithms is evaluated through
random problem instances. The results indicate that due to the efficient usage
of significant gradient information, DOMP and EDOMP are fast and robust
reconstruction algorithms and are very comparable to several state-of-art
algorithms in this field.

The paper is organized as follows. In Section 2, we describe the DOMP
algorithm and its closest kin EDOMP. In Section 3, we introduce an
approximation counterpart of the projection problem in DOMP, which is used to
facilitate the analysis of the two proposed algorithms. In Section 4, we
perform the rigorous analysis of the proposed algorithms to establish the
reconstruction error bounds. Some implications of the error bounds, including
the finite convergence of the algorithms for large-scale compressed sensing
problems, are also discussed in Section 4. Numerical results are demonstrated
in Section 5.

##  2 Dynamic orthogonal matching pursuit

The OMP algorithm only select one index corresponding to the largest magnitude
of $r^{(p)}$ at every iteration. To increase the chance for the correct
support of the target data being identified, it would be helpful to select
indices at every iteration in a dynamic and adaptive manner. To this goal, we
propose the so-called dynamic orthogonal matching pursuit (DOMP), which select
vector bases (i.e., the column vectors of $A$) at every iteration to
approximate the target data through efficiently exploiting the information of
the underlying gradient vector. The DOMP algorithm is described as Algorithm
2.

Algorithm 2 Dynamic Orthogonal Matching Pursuit (DOMP)

  * S1

Initialization: Set $x^{(0)}=0$, $S^{(0)}=\emptyset$ and
$r^{(0)}=A^{T}(y-Ax^{(0)})=A^{T}y.$ Choose parameter $\gamma\in(0,1].$

  * S2

Given $x^{(p)}$, $S^{(p)}$ and $r^{(p)}=A^{T}(y-Ax^{(p)}),$ let

$\Theta^{(p)}=\\{i:~{}i\in
L_{k}(r^{(p)}),~{}|(r^{(p)})_{i}|\geq\gamma\|r^{(p)}\|_{\infty}\\},$

and then set

$S^{(p+1)}=S^{(p)}\cup\Theta^{(p)},$ (DOMP1)
$x^{(p+1)}=\mathop{\arg\min}_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}:~{}\textrm{supp}(z)\subseteq
S^{(p+1)}\\}.$ (DOMP2)

Replace $p+1$ with $p$, and redo S2 until a certain stopping criterion is
satisfied.

Two typical classes of stopping criteria can be used in DOMP depending on the
application environment: The algorithm may stop in prescribed number of
iterations; the algorithm may stop when
$\|y-Ax^{(p)}\|_{2}\leq\varepsilon^{*}$ or
$\|r^{(p)}\|_{2}\leq\varepsilon^{*},$ where $\varepsilon^{*}>0$ is a
prespecified tolerance.

Since $x^{(p)}$ is an optimal solution to the convex optimization problem
$\min\\{\|y-Az\|_{2}:\textrm{supp}(z)\subseteq S^{(p)}\\},$ by the first-order
optimality condition, the iterates generated by DOMP satisfy that

$(r^{(p)})_{S^{(p)}}=0~{}\textrm{ for any }p\geq 1.$ (5)

This property will be frequently used in our analysis of the algorithm.

The DOMP algorithm dynamically select the vector basis according to the
criterion $|(r^{(p)})_{i}|\geq\gamma\|r^{(p)}\|_{\infty}$ for $i\in
L_{k}(r^{(p)}).$ This rule guarantees that only the indices corresponding to
the significant entries of $r^{(p)}$ can be used to identify the support of
target data. If $\Theta^{(p)}$ is a singleton, then the current step of DOMP
is reduced exactly to that of OMP. In general, however, $\Theta^{(p)}$
contains more than one elements corresponding to the indices of a few largest
magnitudes of $r^{(p)}.$ Even when $\gamma=1,$ the DOMP algorithm may not
necessarily be the same as OMP since the set $\Theta^{(p)}$ may still contain
more than one indices if $r^{(p)}$ possesses multiple entries whose absolute
values are equal to $\|r^{(p)}\|_{\infty}.$ The cardinality of $\Theta^{(p)}$
can be any value between 1 and $k,$ depending on the prescribed value of
$\gamma$ and the number of significant entries of $r^{(p)}.$ Such a dynamic
selection of indices efficiently utilizes the gradient information of the
error metric, and thus it might speed up the algorithm by increasing the
chance for the correct support of target data being identified at every
iteration. This is quite different from existing modifications of OMP. For
instance, the indices chosen at each step of WOMP is not necessarily in
$L_{k}(r^{(p)})$, and the number of indices selected in each step of gOMP is
fixed to be $N\geq 1$ no matter what structure the vector $r^{(p)}$ possesses.
When $r^{(p)}$ contains very few large magnitudes whose number is less than
$N,$ the gOMP algorithm would select an index corresponding to a small
magnitude of $r^{(p)}$ that is less likely to be correct in general.

After a few iterations are performed, the cardinality of $S^{(p+1)}$ in DOMP
might be larger than $k.$ In this case, it is useful to perform the hard
thresholding on the vector generated by (DOMP2) in order to maintain the
$k$-sparsity of iterates so that they are feasible to the sparse optimization
problem (2). This consideration leads to the enhanced dynamic orthogonal
matching pursuit (EDOMP) which is described as Algorithm 3.

Algorithm 3 Enhanced Dynamic Orthogonal Matching Pursuit (EDOMP)

  * S1

Initialization: Set $x^{(0)}=0$, $S^{(0)}=\emptyset$, $r^{(0)}=A^{T}y$ and a
parameter $\gamma\in(0,1].$

  * S2

Given $x^{(p)}$, $S^{(p)}$ and $r^{(p)}=A^{T}(y-Ax^{(p)}),$ let

$\Theta^{(p)}=\\{i:~{}i\in
L_{k}(r^{(p)}),~{}|(r^{(p)})_{i}|\geq\gamma\|r^{(p)}\|_{\infty}\\}.$

Set $S^{(p+1)}=S^{(p)}\cup\Theta^{(p)}$ and

$\widetilde{x}^{(p+1)}=\mathop{\arg\min}_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}:~{}\textrm{supp}(z)\subseteq
S^{(p+1)}\\}.$

If $|S^{(p+1)}|\leq k$, set $x^{(p+1)}=\widetilde{x}^{(p+1)};$ otherwise, set
$Q=L_{k}(\widetilde{x}^{(p+1)})$ and

$x^{(p+1)}=\textrm{arg}\min_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}:~{}\textrm{supp}(z)\subseteq
Q\\}.$

Replace $p+1$ with $p$, and redo S2 until a certain stopping criterion is
satisfied.

The analysis in the paper is focused on the DOMP algorithm. Based on the
result for DOMP, it is not difficult to obtain the result for EDOMP. The main
purpose of this analysis is to establish the reconstruction error bounds for
the two algorithms, which bound the error between the target data and the
iterates generated by the proposed algorithms. To facilitate the analysis of
the proposed algorithms, let us first define an auxiliary optimization model
in the next section.

##  3 Approximation counterpart of (DOMP2)

Denote by $S=L_{k}(x),$ and let $x^{(p)},S^{(p)},r^{(p)},\Theta^{(p)}$ and
$S^{(p+1)}$ be defined in DOMP. Define

$\Lambda^{(p)}:=L_{k}(r^{(p)})\setminus(S^{(p)}\cup\Theta^{(p)}\cup S).$ (6)

We now introduce an approximation counterpart (AC) to the projection problem
(DOMP2), which generates the index set $\widehat{S}^{(p+1)}$ and the vector
$\widehat{x}^{(p+1)}.$

Approximation counterpart of (DOMP2): Let $x^{(p)}$, $S^{(p)}$, $\Theta^{(p)}$
and $S^{(p+1)}$ be given in DOMP, and let $\Lambda^{(p)}$ be defined by (6).
Let

$\widehat{S}^{(p+1)}=S^{(p+1)}\cup\Lambda^{(p)},$ (AC1)
$\widehat{x}^{(p+1)}=\mathop{\arg\min}_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}^{2}+\sigma\|z_{\Lambda^{(p)}}\|_{2}^{2}:~{}\textrm{supp}(z)\subseteq\widehat{S}^{p+1}\\},$
(AC2)

where $\|z_{\Lambda^{(p)}}\|_{2}^{2}=\sum_{i\in\Lambda^{(p)}}z_{i}^{2}$ and
$\sigma$ is a given large positive parameter.

When $r^{(p)}=0,$ $x^{(p)}$ is already a global solution to the problem (2).
Thus, to analyze the DOMP and EDOMP algorithms, we assume without loss of
generality that $r^{(p)}\not=0,$ in which case we can see from the definition
of $\Theta^{(p)}$ that $(r^{(p)})_{i}\not=0$ for any $i\in\Theta^{(p)}.$ This
together with (5) implies that

$S^{(p)}\cap\Theta^{(p)}=\emptyset.$ (7)

Since $S^{(p+1)}=S^{(p)}\cup\Theta^{(p)}$, we also see from (6) that

$\Lambda^{(p)}\cap S^{(p+1)}=\emptyset.$ (8)

Thus

$|S^{(p+1)}|=|S^{(p)}|+|\Theta^{(p)}|,~{}|\widehat{S}^{(p+1)}|=|S^{(p+1)}|+|\Lambda^{(p)}|,~{}p\geq
1.$ (9)

The solution of the optimization problem in (AC2) depends on the parameter
$\sigma.$ Thus $\widehat{x}^{(p+1)}$ should be written as
$\widehat{x}^{(p+1)}(\sigma).$ For notational convenience, however, we simply
use $\widehat{x}^{(p+1)}$ to denote the solution of (AC2) throughout the
paper. In this paper, the above approximation counterpart is only used as an
auxiliary tool to provide convenience for the analysis of DOMP. In (AC2), the
components of $z$ supported on $\Lambda^{(p)}$ are surpassed by a large
penalty parameter $\sigma.$ For a sufficiently large $\sigma,$ the components
of $\widehat{x}^{(p+1)}$ supported on $\Lambda^{(p)}$ would either completely
vanish or be sufficiently small. As a result, $\widehat{x}^{(p+1)}$ can be
made arbitrarily close to $x^{(p+1)},$ the iterate generated by DOMP, provided
that $\sigma$ is sufficiently large. The following lemma makes this rigorous.

###### Lemma 3.1

At the iterate $x^{(p)}$, let $x^{(p+1)}$ and $S^{(p+1)}$ be generated by
DOMP, and let $\widehat{S}^{(p+1)}$ and $\widehat{x}^{(p+1)}$be defined in
(AC1) and (AC2) accordingly. Then one has

$\|A(\widehat{x}^{(p+1)}-x^{(p+1)})\|_{2}\leq C\vartheta_{(y,A)},$ (10)

where
$C:=\sqrt{\frac{2\|A\|_{2}}{\sqrt{\sigma}}+\frac{\|A\|_{2}^{2}}{\sigma}}+\frac{\|A\|_{2}}{\sqrt{\sigma}}$
and $\vartheta_{(y,A)}$ is the constant defined as

$\vartheta_{(y,A)}:=\max_{U\subseteq\\{1,\cdots,n\\},U\not=\emptyset}\left(\min_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}:~{}\emph{supp}(z)\subseteq
U\\}\right).$ (11)

_Proof._ Suppose that $x^{(p)},\Theta^{(p)}$ and $x^{(p+1)}$ are generated by
DOMP. Let $\Lambda^{(p)}$ be defined by (6) and $\widehat{x}^{(p+1)}$ be a
solution to the minimization problem (AC2). Note that $x^{(p+1)}$ is a
feasible solution to the minimization problem (AC2), by the optimality of
$\widehat{x}^{(p+1)},$ we have

$\displaystyle\|y-A\widehat{x}^{(p+1)}\|_{2}^{2}+\sigma\|(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}^{2}$
$\displaystyle\leq\|y-Ax^{(p+1)}\|_{2}^{2}+\sigma\|(x^{(p+1)})_{\Lambda^{(p)}}\|_{2}^{2}$
$\displaystyle=\|y-Ax^{(p+1)}\|_{2}^{2},$ (12)

where the equality follows from (8) which implies that
$(x^{(p+1)})_{\Lambda^{(p)}}=0$ as $\textrm{supp}(x^{(p+1)})\subseteq
S^{p+1}.$ Thus

$\displaystyle\sigma\|(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}^{2}\leq\|y-Ax^{(p+1)}\|_{2}^{2}=\min_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}^{2}:~{}\textrm{supp}(z)\subseteq
S^{(p+1)}\\}\leq(\vartheta_{(y,A)})^{2},$

where $\vartheta_{(y,A)}$ is the constant defined in (11). The inequalities
above imply that

$\|(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}\leq\frac{\vartheta_{(y,A)}}{\sqrt{\sigma}},~{}\|y-Ax^{(p+1)}\|_{2}\leq\vartheta_{(y,A)}.$
(13)

We now bound $\|A\left(x^{(p+1)}-\widehat{x}^{(p+1)}\right)\|_{2}.$ From (3),
we see that

$\|y-A\widehat{x}^{(p+1)}\|_{2}\leq\|y-Ax^{(p+1)}\|_{2}.$ (14)

By (AC1) and (8), we see that
$\widehat{x}^{(p+1)}=(\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}=(\widehat{x}^{(p+1)})_{S^{(p+1)}}+(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}.$
Thus by the triangular inequality, we have

$\displaystyle\|y-A\widehat{x}^{(p+1)}\|_{2}$
$\displaystyle=\|y-A[(\widehat{x}^{(p+1)})_{S^{(p+1)}}+(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}]\|_{2}$
$\displaystyle\geq\|y-A(\widehat{x}^{(p+1)})_{S^{(p+1)}}\|_{2}-\|A(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}.$
(15)

Merging (14) and (3) leads to

$\|y-A(\widehat{x}^{(p+1)})_{S^{(p+1)}}\|_{2}\leq\|y-Ax^{(p+1)}\|_{2}+\|A(\widehat{x}^{p+1})_{\Lambda^{(p)}}\|_{2},$

which together with (13) implies that

$\displaystyle\|y$
$\displaystyle-A(\widehat{x}^{(p+1)})_{S^{(p+1)}}\|_{2}^{2}$
$\displaystyle\leq\left(\|y-Ax^{(p+1)}\|_{2}+\|A(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}\right)^{2}$
$\displaystyle=\|y-Ax^{(p+1)}\|_{2}^{2}+2\|y-Ax^{(p+1)}\|_{2}\|A(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}+\|A(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}^{2}$
$\displaystyle\leq\|y-Ax^{(p+1)}\|_{2}^{2}+2\vartheta_{(y,A)}\|A\|_{2}\|(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}+\|A\|_{2}^{2}\|(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}^{2}$
$\displaystyle\leq\|y-Ax^{(p+1)}\|_{2}^{2}+2\vartheta_{(y,A)}\|A\|_{2}\left(\frac{\vartheta_{(y,A)}}{\sqrt{\sigma}}\right)+\|A\|_{2}^{2}\left(\frac{\vartheta_{(y,A)}}{\sqrt{\sigma}}\right)^{2}$
$\displaystyle=\|y-Ax^{(p+1)}\|_{2}^{2}+\left(\frac{2\|A\|_{2}}{\sqrt{\sigma}}+\frac{\|A\|_{2}^{2}}{\sigma}\right)(\vartheta_{(y,A)})^{2}.$
(16)

By Taylor’s expansion, we also have that

$\displaystyle\|y-A(\widehat{x}^{(p+1)})_{S^{(p+1)}}\|_{2}^{2}$
$\displaystyle=\|y-Ax^{(p+1)}\|_{2}^{2}+2[-A^{T}(y-Ax^{(p+1)})]^{T}[(\widehat{x}^{(p+1)})_{S^{(p+1)}}-x^{(p+1)}]$
$\displaystyle~{}~{}~{}+[(\widehat{x}^{(p+1)})_{S^{(p+1)}}-x^{(p+1)}]^{T}A^{T}A[(\widehat{x}^{(p+1)})_{S^{(p+1)}}-x^{(p+1)}]$
$\displaystyle=\|y-Ax^{(p+1)}\|_{2}^{2}+\|A[(\widehat{x}^{(p+1)})_{S^{(p+1)}}-x^{(p+1)}]\|_{2}^{2},$
(17)

where the last equality follows from (5) and the fact that
$\textrm{supp}[(\widehat{x}^{(p+1)})_{S^{(p+1)}}$ $-x^{(p+1)}]$ $\subseteq
S^{(p+1)}.$ Combining (3) and (3) yields

$\|A[(\widehat{x}^{(p+1)})_{S^{(p+1)}}-x^{(p+1)}]\|_{2}^{2}\leq\left(\frac{2\|A\|_{2}}{\sqrt{\sigma}}+\frac{\|A\|_{2}^{2}}{\sigma}\right)(\vartheta_{(y,A)})^{2}.$
(18)

By (AC1) and (8), i.e., $\widehat{S}^{(p+1)}=S^{(p+1)}\cup\Lambda^{(p)}$ and
$S^{(p+1)}\cap\Lambda^{(p)}=\emptyset,$ we immediately see that
$\left(\overline{\widehat{S}^{(p+1)}}\right)\cap\Lambda^{(p)}=\emptyset$ and
$\overline{S^{(p+1)}}=\overline{\widehat{S}^{(p+1)}\setminus\Lambda^{(p)}}=\overline{\widehat{S}^{(p+1)}}\cup\Lambda^{(p)},$
and hence

$\displaystyle(\widehat{x}^{(p+1)})_{\overline{S^{(p+1)}}}=(\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}+(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}=(\widehat{x}^{(p+1)})_{\Lambda^{(p)}},$

where the last equality follows from the fact that
$(\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}=0.$ This together with
(13), (18) and $(x^{(p+1)})_{\overline{S^{(p+1)}}}=0$ implies that

$\displaystyle\|A(\widehat{x}^{(p+1)}-x^{(p+1)})\|_{2}$
$\displaystyle=\|A[(\widehat{x}^{(p+1)}-x^{(p+1)})_{S^{(p+1)}}+(\widehat{x}^{(p+1)}-x^{(p+1)})_{\overline{S^{(p+1)}}}]\|_{2}$
$\displaystyle=\|A[(\widehat{x}^{(p+1)})_{S^{(p+1)}}-x^{(p+1)}]+A(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}$
$\displaystyle\leq\|A[(\widehat{x}^{(p+1)})_{S^{(p+1)}}-x^{(p+1)}]\|_{2}+\|A(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}$
$\displaystyle\leq\vartheta_{(y,A)}\sqrt{\frac{2\|A\|_{2}}{\sqrt{\sigma}}+\frac{\|A\|_{2}^{2}}{\sigma}}+\|A\|_{2}\frac{\vartheta_{(y,A)}}{\sqrt{\sigma}}$
$\displaystyle=\left(\sqrt{\frac{2\|A\|_{2}}{\sqrt{\sigma}}+\frac{\|A\|_{2}^{2}}{\sigma}}+\frac{\|A\|_{2}}{\sqrt{\sigma}}\right)\vartheta_{(y,A)},$

which is exactly the inequality (10). $\Box$

A basic property of the optimization problem (AC2) is given in the next lemma
which follows directly from the optimality condition of convex optimization.
The proof of the lemma is omitted.

###### Lemma 3.2

Let $\widehat{x}^{(p+1)}$ be a minimizer of (AC2), i.e.,

$\widehat{x}^{(p+1)}=\mathop{\arg\min}_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}^{2}+\sigma\|z_{\Lambda^{(p)}}\|_{2}^{2}:~{}\emph{supp}(z)\subseteq\widehat{S}^{(p+1)}\\},$

where $\widehat{S}^{(p+1)}$ is defined by (AC1). Then

$\left[-A^{T}(y-A\widehat{x}^{(p+1)})+\sigma(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\right]_{\widehat{S}^{(p+1)}}=0.$
(19)

##  4 Reconstruction error bounds

In this section, we establish the reconstruction error bounds for DOMP and
EDOMP. The guaranteed performance of the algorithms for sparse data
reconstruction can be interpreted via such error bounds which measure the
distance of the generated $k$-sparse solution and the significant components
of the target data. The error bound not only indicates the efficiency and
capability of an algorithm in sparse data reconstruction, but also may
directly imply some other desired attributes of the algorithm such as the
stability and convergence of the algorithm. Let us first recall the following
matrix property that will be used in our analysis.

###### Lemma 4.1

[20] _(i)_ Let $u\in\mathbb{R}^{n}$ and $\Lambda\subseteq\\{1,2,\dots,n\\}.$
If $|\Lambda\cup{\rm supp}(u)|\leq t,$ then
$\|[(I-A^{T}A)u]_{\Lambda}\|_{2}\leq\delta_{t}\|u\|_{2}.$

(ii) Let $u\in\mathbb{R}^{n}$ and $\Lambda\subseteq\\{1,2,\dots,n\\}.$ If
$\Lambda\cap{\rm supp}(u)=\emptyset$ and $|\Lambda\cup{\rm supp}(u)|\leq t,$
then $\|(A^{T}Au)_{\Lambda}\|_{2}\leq\delta_{t}\|u\|_{2}.$

(iii) Let $u\in\mathbb{R}^{n}$ and $\Lambda\subseteq\\{1,2,\dots,n\\}$ with
$|\Lambda|\leq t,$ one has
$\|(A^{T}u)_{\Lambda}\|_{2}\leq\sqrt{1+\delta_{t}}\|u\|_{2}.$

The error bounds are established in this paper for DOMP and EDOMP under the
RIP assumption. It is worth pointing out that the RIP assumption is not the
unique one that can be used to analyze the efficiency of sparse-data-
reconstruction algorithms. There exist other essential tools such as the spark
[18], mutual coherence [18], null space property [20], and range space
property of $A^{T}$ [55, 56]. The interested reader may examine the
performance of the algorithms by using other tools including the above-
mentioned ones.

###  4.1 Main result for DOMP

It is important to address the following questions: How does the
reconstruction error decay in the course of iterations? Equivalently, after a
few iterations are performed, how close is the current iterate $x^{(p)}$ to
the target data? In other words, we would like to measure the quality of the
iterate generated by the algorithm as an approximation to the target data. The
main result for DOMP is summarized in Theorem 4.2, whose proof is postponed to
the end of the next subsection after we establish some helpful technical
results.

###### Theorem 4.2

Suppose that $y:=Ax+\nu$ are the measurements of the target data
$x\in\mathbb{R}^{n}$ where $\nu$ are the measurement errors. Let
$\gamma\in(0,1]$ be a given constant. If the RIC of the measurement matrix $A$
satisfies

$\delta_{ck}<\frac{1}{\sqrt{1+\left(1+\sqrt{1+k\gamma^{2}}\right)^{2}}},$ (20)

where $c>2$ is an integer number, then at the $p$th iteration, provided that
$|S^{p+1}|\leq(c-2)k,$ the iterate $x^{(p+1)}$ generated by DOMP approximates
$x_{S}$ with error

$\displaystyle\|x^{(p+1)}-x_{S}\|_{2}\leq$
$\displaystyle\beta^{p}\left((\varrho/\beta)^{k}\|x_{S}-x^{(0)}\|_{2}\right)+\tau\|\nu^{\prime}\|_{2},$
(21)

where $\nu^{\prime}=Ax_{\overline{S}}+\nu$ and $S=L_{k}(x).$ The constants
$\beta$ and $\varrho$ are given respectively as

$\beta=\frac{\left(1+\sqrt{1+k\gamma^{2}}\right)\delta_{ck}}{\sqrt{1-\delta^{2}_{ck}}}<1,~{}\varrho=\sqrt{\frac{1+\delta_{ck}}{1-\delta_{ck}}},$

and $\tau$ is a constant dependent only of $\delta_{ck},$ $k$ and $\gamma.$

###### Remark 4.3

_If $x$ is $k$-compressible with very small tail $\|x_{\overline{S}}\|_{2}$
and the measurements are accurate enough, then $\|\nu^{\prime}\|_{2}$ would be
small enough. In particular, if $x$ is $k$-sparse and the measurements are
accurate, then $\|\nu^{\prime}\|_{2}=0.$ From (21), the reconstruction quality
in these cases would completely depends on the times of iterations being
excuted. The more iterations, the better the reconstruction quality. We also
note that $|S^{(p+1)}|$ is the total number of indices being selected after
$p$ iterations. At the $p$th iteration, the indices in $\Theta^{(p)}$ are
added to $S^{(p)}$ to form the set $S^{(p+1)}.$ By (7),
$|S^{(p+1)}|=\sum_{i=1}^{p}|\Theta^{(p)}|\leq pk,$ thus the largest integer
number $p^{*}$ satisfying $|S^{(p^{*}+1)}|\leq(c-2)k$ would be at least
$(c-2).$ This means when $c\gg 2$ the DOMP algorithm can perform enough
iterations and thus it follows from (21) that $\|x^{(p)}-x_{S}\|_{2}\approx 0$
after the algorithm is performed enough iterations. This means $x^{(p)}$ is a
quality reconstruction of $x_{S}.$ _

From Definition 1.1, we see that $\delta_{s}\leq\delta_{t}$ for any positive
integer number $s\leq t.$ Thus if $A$ has the RIP of order $t$, i.e.,
$\delta_{t}<1,$ then it has the RIP of any order $s\leq t.$ The condition
$\delta_{t}<1$ implies that any $t$ columns of matrix are linearly
independent, and thus $t$ must be lower than the $\textrm{Spark}(A)$ which is
the minimum number of columns in $A$ that are linearly dependent [18]. In this
paper, we define the highest order of the RIP of $A$ as

$t^{\max}=\max\\{t:~{}\delta_{t}<1\\}.$

The property $\delta_{t^{\max}}<1$ is referred to as the RIP of highest order
of $A.$ The lemma below follows immediately from Theorem 4.2.

###### Corollary 4.4

Let $y:=Ax+\nu$ be the measurements of the target data $x\in\mathbb{R}^{n}$
where $\nu$ are the measurement errors. Let $\gamma\in(0,1]$ be a given
constant. If the RIC of highest order $t^{\max}$ $(t^{\max}>2k)$ of the matrix
$A$ satisfies

$\delta_{t^{\max}}<\frac{1}{\sqrt{1+\left(1+\sqrt{1+k\gamma^{2}}\right)^{2}}},$
(22)

then at the $p$th iteration, provided $|S^{p+1}|\leq t^{\max}-2k,$ the iterate
$x^{(p+1)}$ generated by DOMP approximates $x_{S}$ with error

$\displaystyle\|x^{(p+1)}-x_{S}\|_{2}\leq$
$\displaystyle\hat{\beta}^{p}\left((\hat{\varrho}/\hat{\beta})^{k}\|x_{S}-x^{(0)}\|_{2}\right)+\hat{\tau}\|\nu^{\prime}\|_{2},$

where $\nu^{\prime}=Ax_{\overline{S}}+\nu$ and $S=L_{k}(x).$ The constants
$\hat{\beta}$ and $\hat{\varrho}$ are given respectively as

$\hat{\beta}=\frac{\left(1+\sqrt{1+k\gamma^{2}}\right)\delta_{t^{\max}}}{\sqrt{1-\delta^{2}_{t^{\max}}}}<1,~{}\hat{\varrho}=\sqrt{\frac{1+\delta_{t^{\max}}}{1-\delta_{t^{\max}}}},~{}$

and $\hat{\tau}$ is a constant dependent only of $\delta_{t^{\max}}$, $k$ and
$\gamma.$

###### Remark 4.5

_The results above indicate that the quality of the iterate as an
approximation to $x_{S}$ can be measured provided that the total number of
selected indices is lower than $t^{\max}-2k.$ The RIC bounds (20) and (22)
depends on the parameter $\gamma$. In theory, a small parameter $\gamma$ can
alleviate the requirement on measurement matrices since the smaller the
parameter $\gamma,$ the larger the right-hand sides of (20) and (22). Taking
the sparsity level $k=100$ as an example, the table below lists a few RIC
bounds corresponding to several different choices of $\gamma.$_

RIC bound for DOMP |  $k=100$
---|---
$\delta_{t^{\max}}<\frac{1}{\sqrt{1+\left(1+\sqrt{1+k\gamma^{2}}\right)^{2}}}$ | $\begin{array}[]{l}\gamma=0.9:~{}\delta_{t^{\max}}<0.0990\\\ \gamma=0.7:~{}\delta_{t^{\max}}<0.1230\\\ \gamma=0.5:~{}\delta_{t^{\max}}<0.1618\\\ \gamma=0.3:~{}\delta_{t^{\max}}<0.2236\\\ \gamma=0.1:~{}\delta_{t^{\max}}<0.3827\\\ \gamma\to 0:~{}\delta_{t^{\max}}<1/\sqrt{5}\end{array}$

_It is worth mentioning that the error bound ( 21) combined with Lemma 6.23 in
[20] can imply the stability of DOMP and EDOMP for sparse data reconstruction
under the conditions similar to that of Theorem 4.2. Such stability results
are omitted in this paper. The main results above can also imply the finite
convergence of the proposed algorithms for a class of large-scale compressed
sensing problems (see Section 4.4 for details)._

###  4.2 Proof of the main result for DOMP

We first establish several useful technical results. The first one below is
actually shown in [58].

###### Lemma 4.6

Given constants $\alpha_{1},\alpha_{2},\alpha_{3}\geq 0$ where $\alpha_{1}<1,$
if $t$ satisfies that

$t\leq\alpha_{1}\sqrt{t^{2}+\alpha_{2}^{2}}+\alpha_{3},$ (23)

then

$t\leq\frac{\alpha_{1}}{\sqrt{1-\alpha_{1}^{2}}}\alpha_{2}+\frac{1}{1-\alpha_{1}}\alpha_{3},~{}\sqrt{t^{2}+\alpha_{2}^{2}}\leq\frac{\alpha_{2}}{\sqrt{1-\alpha_{1}^{2}}}+\frac{\alpha_{3}}{1-\alpha_{1}}.$
(24)

_Proof_. The first inequality in (24) was shown in [58] (see Lemma 4.1
therein). Thus we only need to show the second inequality in (24), which
follows from the first inequality together with the fact that
$\sqrt{(a+c)^{2}+b^{2}}\leq\sqrt{a^{2}+b^{2}}+c$ for any $a,b,c\geq 0.$
Indeed,

$\displaystyle\sqrt{t^{2}+\alpha_{2}^{2}}$
$\displaystyle\leq\sqrt{\left(\frac{\alpha_{1}}{\sqrt{1-\alpha_{1}^{2}}}\alpha_{2}+\frac{1}{1-\alpha_{1}}\alpha_{3}\right)^{2}+\alpha_{2}^{2}}\leq\sqrt{\left(\frac{\alpha_{1}}{\sqrt{1-\alpha_{1}^{2}}}\alpha_{2}\right)^{2}+\alpha_{2}^{2}}+\frac{1}{1-\alpha_{1}}\alpha_{3}$
$\displaystyle=\frac{1}{\sqrt{1-\alpha_{1}^{2}}}\alpha_{2}+\frac{1}{1-\alpha_{1}}\alpha_{3},$

as claimed. $\Box$

Some fundamental properties of DOMP and the optimization problem (AC2) are
given in the next two lemmas.

###### Lemma 4.7

Let $y:=Ax+\nu,$ $S^{(p+1)}$ be generated by DOMP, $\widehat{S}^{(p+1)}$ be
defined in (AC1), and let $\widehat{x}^{(p+1)}$ be a minimizer of (AC2). If
$A$ satisfies that $\delta_{k+|\widehat{S}^{(p+1)}|}<1$ , then

$\displaystyle\|x_{S}-\widehat{x}^{(p+1)}\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{1-\delta^{2}_{k+|\widehat{S}^{(p+1)}|}}}\left\|(x_{S}-\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}\right\|_{2}+\frac{\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}}{1-\delta_{k+|\widehat{S}^{(p+1)}|}}\|\nu^{\prime}\|_{2},$
(25)

where $\nu^{\prime}=Ax_{\overline{S}}+\nu$ and $S=L_{k}(x).$

_Proof._ By Lemma 3.2, we have

$\left[-A^{T}(y-A\widehat{x}^{(p+1)})+\sigma(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\right]_{\widehat{S}^{(p+1)}}=0.$

As $y=Ax+\nu=Ax_{S}+\nu^{\prime}$ where $\nu^{\prime}=Ax_{\overline{S}}+\nu,$
the above equality can be written as

$[-A^{T}A(x_{S}-\widehat{x}^{(p+1)})-A^{T}\nu^{\prime}+\sigma(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}]_{\widehat{S}^{(p+1)}}=0.$

Note that
$[(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}]_{\widehat{S}^{(p+1)}}=(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}$
since $\Lambda^{(p)}\subseteq\widehat{S}^{(p+1)}.$ The equality above is
equivalent to

$\displaystyle(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}=\left[(I-A^{T}A)(x_{S}-\widehat{x}^{(p+1)})\right]_{\widehat{S}^{(p+1)}}-(A^{T}\nu^{\prime})_{\widehat{S}^{(p+1)}}+\sigma(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}.$
(26)

By the definition of $\Lambda^{(p)}$ in (6), we see that
$S\cap\Lambda^{(p)}=\emptyset.$ Thus $(x_{S})_{\Lambda^{(p)}}=0$ and

$\displaystyle[(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}]^{T}(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}$
$\displaystyle=[(x_{S}-\widehat{x}^{(p+1)})_{\Lambda^{(p)}}]^{T}(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}=-\|(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}\|_{2}^{2}\leq
0.$ (27)

Multiplying (26) by $(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}$, using
(27) and Lemma 4.1 (i) and (iii), we obtain

$\displaystyle\|(x_{S}$
$\displaystyle-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}^{2}$
$\displaystyle=[(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}]^{T}[(I-A^{T}A)(x_{S}-\widehat{x}^{(p+1)})]_{\widehat{S}^{(p+1)}}$
$\displaystyle~{}~{}~{}-[(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}]^{T}(A^{T}\nu^{\prime})_{\widehat{S}^{(p+1)}}+\sigma[(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}]^{T}(\widehat{x}^{(p+1)})_{\Lambda^{(p)}}$
$\displaystyle\leq[(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}]^{T}[(I-A^{T}A)(x_{S}-\widehat{x}^{(p+1)})]_{\widehat{S}^{(p+1)}}$
$\displaystyle~{}~{}~{}-[(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}]^{T}(A^{T}\nu^{\prime})_{\widehat{S}^{(p+1)}}$
$\displaystyle\leq\delta_{k+|\widehat{S}^{(p+1)}|}\|x_{S}-\widehat{x}^{(p+1)}\|_{2}\|(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}$
$\displaystyle~{}~{}~{}+\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}\|\nu^{\prime}\|_{2}\|(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}$
$\displaystyle=\|(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}\left(\delta_{k+|\widehat{S}^{(p+1)}|}\|x_{S}-\widehat{x}^{(p+1)}\|_{2}+\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}\|\nu^{\prime}\|_{2}\right).$
(28)

If $\|(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}=0,$ then
$\|x_{S}-\widehat{x}^{(p+1)}\|_{2}=\|(x_{S}-\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2},$
and hence the inequality (25) is satisfied trivially. Thus we assume without
loss of generality that
$\|(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}\not=0.$ In this
case, we cancel this term from (4.2) to obtain that

$\displaystyle\|(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}$
$\displaystyle\leq\delta_{k+|\widehat{S}^{(p+1)}|}\|x_{S}-\widehat{x}^{(p+1)}\|_{2}+\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}\|\nu^{\prime}\|_{2}$
$\displaystyle=\delta_{k+|\widehat{S}^{(p+1)}|}\Big{(}\|(x-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}^{2}+\|(x-\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2}^{2}\Big{)}^{\frac{1}{2}}$
$\displaystyle~{}~{}~{}+\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}\|\nu^{\prime}\|_{2},$

which is in the form of (23) with
$t=\|(x_{S}-\widehat{x}^{p+1})_{\widehat{S}^{(p+1)}}\|_{2},$
$\alpha_{1}=\delta_{k+|\widehat{S}^{(p+1)}|},~{}\alpha_{2}=\|(x_{S}-\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2},~{}\alpha_{3}=\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}\|\nu^{\prime}\|_{2},$
and

$\displaystyle\|x_{S}-\widehat{x}^{(p+1)}\|_{2}=\sqrt{\|(x_{S}-\widehat{x}^{(p+1)})_{\widehat{S}^{(p+1)}}\|_{2}^{2}+\|(x_{S}-\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2}^{2}}=\sqrt{t^{2}+\alpha_{2}^{2}}.$

Thus it immediately follows from Lemma 4.6 that

$\displaystyle\|x_{S}-\widehat{x}^{(p+1)}\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{1-\delta^{2}_{k+|\widehat{S}^{(p+1)}|}}}\|(x_{S}-\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2}+\frac{\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}}{1-\delta_{k+|\widehat{S}^{(p+1)}|}}\|\nu^{\prime}\|_{2},$

which is exactly the relation (25). $\Box$

Under the condition $\Theta^{(p)}\cap S=\emptyset,$ we now bound the term
$\|(x_{S}-\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2}$ which
is equal to $\|(x_{S}-x^{(p)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2}$ since
$(\widehat{x}^{(p+1)})_{\overline{\widehat{S}^{(p+1)}}}=0$ and
$(x^{(p)})_{\overline{\widehat{S}^{(p+1)}}}=0.$

###### Lemma 4.8

Let $y:=Ax+\nu,$ and let $x^{(p)},$ $S^{(p)},$ $\Theta^{(p)}$ and $S^{(p+1)}$
be generated by DOMP. Let $\widehat{S}^{(p+1)}$ be defined by (AC1), i.e.,
$\widehat{S}^{(p+1)}=S^{(p+1)}\cup\Lambda^{(p)}$ where $\Lambda^{(p)}$ is
defined by (6). Suppose that $\Theta^{(p)}\cap S=\emptyset$ where
$S=L_{k}(x).$ If the matrix $A$ satisfies that
$\delta_{k+|\widehat{S}^{(p+1)}|}<1,$ then one has

$\|(x_{S}-x^{(p)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2}\leq\left(1+\sqrt{1+\gamma^{2}k}\right)\left(\delta_{2k+|S^{(p)}|}\|x_{S}-x^{(p)}\|_{2}+\sqrt{1+\delta_{k}}\|\nu^{\prime}\|_{2}\right),$
(29)

where $\nu^{\prime}=Ax_{\overline{S}}+\nu$ and $\gamma\in(0,1]$ is a given
parameter in DOMP.

Proof.  Let $x^{(p)}$ be the current iterate and
$r^{(p)},S^{(p)},\Theta^{(p)},S^{(p+1)}$ be defined in DOMP. Suppose that
$\Theta^{(p)}$ and $S$ are disjoint, i.e.,

$S\cap\Theta^{(p)}=\emptyset.$ (30)

We denote by $\widetilde{L}:=L_{k}(r^{(p)})$ for notational convenience. Note
that $|\widetilde{L}|=k=|S|.$ Thus

$\displaystyle|S\backslash\widetilde{L}|=|S|-|S\cap\widetilde{L}|=|\widetilde{L}|-|S\cap\widetilde{L}|=|\widetilde{L}\backslash
S|.$ (31)

This means the number of elements in $S\backslash\widetilde{L}$ is equal to
the number of elements in $\widetilde{L}\backslash S.$ By the definition of
$\widetilde{L}$, the entries of $r^{(p)}=A^{T}(y-Ax^{(p)})$ supported on
$\widetilde{L}\backslash S$ are among the $k$ largest magnitudes of the
vector. This, together with (31), implies that

$\|(r^{(p)})_{S\backslash\widetilde{L}}\|_{2}\leq\|(r^{(p)})_{\widetilde{L}\backslash
S}\|_{2}.$ (32)

By (6), $S\cap\Lambda^{(p)}=\emptyset$ which together with (30) implies that

$S\cap\widehat{S}^{(p+1)}=S\cap(S^{(p)}\cup\Theta^{(p)}\cup\Lambda^{(p)})=S\cap
S^{(p)}.$ (33)

Note that $S=(S\backslash T)\cup(S\cap T)$ for any set $T,$ where $S\setminus
T$ and $S\cap T$ are disjoint. Thus by setting $T=\widehat{S}^{(p+1)}$ and
$T=\widetilde{L}$ respectively, we immediately obtain the following two
relations:

$\|(r^{(p)})_{S}\|_{2}^{2}=\|(r^{(p)})_{S\backslash\widehat{S}^{(p+1)}}\|_{2}^{2}+\|(r^{(p)})_{S\cap\widehat{S}^{(p+1)}}\|_{2}^{2},$
(34)
$\|(r^{(p)})_{S}\|_{2}^{2}=\|(r^{(p)})_{S\backslash\widetilde{L}}\|_{2}^{2}+\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}^{2}.$
(35)

Note that $x^{(p)}$ is a minimizer of the convex optimization problem
$\min\\{\|y-Az\|_{2}:\textrm{supp}(z)\subseteq S^{(p)}\\}.$ Thus $x^{(p)}$ and
$S^{(p)}$ satisfy (5), i.e.,

$(r^{(p)})_{S^{(p)}}=0.$ (36)

This together with (33) implies that
$\|(r^{(p)})_{S\cap\widehat{S}^{(p+1)}}\|_{2}^{2}=\|(r^{(p)})_{S\cap
S^{(p)}}\|_{2}^{2}=0.$ Thus, merging (34) and (35) yields

$\displaystyle\|(r^{(p)})_{S\backslash\widehat{S}^{(p+1)}}\|_{2}^{2}=\|(r^{(p)})_{S\backslash\widetilde{L}}\|_{2}^{2}+\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}^{2}.$
(37)

By (32), (36) and (37), one has

$\displaystyle\Omega^{2}$ $\displaystyle:=\|(r^{(p)})_{(S\cup
S^{(p)})\backslash\widehat{S}^{(p+1)}}\|_{2}^{2}=\|(r^{(p)})_{S\backslash\widehat{S}^{(p+1)}}\|_{2}^{2}=\|(r^{(p)})_{S\backslash\widetilde{L}}\|_{2}^{2}+\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}^{2}$
$\displaystyle\leq\|(r^{(p)})_{\widetilde{L}\backslash
S}\|_{2}^{2}+\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}^{2}$
$\displaystyle=\|(r^{(p)})_{\widetilde{L}\backslash(S\cup
S^{(p)})}\|_{2}^{2}+\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}^{2},$ (38)

where the last equality follows from (36). In fact, by eliminating the
components of $(r^{(p)})_{\widetilde{L}\backslash S}$ indexed by $S^{(p)},$ we
immediately see that

$\|(r^{(p)})_{\widetilde{L}\backslash
S}\|_{2}=\|(r^{(p)})_{\widetilde{L}\backslash(S\cup S^{(p)})}\|_{2}.$ (39)

We now estimate the last term $\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}^{2}$ in
(4.2). Note that the elements in $\Theta^{(p)}$ are added to $S^{(p)}$ to form
the next set $S^{(p+1)}.$ From the definition of $\Theta^{(p)},$ it contains
the indices in $\widetilde{L}=L_{k}(r^{(p)})$ such that

$|(r^{(p)})_{i}|\geq\gamma\|r^{(p)}\|_{\infty}.$

Clearly, we have either $|\Theta^{(p)}|<k$ or $|\Theta^{(p)}|=k.$ We now
consider the two cases separately.

_Case 1:_ $|\Theta^{(p)}|=k.$ In this case, all indices of $\widetilde{L}$ are
selected into $\Theta^{k}.$ So $\Theta^{(p)}=\widetilde{L}.$ Under the
assumption (30), it implies that
$S\cap\widetilde{L}=S\cap\Theta^{(p)}=\emptyset$ and hence
$\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}=0.$ As a result, the relation (4.2)
reduces to $\Omega\leq\|(r^{(p)})_{\widetilde{L}\backslash(S\cup
S^{(p)})}\|_{2}.$

_Case 2:_ $|\Theta^{(p)}|<k.$ In this case, by the structure of DOMP, not all
indices in $\widetilde{L}$ are selected into $\Theta^{(p)}.$ Without loss of
generality, we assume that $S\cap\widetilde{L}\not=\emptyset$ since otherwise
$\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}^{2}=0.$ Under the condition (30), we
see that
$(S\cap\widetilde{L})\cap\Theta^{(p)}=(S\cap\Theta^{(p)})\cap\widetilde{L}=\emptyset.$
So the indices in $S\cap\widetilde{L}$ are not in $\Theta^{(p)}$, and hence
$|(r^{(p)})_{i}|<\gamma\|r^{(p)}\|_{\infty}~{}\textrm{for all }i\in
S\cap\widetilde{L},$ which implies that

$\|(r^{(p)})_{S\cap\widetilde{L}}\|_{\infty}<\gamma\|r^{(p)}\|_{\infty}.$ (40)

Again, as $\Theta^{(p)}\subseteq\widetilde{L}$ and the elements in
$S\cap\widetilde{L}$ are not in $\Theta^{(p)},$ we must have that
$\Theta^{(p)}\subseteq\widetilde{L}\backslash(\widetilde{L}\cap
S)=\widetilde{L}\backslash S.$ Since the index of the largest magnitude of
$r^{(p)}$ is in $\Theta^{(p)},$ we have

$\|r^{(p)}\|_{\infty}=\|(r^{(p)})_{\Theta^{p}}\|_{\infty}\leq\|(r^{(p)})_{\Theta^{p}}\|_{2}\leq\|(r^{(p)})_{\widetilde{L}\backslash
S}\|_{2}.$

Merging (39) and the relation above yields

$\|r^{(p)}\|_{\infty}\leq\|(r^{(p)})_{\widetilde{L}\backslash(S\cup
S^{(p)})}\|_{2}.$ (41)

By using (40) and (41), we deduce that

$\displaystyle\|(r^{(p)})_{S\cap\widetilde{L}}\|_{2}$
$\displaystyle\leq\sqrt{|S\cap\widetilde{L}|}\|(r^{(p)})_{S\cap\widetilde{L}}\|_{\infty}<\gamma\sqrt{|S\cap\widetilde{L}|}\|r^{(p)}\|_{\infty}$
$\displaystyle\leq\gamma\sqrt{|S\cap\widetilde{L}|}\|(r^{(p)})_{\widetilde{L}\backslash(S\cup
S^{(p)})}\|_{2}$
$\displaystyle\leq\gamma\sqrt{k}\|(r^{(p)})_{\widetilde{L}\backslash(S\cup
S^{(p)})}\|_{2},$ (42)

where the last inequality follows from
$\gamma\sqrt{|S\cap\widetilde{L}|}\leq\gamma\sqrt{k}.$ Combining (4.2) and
(4.2) leads to

$\Omega\leq\sqrt{1+\gamma^{2}k}\left\|(r^{(p)})_{\widetilde{L}\backslash(S\cup
S^{(p)})}\right\|_{2}.$ (43)

So the bound (43) is valid in both Case 1 and Case 2. Since
$[\widetilde{L}\backslash(S\cup
S^{(p)})]\cap\textrm{supp}(x_{S}-x^{(p)})=\emptyset,$ by Lemma 4.1 (ii) and
(iii), we obtain

$\displaystyle\|(r^{(p)})_{\widetilde{L}\backslash(S\cup S^{(p)})}\|_{2}$
$\displaystyle=\|(A^{T}A(x_{S}-x^{(p)})+A^{T}\nu^{\prime})_{\widetilde{L}\backslash(S\cup
S^{(p)})}\|_{2}$
$\displaystyle\leq\|(A^{T}A(x_{S}-x^{(p)}))_{\widetilde{L}\backslash(S\cup
S^{(p)})}\|_{2}+\|(A^{T}\nu^{\prime})_{\widetilde{L}\backslash(S\cup
S^{(p)})}\|_{2}$
$\displaystyle\leq\delta_{k+|S^{(p)}|+|\widetilde{L}|}\|x_{S}-x^{(p)}\|_{2}+\sqrt{1+\delta_{k}}\|\nu^{\prime}\|_{2}$
$\displaystyle=\delta_{2k+|S^{(p)}|}\|x_{S}-x^{(p)}\|_{2}+\sqrt{1+\delta_{k}}\|\nu^{\prime}\|_{2}.$

Merging (43) and the relation above leads to

$\displaystyle\Omega\leq\sqrt{1+k\gamma^{2}}\left(\delta_{2k+|S^{(p)}|}\|x_{S}-x^{(p)}\|_{2}+\sqrt{1+\delta_{k}}\|\nu^{\prime}\|_{2}\right).$
(44)

Denote by $W:=[(x_{S}-x^{(p)})-A^{T}(y-Ax^{(p)})]_{(S\cup
S^{(p)})\setminus\widehat{S}^{(p+1)}}.$ Note that
$|\textrm{supp}(x_{S}-x^{(p)})|\leq k+|S^{(p)}|$ and $|(S\cup
S^{(p)})\setminus\widehat{S}^{(p+1)}|\leq|S|=k$ since
$S^{(p)}\subseteq\widehat{S}^{(p+1)}.$ By Lemma 4.1 (i) and (iii), one has

$\displaystyle\|W\|_{2}$
$\displaystyle=\|[(I-A^{T}A)(x_{S}-x^{(p)})-A^{T}\nu^{\prime}]_{(S\cup
S^{(p)})\backslash\widehat{S}^{(p+1)}}\|_{2}$
$\displaystyle\leq\delta_{k+|S^{(p)}|}\|x_{S}-x^{(p)}\|_{2}+\sqrt{1+\delta_{k}}\|\nu^{\prime}\|_{2}.$
(45)

Note that $x_{S}-x^{(p)}=(x_{S}-x^{(p)})_{(S\cup S^{(p)})}$ since
$\textrm{supp}(x_{S}-x^{(p)})\subseteq S\cup S^{(p)}.$ We have

$\displaystyle\|(x_{S}-x^{(p)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2}$
$\displaystyle=\|(x_{S}-x^{(p)})_{(S\cup
S^{(p)})\backslash\widehat{S}^{(p+1)}}\|_{2}$
$\displaystyle=\|[x_{S}-x^{(p)}-A^{T}(y-Ax^{(p)})]_{(S\cup
S^{(p)})\backslash\widehat{S}^{(p+1)}}$
$\displaystyle~{}~{}~{}+[A^{T}(y-Ax^{(p)})]_{(S\cup
S^{(p)})\backslash\widehat{S}^{(p+1)}}\|_{2}$
$\displaystyle\leq\|W\|_{2}+\Omega.$ (46)

Denote by $\phi:=1+\sqrt{1+k\gamma^{2}}.$ By combining (44), (4.2) and (4.2),
we immediately obtain that

$\displaystyle\|(x_{S}-x^{(p)})_{\overline{\widehat{S}^{(p+1)}}}\|_{2}$
$\displaystyle=\left(\delta_{k+|S^{(p)}|}+\sqrt{1+k\gamma^{2}}\delta_{2k+|S^{(p)}|}\right)\|x_{S}-x^{(p)}\|_{2}+\phi\sqrt{1+\delta_{k}}\|\nu^{\prime}\|_{2}$
$\displaystyle\leq\phi\left(\delta_{2k+|S^{(p)}|}\|x_{S}-x^{(p)}\|_{2}+\sqrt{1+\delta_{k}}\|\nu^{\prime}\|_{2}\right),$

where the last inequality follows from the fact
$\delta_{k+|S^{(p)}|}\leq\delta_{2k+|S^{(p)}|}.$ Thus (29) is satisfied.
$\Box$

We have all ingredients needed to show the main result stated in Theorem 4.2.

_The proof of Theorem 4.2:_ Let $x^{(p)}$ be the current iterate and
$S^{(p)},\Theta^{(p)},S^{(p+1)}$ and $x^{(p+1)}$ are defined by DOMP. Without
loss of generality, we assume $r^{(p)}\not=0.$ Let $\widehat{S}^{(p+1)}$ be
defined as (AC1) and $\widehat{x}^{(p+1)}$ be a solution to the auxiliary
minimization problem in (AC2). Still, $S=L_{k}(x)$ is the index set for the
$k$ largest magnitudes of the target vector $x.$ At the $p$th iteration, there
are only two cases: either $S\cap\Theta^{(p)}\not=\emptyset$ or
$S\cap\Theta^{(p)}=\emptyset.$

_Case 1:_ $S\cap\Theta^{(p)}\not=\emptyset.$ In this case, at least one of the
indices in $S$ is added to $S^{(p+1)}=S^{(p)}\cup\Theta^{p}.$ By (7),
$\Theta^{(p)}\cap S^{(p)}=\emptyset.$ Thus set $S^{(p+1)}$ contains more
elements of $S$ than $S^{(p)}$ in this case. Note that
$\textrm{supp}(x^{(p)})\subseteq S^{(p)}\subseteq S^{(p+1)}.$ Thus $x^{(p)}$
is a feasible vector to the optimization problem (DOMP2), to which $x^{(p+1)}$
is a minimizer. Thus by optimality, one has

$\|y-Ax^{(p+1)}\|_{2}\leq\|y-Ax^{(p)}\|_{2}.$

Note that $y=Ax_{S}+\nu^{\prime}$ where $\nu^{\prime}=Ax_{\overline{S}}+\nu.$
By the triangular inequality, it follows from the inequality above that

$\|A(x_{S}-x^{(p+1)})\|_{2}-\|\nu^{\prime}\|_{2}\leq\|A(x_{S}-x^{(p)})\|_{2}+\|\nu^{\prime}\|_{2},$

By noting that $|\textrm{supp}(x_{S}-x^{(p+1)})|\leq k+|S^{(p+1)}|$ and
$|\textrm{supp}(x_{S}-x^{(p)})|\leq k+|S^{(p)}|$ and by the definition of RIC
of $A$, the inequality above implies that

$\displaystyle\sqrt{1-\delta_{k+|S^{(p+1)}|}}\|x^{(p+1)}-x_{S}\|_{2}\leq\sqrt{1+\delta_{k+|S^{(p)}|}}\|x^{(p)}-x_{S}\|_{2}+2\|\nu^{\prime}\|_{2}.$

Since $\delta_{k+|S^{(p)}|}\leq\delta_{k+|S^{(p+1)}|},$ one has

$\displaystyle\|x^{(p+1)}-x_{S}\|_{2}\leq\sqrt{\frac{1+\delta_{k+|S^{(p+1)}|}}{1-\delta_{k+|S^{(p+1)}|}}}\|x^{(p)}-x_{S}\|_{2}+\frac{2}{\sqrt{1-\delta_{k+|S^{(p+1)}|}}}\|\nu^{\prime}\|_{2}.$
(47)

The first relation in (9) implies that
$|S^{(p+1)}|=\sum_{i=1}^{p}|\Theta^{(i)}|,$ which means $\\{|S^{(p)}|\\}$ is
nondecreasing sequence. Let $p^{*}$ denote the largest integer number $p$ such
that $|S^{(p+1)}|\leq(c-2)k.$ Then for any $p\leq p^{*},$ the coefficients on
the right-hand side of (47) are bounded by

$\sqrt{\frac{1+\delta_{k+|S^{(p+1)}|}}{1-\delta_{k+|S^{(p+1)}|}}}\leq\varrho:=\sqrt{\frac{1+\delta_{ck}}{1-\delta_{ck}}},~{}\frac{2}{\sqrt{1-\delta_{k+|S^{(p+1)}|}}}\leq
c_{1}:=\frac{2}{\sqrt{1-\delta_{ck}}}.$ (48)

Thus it follows from (47) and (48) that

$\|x^{(p+1)}-x_{S}\|_{2}\leq\varrho\|x^{(p)}-x_{S}\|_{2}+c_{1}\|\nu^{\prime}\|_{2}$
(49)

for any $p\leq p^{*}.$ We now analyze the second case.

_Case 2:_ $S\cap\Theta^{(p)}=\emptyset.$ Let $p^{*}$ be defined as above,
i.e., $p^{*}$ is the largest number $p$ such that $|S^{(p+1)}|\leq(c-2)k.$
Denote by $\phi=1+\sqrt{1+k\gamma^{2}}.$ By Lemmas 4.7 and 4.8, we immediately
obtain that

$\displaystyle\|x_{S}$ $\displaystyle-\widehat{x}^{(p+1)}\|_{2}$ (50)
$\displaystyle\leq\frac{\phi(\delta_{2k+|S^{(p)}|}\|x_{S}-x^{(p)}\|_{2}+\sqrt{1+\delta_{k}}\|\nu^{\prime}\|_{2})}{\sqrt{1-\delta^{2}_{k+|\widehat{S}^{(p+1)}|}}}+\frac{\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}\|\nu^{\prime}\|_{2}}{1-\delta_{k+|\widehat{S}^{(p+1)}|}}$
$\displaystyle=\frac{\phi\delta_{2k+|S^{(p)}|}\|x_{S}-x^{(p)}\|_{2}}{\sqrt{1-\delta^{2}_{k+|\widehat{S}^{(p+1)}|}}}+\left(\frac{\phi\sqrt{1+\delta_{k}}}{\sqrt{1-\delta^{2}_{k+|\widehat{S}^{(p+1)}|}}}+\frac{\sqrt{1+\delta_{|\widehat{S}^{(p+1)}|}}}{1-\delta_{k+|\widehat{S}^{(p+1)}|}}\right)\|\nu^{\prime}\|_{2}$
$\displaystyle\leq\frac{\phi\delta_{2k+|S^{(p+1)}|}\|x_{S}-x^{(p)}\|_{2}}{\sqrt{1-\delta^{2}_{2k+|S^{(p+1)}|}}}+\left(\frac{\phi\sqrt{1+\delta_{k}}}{\sqrt{1-\delta^{2}_{2k+|S^{(p+1)}|}}}+\frac{\sqrt{1+\delta_{2k+|S^{(p+1)}|}}}{1-\delta_{2k+|S^{(p+1)}|}}\right)\|\nu^{\prime}\|_{2}$
$\displaystyle\leq\frac{\phi\delta_{ck}\|x_{S}-x^{(p)}\|_{2}}{\sqrt{1-\delta^{2}_{ck}}}+\left(\frac{\phi\sqrt{1+\delta_{k}}}{\sqrt{1-\delta^{2}_{ck}}}+\frac{\sqrt{1+\delta_{ck}}}{1-\delta_{ck}}\right)\|\nu^{\prime}\|_{2},$
(51)

where the second inequality follows from the fact that
$\delta_{2k+|S^{(p)}|}\leq\delta_{2k+|S^{(p+1)}|}$ since
$|S^{(p)}|\leq|S^{(p+1)}|$, and that
$\delta_{k+|\widehat{S}^{(p+1)}|}\leq\delta_{2k+|S^{(p+1)}|}$ since
$|\widehat{S}^{(p+1)}|=|S^{(p+1)}|+|\Lambda^{(p)}|\leq k+|S^{(p+1)}|$ which
follows from the second relation in (9). The last inequality follows from the
fact $\delta_{2k+|S^{(p+1)}|}\leq\delta_{ck}$ due to $p\leq p^{*}.$ Denote by

$\epsilon:=\frac{\vartheta_{(y,A)}}{\sqrt{1-\delta_{ck}}}\left(\sqrt{\left(\frac{2}{\sqrt{\sigma}}+\frac{\|A\|_{2}}{\sigma}\right)\|A\|_{2}}+\frac{\|A\|_{2}}{\sqrt{\sigma}}\right),$
(52)

where $\vartheta_{(y,A)}$ and $\sigma$ are defined in Lemma 3.1. Since
$\textrm{supp}(\widehat{x}^{(p+1)}-x^{(p+1)})\subseteq\widehat{S}^{(p+1)},$ by
the definition of RIC of $A$ and Lemma 3.1, we have

$\displaystyle\|\widehat{x}^{(p+1)}-x^{(p+1)}\|_{2}$
$\displaystyle\leq\frac{1}{\sqrt{1-\delta_{|\widehat{S}^{(p+1)}|}}}\|A(\widehat{x}^{(p+1)}-x^{(p+1)})\|_{2}\leq\frac{1}{\sqrt{1-\delta_{ck}}}\|A(\widehat{x}^{(p+1)}-x^{(p+1)})\|_{2}$
$\displaystyle\leq\frac{\vartheta_{(y,A)}}{\sqrt{1-\delta_{ck}}}\left(\sqrt{\left(\frac{2}{\sqrt{\sigma}}+\frac{\|A\|_{2}}{\sigma}\right)\|A\|_{2}}+\frac{\|A\|_{2}}{\sqrt{\sigma}}\right)$
$\displaystyle=\epsilon.$ (53)

Then using the triangular inequality and (50) and (4.2) yields

$\displaystyle\|x_{S}-x^{(p+1)}\|_{2}$
$\displaystyle\leq\|x_{S}-\widehat{x}^{(p+1)}\|_{2}+\|\widehat{x}^{(p+1)}-x^{(p+1)}\|_{2}$
$\displaystyle\leq\frac{\phi\delta_{ck}}{\sqrt{1-\delta^{2}_{ck}}}\|x_{S}-x^{(p)}\|_{2}+\left(\frac{\phi\sqrt{1+\delta_{k}}}{\sqrt{1-\delta^{2}_{ck}}}+\frac{\sqrt{1+\delta_{ck}}}{1-\delta_{ck}}\right)\|\nu^{\prime}\|_{2}+\epsilon$
$\displaystyle=\beta\|x_{S}-x^{(p)}\|_{2}+c_{2}\|\nu^{\prime}\|_{2}+\epsilon,$
(54)

where the constants $\beta$ and $c_{2}$ are given by

$\beta=\frac{\phi\delta_{ck}}{\sqrt{1-\delta^{2}_{ck}}},~{}~{}c_{2}=\left(\frac{\phi\sqrt{1+\delta_{k}}}{\sqrt{1-\delta^{2}_{ck}}}+\frac{\sqrt{1+\delta_{ck}}}{1-\delta_{ck}}\right).$
(55)

It is easy to verify that $\beta<1$ under the assumption of the theorem. In
fact, $\beta=\frac{\phi\delta_{ck}}{\sqrt{1-\delta^{2}_{ck}}}<1$ is guaranteed
under the condition

$\delta_{ck}<\frac{1}{\sqrt{1+\phi^{2}}}=\frac{1}{\sqrt{1+\left(1+\sqrt{1+k\gamma^{2}}\right)^{2}}}.$

Suppose that the algorithm DOMP has performed $p$ iterations where $p\leq
p^{*}.$ Without loss of generality, suppose that within these $p$ iterations
the aforementioned _Case 1_ appears $\tau^{*}$ times, and thus _Case 2_
appears $p-\tau^{*}$ times. Clearly, _Case 1_ appears at most $k$ times since
$|S|=k,$ so $\tau^{*}\leq k.$ The error bound for this case is given by (49),
and the error bound for Case 2 is given by (4.2). Therefore, it is not
difficult to verify that after $p$ iterations, one has

$\displaystyle\|x_{S}-x^{(p+1)}\|_{2}\leq(\varrho^{\tau^{*}}\beta^{p-\tau^{*}})\|x_{S}-x^{(0)}\|_{2}+c_{1}\beta^{p-\tau^{*}}\left(\frac{\varrho^{\tau^{*}}-1}{\varrho-1}\right)\|\nu^{\prime}\|_{2}+\frac{c_{2}\|\nu^{\prime}\|_{2}+\epsilon}{1-\beta}.$
(56)

where all constants $(\beta,\varrho,c_{1},c_{2})$ are determined only by
$\delta_{ck}$ and/or $k$ and $\gamma.$ To see (56), without loss of
generality, we assume that the first $\tau^{*}$ iterations correspond to Case
1, and the remaining $p-\tau^{*}$ iterations correspond to Case 2. Then using
the fact
$\sum_{i=0}^{p-\tau^{*}-1}\beta^{i}=(1-\beta^{p-\tau^{*}})/(1-\beta)<1/(1-\beta)$
for $\beta<1,$ it follows from (4.2) that

$\displaystyle\|x_{S}-x^{(p+1)}\|_{2}$
$\displaystyle\leq\beta^{p-\tau^{*}}\|x_{S}-x^{(\tau^{*}+1)}\|_{2}+(1+\beta+\dots+\beta^{p-\tau^{*}-1})(c_{2}\|\nu^{\prime}\|_{2}+\epsilon)$
$\displaystyle\leq\beta^{p-\tau^{*}}\|x_{S}-x^{(\tau^{*}+1)}\|_{2}+\frac{c_{2}\|\nu^{\prime}\|_{2}+\epsilon}{1-\beta}.$
(57)

Also, by (49) and using the fact
$\sum_{i=0}^{\tau^{*}-1}\varrho^{i}=(\varrho^{\tau^{*}}-1)/(\varrho-1)$ where
$\varrho>1,$ we obtain

$\displaystyle\|x_{S}-x^{(\tau^{*}+1)}\|_{2}$
$\displaystyle\leq\varrho^{\tau^{*}}\|x_{S}-x^{(0)}\|_{2}+(1+\varrho+\dots+\varrho^{\tau^{*}-1})(c_{1}\|\nu^{\prime}\|_{2})$
$\displaystyle=\varrho^{\tau^{*}}\|x_{S}-x^{(0)}\|_{2}+c_{1}\left(\frac{\varrho^{\tau^{*}}-1}{\varrho-1}\right)\|\nu^{\prime}\|_{2}.$
(58)

Merging (4.2) and (4.2) yields

$\displaystyle\|x_{S}-x^{(p+1)}\|_{2}\leq\beta^{p-\tau^{*}}(\varrho^{\tau^{*}}\|x_{S}-x^{(0)}\|_{2})+c_{1}\beta^{p-\tau^{*}}\left(\frac{\varrho^{\tau^{*}}-1}{\varrho-1}\right)\|\nu^{\prime}\|_{2}+\frac{c_{2}\|\nu^{\prime}\|_{2}+\epsilon}{1-\beta},$

which is exactly the error bound given in (56). Note that the coefficients
$(\varrho/\beta)^{\tau^{*}}\leq(\varrho/\beta)^{k}$ and
$c_{1}\beta^{p-\tau^{*}}\left(\frac{\varrho^{\tau^{*}}-1}{\varrho-1}\right)\leq
c_{1}\left(\frac{\varrho^{k}-1}{\varrho-1}\right)$ since $\beta<1,$
$\varrho>1$ and $\tau^{*}\leq k.$ Thus we deduce that

$\displaystyle\|x_{S}-x^{(p+1)}\|_{2}\leq\beta^{p}\left[(\varrho/\beta)^{k}\|x_{S}-x^{(0)}\|_{2}\right]+\tau\|\nu^{\prime}\|_{2}+\epsilon/(1-\beta).$
(59)

where

$\tau=c_{1}\left(\frac{\varrho^{k}-1}{\varrho-1}\right)+\frac{c_{2}}{1-\beta},$

with $c_{1}=2/\sqrt{1-\delta_{ck}},$ and $c_{2}$ is the constant given in
(55). The term $(\varrho/\beta)^{k}\|x_{S}-x^{(0)}\|_{2}$ in (59) is a fixed
quantity. In (59), only the last term $\epsilon/(1-\beta)$ depends on
$\sigma$, and we see from the definition of $\epsilon$ that $\epsilon\to 0$ as
$\sigma\to\infty.$ Therefore, the desired estimation (21) is obtained. $\Box$

###  4.3 Error bound for EDOMP

The EDOMP algorithm shares the same steps of DOMP when $|S^{(p)}|\leq k,$ and
performs hard thresholding to restore the $k$-sparsity of iterates when
$|S^{(p)}|>k.$ The next two lemmas are utilized in the analysis of EDOMP. The
first one was shown in [58], and can also be shown from the results in [41].
The second one was summarized in [32] (similar properties have been used in
such references as [20, 57, 59]).

###### Lemma 4.9

[58] For any vector $z\in\mathbb{R}^{n}$ and for any $k$-sparse vector
$w\in\mathbb{R}^{n},$ one has

$\|w-{\cal H}_{k}(z)\|_{2}\leq\frac{\sqrt{5}+1}{2}\|(w-z)_{T^{\\#}\cup
T^{*}}\|_{2},$ (60)

where $T^{\\#}={\rm supp}(w)$ and $T^{*}={\rm supp}({\cal H}_{k}(z)).$

###### Lemma 4.10

[32] Denote by $y:=Ax_{S}+\nu^{\prime}$ where $S=L_{k}(x).$ Let
$v\in\mathbb{R}^{n}$ be an arbitrary $k$-sparse vector. Then the solution of
the projection problem

$z^{*}=\mathop{\arg\min}_{z\in\mathbb{R}^{n}}\\{\|y-Az\|_{2}:~{}{\rm
supp}(z)\subseteq{\rm supp}(v)\\}$

satisfies that

$\|z^{*}-x_{S}\|_{2}\leq\frac{1}{\sqrt{1-(\delta_{2k})^{2}}}\|x_{S}-v\|_{2}+\frac{\sqrt{1+\delta_{k}}}{1-\delta_{2k}}\|\nu^{\prime}\|_{2}.$

We now state and show the main result concerning the reconstruction error
bound via EDOMP.

###### Theorem 4.11

Let $y:=Ax+\nu$ be the measurements of the data $x\in\mathbb{R}^{n}$ with
measurement errors $\nu,$ and denote by $S=L_{k}(x).$ Given a constant
$\gamma\in(0,1]$, if the RIC of order $ck$ $(c>2)$ of the matrix $A$ obeys

$\delta_{ck}<\frac{2}{\sqrt{4+\eta^{2}\left(1+\sqrt{1+k\gamma^{2}}\right)^{2}}+\eta\left(1+\sqrt{1+k\gamma^{2}}\right)},$
(61)

where $\eta=(\sqrt{5}+1)/2,$ then at the $p$th iteration with
$|S^{(p+1)}|\leq(c-2)k$, the iterate $x^{(p+1)}$ generated by EDOMP
approximates $x_{S}$ with error

$\displaystyle\|x^{(p+1)}-x_{S}\|_{2}\leq(\beta^{*})^{p}(\varrho/\beta)^{k}\|x_{S}-x^{(0)}\|_{2}+\tau^{*}\|\nu^{\prime}\|_{2},$
(62)

where $\beta^{*}<1$ is given by

$\beta^{*}:=\left(\frac{\sqrt{5}+1}{2\sqrt{1-\delta_{ck}^{2}}}\right)\frac{\left(1+\sqrt{1+k\gamma^{2}}\right)\delta_{ck}}{\sqrt{1-\delta^{2}_{ck}}}.$

The constants $\beta$ and $\varrho$ in (62) are given as in Theorem 4.2, and
the constant $\tau^{*}$ depends on $\delta_{ck}$, $k$ and $\gamma$ only.

_Proof._ The proof is straightforward based on that of Theorem 4.2. By the
structure of EDOMP, at the current $x^{(p)},$ the algorithm first generates
the intermediate point $\widetilde{x}^{(p+1)}$ and then decides whether to
accept it as $x^{(p+1)}$ or not. For notational simplicity, we denote by
$u:={\cal H}_{k}(\widetilde{x}^{(p+1)}).$ If $|S^{(p+1)}|\leq k$, then
$\widetilde{x}^{(p+1)}$ is $k$-sparse and EDOMP takes
$x^{(p+1)}=\widetilde{x}^{(p+1)}$ directly, and hence in this case
$\|x_{S}-u\|_{2}=\|x_{S}-\widetilde{x}^{(p+1)}\|_{2};$ otherwise, if
$|S^{(p+1)}|>k,$ the algorithm performs an orthogonal projection on the
support $\Omega=L_{k}(\widetilde{x}^{(p+1)})$ to produce $x^{(p+1)}.$ It
follows immediately from Lemma 4.9 (by setting $z=\widetilde{x}^{(p+1)}$ and
$w=x_{S}$) that

$\displaystyle\|x_{S}-u\|_{2}\leq\frac{\sqrt{5}+1}{2}\|(x_{S}-\widetilde{x}^{(p+1)})_{S\cup
T^{*}}\|_{2},$

where $T^{*}=\textrm{supp}(u).$ Thus, no matter which case (i.e.,
$|S^{(p+1)}|\leq k$ or $|S^{(p+1)}|>k$), the following relation is always
satisfied:

$\|x_{S}-u\|_{2}\leq\frac{\sqrt{5}+1}{2}\|(x_{S}-\widetilde{x}^{(p+1)})\|_{2}.$
(63)

Note that the intermediate point $\widetilde{x}^{(p+1)}$ is generated by the
same step of DOMP at the $p$th iteration. As shown in the proof of Theorem
4.2, at the $p$th iteration, there are only two cases: $\Theta^{(p)}\cap
S\not=\emptyset$ and $\Theta^{(p)}\cap S=\emptyset.$ For the former, one has

$\|\widetilde{x}^{(p+1)}-x_{S}\|_{2}\leq\varrho\|x^{(p)}-x_{S}\|_{2}+c_{1}\|\nu^{\prime}\|_{2},$

and for the latter, one has

$\|\widetilde{x}^{(p+1)}-x_{S}\|_{2}\leq\beta\|x_{S}-x^{(p)}\|_{2}+c_{2}\|\nu^{\prime}\|_{2}+\epsilon,$

where $\varrho,\beta,c_{1}$ and $c_{2}$ are the same constants in Theorem 4.2
and $\epsilon$ is defined in (52). By considering the two cases, it follows
from (63) that the vector $u$ approximates $x_{S}$ either with error

$\|x_{S}-u\|_{2}\leq\widehat{\varrho}\|x^{p}-x_{S}\|_{2}+\widehat{c}_{1}\|\nu^{\prime}\|_{2},$
(64)

or with the error

$\|x_{S}-u\|_{2}\leq\widehat{\beta}\|x_{S}-x^{(p)}\|_{2}+\widehat{c}_{2}\|\nu^{\prime}\|_{2}+\widehat{\epsilon},$
(65)

where

$(\widehat{\beta},\widehat{\varrho},\widehat{c}_{1},\widehat{c}_{2},\widehat{\epsilon})=\frac{\sqrt{5}+1}{2}(\beta,\varrho,c_{1},c_{2},\epsilon).$
(66)

When the EDOMP algorithm performs an orthogonal projection with
$Q=L_{k}(\widetilde{x}^{(p+1)})=L_{k}({\cal H}_{k}(\widetilde{x}^{(p+1)})).$
Noting that $u={\cal H}_{k}(\widetilde{x}^{(p+1)})$ is $k$-sparse, we conclude
from Lemma 4.10 that the iterate $x^{(p+1)}$ generated by EDOMP satisfies that

$\displaystyle\|x^{(p+1)}-x_{S}\|_{2}$
$\displaystyle\leq\frac{\|x_{S}-u\|_{2}}{\sqrt{1-(\delta_{2k})^{2}}}+\frac{\sqrt{1+\delta_{k}}}{1-\delta_{2k}}\|\nu^{\prime}\|_{2}\leq\frac{\|x_{S}-u\|_{2}}{\sqrt{1-\delta_{ck}^{2}}}+\zeta\|\nu^{\prime}\|_{2},$
(67)

where $\zeta:=\frac{\sqrt{1+\delta_{k}}}{1-\delta_{2k}}.$ In (67), the term
$\|x_{S}-u\|_{2}$ is bounded as either (64) or (65)). Thus we conclude that
the iterates $x^{(p+1)}$ generated by EDOMP satisfies either

$\|x^{(p+1)}-x_{S}\|_{2}\leq\varrho^{*}\|x^{(p)}-x_{S}\|_{2}+(c^{*}_{1}+\zeta)\|\nu^{\prime}\|_{2}$

or

$\|x^{(p+1)}-x_{S}\|_{2}\leq\beta^{*}\|x^{(p)}-x_{S}\|_{2}+(c^{*}_{2}+\zeta)\|\nu^{\prime}\|_{2}+\epsilon^{*},$

where the constants $(\beta^{*},\rho^{*},c^{*}_{1},c^{*}_{2},\epsilon^{*})$
are given by

$(\beta^{*},\rho^{*},c^{*}_{1},c^{*}_{2},\epsilon^{*})=\frac{1}{\sqrt{1-\delta_{ck}^{2}}}(\widehat{\beta},\widehat{\rho},\widehat{c}_{1},\widehat{c}_{2},\widehat{\epsilon})=\frac{\sqrt{5}+1}{2\sqrt{1-\delta_{ck}^{2}}}(\beta,\rho,c_{1},c_{2},\epsilon).$
(68)

By a similar analysis in Theorem 4.2, the first case above happens at most $k$
times, and the second case happens at least $p-k$ times. Therefore, By the
same analysis of (59) and by noting that
$\varrho^{*}/\beta^{*}=\widehat{\varrho}/\widehat{\beta}=\varrho/\beta,$ we
finally obtain the following bound

$\displaystyle\|x^{(p+1)}-x_{S}\|_{2}\leq(\beta^{*})^{p}\left[(\varrho/\beta)^{k}\|x_{S}-x^{(0)}\|_{2}\right]+\tau^{*}\|\nu^{\prime}\|_{2},$

where $\tau^{*}$ is a constant depending only on $\delta_{ck}$, $k$ and
$\gamma$. To ensure the constant

$\beta^{*}:=\left(\frac{\sqrt{5}+1}{2\sqrt{1-\delta_{ck}^{2}}}\right)\frac{\left(1+\sqrt{1+k\gamma^{2}}\right)\delta_{ck}}{\sqrt{1-\delta^{2}_{ck}}}<1,$
(69)

it is sufficient to require that $\delta_{ck}$ is bounded as (61). $\Box$

Similar to Corollary 4.3, the results (omitted here) for EDOMP can be stated
in terms of the highest order of RIP. It is also worth mentioning that a
further improvement of the reconstruction capability of EDOMP might be
achieved, in theory, via the optimal $k$-thresholding technique introduced
recently in [57, 59]. Such an investigation, however, goes beyond the scope of
this paper.

The main results established in this section provide the estimation for the
distance between the significant components of the target data and the
solution generated by the proposed algorithms. The results claim that the
reconstruction quality becomes better and better as the iteration proceeds
provided that $|S^{(p)}|\leq(c-2)k,$ where $k$ is the sparsity level of the
target data and $ck$ is the order of the RIC of the measurement matrix. In
this process, the algorithm gradually identifies the correct support of the
sparse data and the iterate $x^{(p)}$ gets closer and closer to the
significant components of the target data. When $m,n$ are particularly large
with $n\gg m$ and the highest order RIC of $A$ satisfies that $t^{\max}\gg
2k$, the proposed algorithms can perform enough iterations to guarantee that
the reconstruction error becomes so small that the finite convergence of the
algorithms can be achieved, as discussed in the next subsection.

###  4.4 Finite convergence

The basic assumption in compressed sensing is that the number of measurements
$m$ is much lower than the signal length $n,$ i.e., $m\ll n.$ It is also well
known that to ensure the target $k$-sparse data being exactly reconstructed,
the target data should be sparse enough so that it is the unique sparsest
solution to the underdetermined linear system $y=Ax$ (see, e.g., [18]). Thus
in this section, we consider the reconstruction problems satisfying the
following assumption.

###### Assumption 4.12

$k\ll m\ll n,$ and $2k\ll t^{\max},$ where $t^{\max}$ is the highest order of
RIP of the measurement matrix $A.$

The problem in such a setting may be referred to as a large-scale compressed
sensing problem for which the proposed algorithms can perform enough
iterations so that significant information of the target data can be
guaranteed to reconstruct. In fact, recall that $p^{*}$ denotes the largest
number of iterations such that $|S^{(p^{*}+1)}|\leq(c-2)k,$ i.e.,
$\sum_{i=1}^{p^{*}}|\Theta^{(i)}|\leq(c-2)k.$ This implies that
$\sum_{i=1}^{p^{*}+1}|\Theta^{(i)}|>(c-2)k$ which together with
$|\Theta^{(i)}|\leq k$ implies that $(p^{*}+1)k>(c-2)k$, i.e., $p^{*}\geq
c-2.$ Thus $p^{*}$ would be a large number when $c\gg 2$ which is guaranteed
when $2k\ll t^{\max}.$

We now point out that for large-scale compressed sensing problems, the
proposed algorithm can exactly reconstruct the support of $x_{S}$ in a finite
number of iterations as long as $\|Ax_{\overline{S}}+\nu\|_{2}$ is small
enough. We say that the vector $x$ is _nondegenerated $k$-compressible_ if it
has at least $k$ nonzero components and $\|x_{\overline{S}}\|_{2}$ is
sufficiently small, where $S=L_{k}(x).$ For such a vector, $x_{i}\not=0$ for
all $i\in S.$ Clearly, any $k$-sparse vector with $k$ nonzeros must be
nondegenerated $k$-compressible.

###### Theorem 4.13

Assume that the data $x\in\mathbb{R}^{n}$ is nondegenerated $k$-compressible.
Let $y:=Ax+\nu$ be the slightly inaccurate measurements of $x$ in the sense
that the errors $\nu$ are sufficiently small. Let $\gamma\in(0,1]$ be a given
constant in DOMP and EDOMP. Then under Assumption 4.12, the following two
statements are valid:

  * (i)

If $A$ has the RIP of order $ck$ with $t^{\max}\geq ck\gg 2k$ and
$\delta_{ck}$ satisfies (21), then there exists $\widehat{p}$ such that for
any $p$ with $\widehat{p}\leq p\leq p^{*},$ the iterate $x^{(p)}$ generated by
DOMP satisfies that $L_{k}(x^{(p)})=L_{k}(x).$

  * (ii)

If $A$ has the RIP of order $ck$ with $t^{\max}\geq ck\gg 2k$ and
$\delta_{ck}$ satisfies (61), then there exists $\widehat{p}$ such that for
any $p$ with $\widehat{p}\leq p\leq p^{*},$ the iterate $x^{(p)}$ generated by
EDOMP satisfies that ${\rm supp}(x^{(p)})=L_{k}(x).$ Furthermore, if $x$ is
$k$-sparse and the measurements $y$ are accurate, then $x^{(p)}=x.$

_Proof._ (i) Under (21), Theorem 4.2 claims that

$\|x^{(p)}-x_{S}\|_{2}\leq\beta^{p-1}(\frac{\varrho}{\beta})^{k}\|x^{0}-x_{S}\|_{2}+\tau\|\nu^{\prime}\|,$
(70)

where $S=L_{k}(x)$ and all constants $(\beta,\varrho,\tau)$ are given in
Theorem 4.2. By assumption, the right-hand side of the above bound is
sufficiently small when $p$ is large enough. Note that

$\|x^{(p)}-x_{S}\|_{2}^{2}=\|(x^{(p)})_{S}-x_{S}\|_{2}^{2}+\|(x^{(p)})_{\overline{S}}\|_{2}^{2}.$

It follows from (70) that both terms $\|(x^{(p)})_{S}-x_{S}\|_{2}$ and
$\|(x^{(p)})_{\overline{S}}\|_{2}$ are sufficiently small when $p$ is large
enough, which is ensured under the assumption of the theorem. This, together
with the fact that $x$ is ‘nondegenerated $k$-compressible’, implies that the
largest $k$ magnitudes of $x^{(p)}$ are concentrated on $S$ and sufficiently
close to $x_{S}.$ This means $L_{k}(x^{(p)})=S.$ Thus after performing enough
iterations, the support of $x_{S}$ is correctly reconstructed by DOMP.

(ii) Under (61), Theorem 4.11 shows that the error bound (62) is valid. By the
same analysis above, we conclude that under the assumption of the theorem,
there exists $\widehat{p}$ such that the iterate $x^{(p)}$ generated by EDOMP
must satisfy that $\textrm{supp}(x^{(p)})=S$ provided that $\widehat{p}\leq
p\leq p^{*}.$ If $x$ is $k$-sparse and the measurements $y$ are accurate, then
$\textrm{supp}(x^{(p)})=\textrm{supp}(x).$ Furthermore, when the measurements
are accurate, by optimality of $x^{(p)}$ (which is a solution to the
orthogonal projection problem in the last step of EDOMP), we have that
$\|y-Ax^{(p)}\|_{2}\leq\|y-Ax\|_{2}=0.$ Since both $x^{(p)}$ and $x$ are
$k$-sparse solutions to the underdetermined linear system $y=Az.$ Under the
RIP assumption, the system $y=Az$ can only have a unique $k$-sparse solution.
Therefore, $x^{(p)}=x.$ $\Box$

The error bounds established in this paper measure how close the iterates
generated by the algorithm to the true target data in terms of $\delta_{ck},$
the number of iterations $p,$ and the measurement error $\|\nu\|_{2}.$ The
bounds indicate that as the number of iterations $p$ increases, the
reconstruction error decays provided that $p\leq p^{*}.$ In the setting of
large-scale compressed sensing, Theorem 4.11 further claims that the exact
reconstruction of the sparse data can be also possible under the assumption of
the theorem.

##  5 Numerical experiments

The performance of the proposed algorithms is clearly related to three main
factors: (a) the choice of parameter $\gamma,$ (b) the relative sparsity level
$k/m$ or $k/n$, and (c) the total number of iterations executed. We first
carry out experiments to demonstrate how these factors affect the performance
of the proposed algorithms and thus to suggest the suitable choice of $\gamma$
as well as the number of iterations to perform. All sparse vectors and
measurement matrices in experiments are randomly generated. The entries of
sparse vectors and matrices are assumed to be independent and identically
distributed and follow the standard normal distribution, and the positions of
nonzero entries of sparse vectors are uniformly distributed. All iterative
algorithms involved in our experiments use $x^{(0)}=0$ as the initial point.
Unless otherwise stated, we adopt the following reconstruction criterion:

$\|x^{(p)}-x\|_{2}/\|x\|_{2}\leq 10^{-5},$ (71)

where $x^{(p)}$ is the iterate produced by the algorithm and $x$ is the target
data to reconstruct. If $x^{(p)}$ satisfies (71), we say that the algorithm
succeeds in reconstructing $x.$

###  5.1 Effect of the parameter $\gamma$

To illustrate how the value of $\gamma$ affects the reconstruction ability of
the proposed algorithms, we compare the success rates of the proposed
algorithms in $k$-sparse data reconstruction using the following 20 different
values: $\gamma=t/20,$ where $t=1,2,\dots,20.$ The size of matrix is
$500\times 2000,$ and the sparsity levels $k=120,140,150,160,170$ and $180$ of
the sparse vectors $x\in\mathbb{R}^{2000}$ are examined in this experiment.
For every given sparsity level $k,$ the success rates for $k$-sparse data
reconstruction via DOMP and EDOMP with each given $\gamma$ are obtained
respectively by attempting 500 random pairs $(A,x$) with measurements $y:=Ax.$
Each of the algorithms is performed a total of $k$ iterations, where $k$ is
the sparsity level of the vector to reconstruct.

$\begin{array}[]{c}\includegraphics[width=208.13599pt,totalheight=149.6029pt]{DOMPparameter.eps}\\\
\textrm{(a) DOMP: Performance vs the choice of $\gamma$}\end{array}$
$\begin{array}[]{c}\includegraphics[width=208.13599pt,totalheight=149.6029pt]{EDOMPparameter.eps}\\\
\textrm{(b) EDOMP: Performance vs the choice of $\gamma$}\end{array}$

Figure 1: Comparison of performances of DOMP and EDOMP with different choices
of $\gamma.$

The results for DOMP and EDOMP are given in Fig. 1. Intuitively, a small value
of $\gamma$ allows more indices to be added to $\Theta^{(p)}$ at every
iteration, but it may also increase the chance for an incorrect index being
added to $\Theta^{p}$, and thus a small $\gamma$ may lower the success rates
of DOMP for data reconstruction as shown in Fig. 1(a). However, as shown in
Fig. 1 (b), it seems that the performance of EDOMP is less sensitive to the
change of $\gamma$ compared with DOMP. On the other side, the results in Fig.
1 indicate that the success rates of the proposed algorithms with $\gamma=1$
are not the highest ones. This indicates that the algorithm with $\gamma=1$
(including OMP) are not working to their potentials to identify the support of
the target data. One can also see from Fig. 1(a) that the sparser the target
data, the wider range of values for $\gamma$ can be used in DOMP. From Fig.
1(b), a much wider range of values for $\gamma$ can be used in EDOMP than
DOMP. The numerical experiments indicate that the values of $\gamma$ situated
between 0.7 and 1 are generally good for DOMP, and EDOMP has more freedom in
the choice of $\gamma.$ As a result, we may use $\gamma=0.9$ as a default
choice for the two algorithms.

###  5.2 Effect of the number of iterations

The main feature of OMP is that the support of the target data is gradually
identified as the algorithm proceeds. This means that the support of the
target data (which is usually unknown beforehand) cannot be fully obtained if
the number of iterations performed is too low. Similarly, the proposed
algorithms need to perform enough iterations before being terminated. However,
after the necessary iterations have been performed, can any further iterations
continue to remarkably improve the performance of the proposed algorithms for
data reconstruction? To find a possible answer, it is useful to carry out an
experiment to test the performance of algorithms against the number of
iterations excuted.

$\begin{array}[]{c}\includegraphics[width=208.13599pt,totalheight=149.6029pt]{DOMPiter01.eps}\\\
\textrm{(a) DOMP: Performance vs no. of iterations }\end{array}$
$\begin{array}[]{c}\includegraphics[width=208.13599pt,totalheight=149.6029pt]{EDOMPiter01.eps}\\\
\textrm{(b) EDOMP: Performance vs no. of iterations }\end{array}$

Figure 2:  Comparison of performances of DOMP and EDOMP with different no. of
iterations.

According to our theory, under the RIP assumption, the DOMP and EDOMP
algorithms keep finding the correct support of the target data provided that
the performed iterations are lower than $p^{*}$, the largest integer number
$p$ such that $|S^{(p+1)}|\leq(c-2)k$ where $c>2$ is the constant associated
with the RIC. But when iterations go beyond $p^{*},$ there would be no
guarantee for the algorithms to continue to find the correct support of
$x_{S}.$ With the same random matrices and sparse vectors in first experiment,
we compare the performance of DOMP and EDOMP when they are allowed to perform
different numbers of iterations: $p=1+3j$ where $j=0,1,\dots,59.$ For every
given sparsity level $k=120,140,150,160,170,180$ and the prescribed number for
iterations, the success rates for data reconstruction via the two algorithms
with $\gamma=0.9$ are obtained by 500 random tries of $(A,x)$ with accurate
measurements. The results are given in Fig. 2. As expected, the algorithms
require to perform necessary iterations in order to possibly reconstruct the
data. The figure indicates that with the increment of iterations, the success
frequencies of the two algorithms for data reconstruction increase to some
highest point, after that the performance of algorithms would generally not be
improved no matter how many further iterations are performed. From Fig. 2, it
can be easily seen that the highest point of the reconstruction curve appears
after a certain number of iterations that is much lower than the sparsity
level $k$ of the vector. This means that unlike the classic OMP, the DOMP and
EDOMP algorithms do not need to perform at least $k$ iterations in order to
reconstruct a $k$-sparse signal. Thus we carry out further simulations to
examine the average number of iterations as well as runtime needed for the
proposed algorithms to reconstruct the sparse data.

###  5.3 Average number of iterations and average runtime

Experiments were performed to demonstrate the average number of iterations and
runtime needed for the proposed algorithms to achieve the reconstruction
criterion (71).

$\begin{array}[]{c}\includegraphics[width=208.13599pt,totalheight=149.6029pt]{iterComparison5.eps}\\\
\textrm{(a) Average no. of iterations }\end{array}$
$\begin{array}[]{c}\includegraphics[width=208.13599pt,totalheight=149.6029pt]{TimeComparison5.eps}\\\
\textrm{(b) Average runtime}\end{array}$

Figure 3: Comparison of average no. of iterations and runtime required by OMP,
DOMP, EDOMP, CoSaMP and SP

The random matrices in 10 different sizes ranging from $(m,n)=(200,1000)$ to
$(2000,10000)$ are used in this experiments. Specifically, $n=5m$ and
$m=200j,$ where $j=1,\dots,10.$ For every $m\times n$ matrix, the sparsity
level of $x\in\mathbb{R}^{n}$ is set as $k=0.3m.$ The OMP algorithm always
performs at least $k$ iterations in order to possibly reconstruct the
$k$-sparse vector. Thus the total number of iterations required by OMP to
reconstruct the $k$-sparse vectors ($k=0.3m$ in this experiment) is increasing
linearly with respect to the size of the matrices, as shown in Fig. 3(a).
However, Fig. 3(a) indicates that the average numbers of iterations required
by DOMP and EDOMP to meet the reconstruction criterion (71) are increasing
slowly to the size of problems, and they are clearly lower than that of CoSaMP
and OMP, while more than that of SP.

The average runtime for the algorithms to achieve the same criterion (71) is
summarized in Fig. 3(b). It can be seen that the proposed algorithms require
much less computational time than OMP and CoSaMP to achieve the same
reconstruction criterion. The proposed algorithms takes very similar amount of
time as SP. As the problem size goes up, the runtime of the proposed
algorithms increases very slowly in a linear-like manner, while the runtime
for OMP and CoSaMP increases dramatically in an exponential manner. The
simulation does indicate that the total iterations as well as the runtime
required by DOMP and EDOMP to reconstruct the random sparse data can be
remarkably lower than that of OMP. This means the proposed algorithms work
faster than OMP and CoSaMP in general, and they perform quite similarly to SP
in time consumption.

###  5.4 Comparison to some existing algorithms

Finally, we compare the success rates in sparse data reconstruction with DOMP
and EDOMP and a few existing methods including OMP, SP CoSaMP and
$\ell_{1}$-minimization. The parameter $\gamma=0.9$ is set in DOMP and EDOMP
which are performed the same number of iterations as OMP (which is set be the
sparsity level $k$ of the target data). CoSaMP and SP are allowed to perform a
total of 500 iterations for every problem instance in this experiment. For
accurate measurements, all algorithms use the stopping criterion (71). For
noisy measurements, however, we adopt the following criterion:

$\|x^{(p)}-x\|_{2}/\|x\|_{2}\leq 10^{-3}.$

In this comparison, the size of matrices is $500\times 2000,$ and the sparsity
level $k$ of the random data $x\in\mathbb{R}^{2000}$ is ranged from 1 to 300
with stepsize 3, i.e., $k=1,4,7,\dots,299.$ For each given sparsity level, 200
random pairs of $(A,x)$ were realized and used to estimate the success rates
of the algorithms for data reconstruction. The accurate measurements are taken
as $y:=Ax$ and inaccurate measurements are taken as
$\widetilde{y}:=Ax+0.001h,$ where $h$ is a standard Gaussian random vector.
When an algorithm terminates, if $x^{(p)}$ satisfies the reconstruction
criterion, then a ‘success’ is counted for the algorithm.

$\begin{array}[]{c}\includegraphics[width=208.13599pt,totalheight=149.6029pt]{AllcomparisonNoiseless.eps}\\\
\textrm{(a) Accurate measurements }\end{array}$
$\begin{array}[]{c}\includegraphics[width=208.13599pt,totalheight=149.6029pt]{AllcomparisonNoisy.eps}\\\
\textrm{(b) Inaccurate measurements}\end{array}$

Figure 4: Comparison of reconstruction success rates of algorithms in
noiseless and noisy cases

The success rates of the proposed algorithms using accurate measurements are
shown in Fig. 4(a), and the results with inaccurate measurements are given in
Fig. 4(b). One can see that the EDOMP outperforms the traditional OMP, and it
performs quite similarly to SP in both noiseless and noisy cases. In noiseless
setting, DOMP and EDOMP perform similarly and both outperform OMP, CoSaMP and
$\ell_{1}$-minimization. However, the performance of DOMP is subject to the
effect of noises, and it performs comparably to $\ell_{1}$-minimization in
noisy situations. One can also observe that DOMP, in noisy cases, may still
perform better than OMP when the sparsity level is low (e.g., $k/m<1/4$), but
it is less successful than OMP when handling the target data with a relatively
high sparsity level (e.g., $k/m>1/4$ in Fig. 4(b)). Overall, DOMP and EDOMP
proposed in this paper are very competitive to the existing mainstream sparse
data reconstruction methods. In particular, the EDOMP method is fast, stable
and less sensitive to noises, and it is very easy to implement like CoSaMP and
SP.

##  6 Conclusions

The reconstruction error bounds for two new OMP-type algorithms are
established in this paper under the RIP assumption. Finite convergence of the
two algorithms is also shown in the scenario of large-scale compressed
sensing. Simulations indicate that the proposed methods (especially, EDOMP)
are more efficient than OMP in sense that they may take much less average
computational times and iterations to reconstruct the sparse data, and they
can compete against several state-of-art methods in this field. Distinguished
from the existing OMP-type methods, the main feature of the proposed
algorithms lies in their dynamic and efficient exploiting the gradient
information of the error metric at every iteration to recognize the support of
the target data. This development maintains the good attribute of OMP such as
low computational cost and in the meantime speeds up the support
identification for the target data.

## References

  * [1] A. Beck and Y.C. Eldar, Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, _SIAM J. Optim._ , 23 (2013), no. 3, pp. 1480–1509.
  * [2] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, _SIAM J. Imaging Sci._ , 2 (2009), no. 1, pp. 183–202.
  * [3] H. Boche, R. Calderbank, G. Kutyniok, J. Vybiral, Compressed Sensing and Its Applications, Springer, New York, 2019.
  * [4] T. Cai and L. Wang, Orthogonal matching pursuit for sparse signal recovery with noise, _IEEE Trans. Inf. Theory_ , 57 (2011), no. 7, pp. 4680–4688.
  * [5] E.J. Candès and T. Tao, Decoding by linear programming. _IEEE Trans. Inf. Theory_ , 51 (2005), no. 12, pp. 4203–4215.
  * [6] E.J. Candès, M. Wakin and S. Boyd, Enhancing sparsity by reweighted $\ell_{1}$ minimization, _J. Fourier Anal. Appl._ , 14 (2008), pp. 877–905.
  * [7] E.J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, _IEEE Trans. Inform. Theory_ , 52 (2006), no. 2, pp. 489–509.
  * [8] L.-H. Chang and J.-Y. Wu. An improved RIP-based performance guarantee for sparse signal recovery via orthogonal matching pursuit, _IEEE Trans. Inf. Theory_ , 60 (2014), no. 9, pp. 5702–5715.
  * [9] L.-H. Chang and J.-Y. Wu, An improved RIP-based performance guarantee for sparse signal reconstruction via subspace pursuit, IEEE 8th Sensor Array and Multichannel Signal Processing Workshop (SAM), pp. 405–408, 2014.
  * [10] S.S. Chen, D.L. Donoho and M.A. Saunders, Atomic decomposition by basis pursuit, _SIAM J. Sci. Comput._ , 20 (1998), no. 1, pp. 33–61.
  * [11] W. Dai and O. Milenkovic, Subspace pursuit for compressive sensing signal reconstruction, _IEEE Trans. Inf. Theory_ , 55 (2009), no. 5, pp. 2230-2249.
  * [12] M.A. Davenport and M.B. Wakin, Analysis of orthogonal matching pursuit using the restricted isometry property, _IEEE Trans. Inf. Theory_ , 56 (2010), no. 9, pp. 4395–4401.
  * [13] G. Davis, S. Mallat and Z. Zhang, Adaptive time-frequency decompositions, _Optical Eng._ , 33 (1994), no. 7, pp. 2183–2191.
  * [14] G. Davis, S. Mallat, and M. Avellaneda, Greedy adaptive approximation, _J. Constr. Approx._ , 13 (1997), no.1, pp. 57–98.
  * [15] R.A. DeVore, Nonlinear approximation, _Acta Num._ , 7 (1998), pp. 51–150.
  * [16] D.L. Donoho, Compressed sensing, _IEEE Trans. Inf. Theory_ , 52 (2006), no. 4, pp. 1289–1306.
  * [17] D. L. Donoho, Y. Tsaig, I. Drori, and J.-L. Starck, Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit, _IEEE Trans. Inf. Theory_ , 58 (2012), no. 2, pp. 1094–1121.
  * [18] M. Elad, Sparse and Redundant Representation: From Theory to Applications in Signal and Image Processing, Springer, New York, 2010.
  * [19] Y. Eldar and G. Kutyniok, Compressed Sensing: Theory and Applications, Cambridge University Press, Cambridge, UK, 2012.
  * [20] S. Foucart and H. Rauhut, _A Mathematical Introduction to Compressive Sensing_ , Basel: Birkhäuser, Springer, 2013.
  * [21] Z. Gao, L. Dai, S. Han, C.-L. I, Z. Wang and L. Hanzo, Compressive sensing techniques for next-generation wireless communications, _IEEE Wireless Commun._ , 25 (2018), no. 3, pp. 144–153.
  * [22] A.C. Gilbert, M. Muthukrishnan, and M.J. Strauss, _Approximation of functions over redundant dictionaries using coherence_ , in Proc. 14th Annu. ACM-SIAM Symp. Discrete Algorithms, Baltimore, MD, pp. 243–252, 2003\.
  * [23] S. Huang and J. Zhu, Recovery of sparse signals using OMP and its variants: Convergence analysis based on RIP, _Inverse Prob._ , 27 (2011), no. 3, p. 035003.
  * [24] R. Khanna, A. Kyrillidis, IHT dies hard: Provable accelerated iterative hard thresholding. International Conference on Artificial Intelligence and Statistics. pp.188-198, 2018.
  * [25] S. Kwon, J. Wang and B. Shim. Multipath matching pursuit. _IEEE Trans. Inf. Theory_ , 60 (2014), no. 5, pp. 2986–3001.
  * [26] M. Leinomen, M. Codreanu and G. Giannakis, Compressed sensing with applications in wireless networks, _Found. Trends Signal Process._ , 13 (2019), no. 1-2, pp. 1–282.
  * [27] B. Li, Y. Shen, Z. Wu and J. Li, Sufficient conditions for pursuit in noisy case, _Signal Process._ , 108 (2015), pp. 111-123.
  * [28] E. Liu and V.N. Temlyakov, The orthogonal super greedy algorithm and applications in compressed sensing, _IEEE Trans. Inf. Theory_ , 58 (2012), no. 4, pp. 2040–2047.
  * [29] A. De Maio, Y. Eldar and A. Haimovich, Compressed Sensing in Radar Signal Processing, Cambridge University Press, Cambridge, 2019.
  * [30] R. Maleh, _Improved rip analyis of orthogonal matching pursuit_ , arXiv:1102.4311v1, Feb. 2011.
  * [31] S. Mallat and Z. Zhang, Matching pursuits with time-frequency dictionaries, _IEEE Trans. Signal Process._ , 41 (1993), no. 12, pp. 3397–3415.
  * [32] N. Meng and Y.B. Zhao, Newton-step-based hard thresholding algorithms for sparse signal recovery, _IEEE Trans. Signal Process._ , 68 (2020), pp. 6594–6606.
  * [33] Q. Mo, A sharp restricted isometry constant bound of orthogonal matching pursuit, arXiv:1501.01708, Jan. 2015.
  * [34] Q. Mo and Y. Shen, A remark on the restricted isometry property in orthogonal matching pursuit, _IEEE Trans. Inf. Theory_ , 58 (2012), no. 6, pp. 3654–3656.
  * [35] D. Needell and R. Vershynin, Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit, _Found. Comput. Math._ , 9 (2009), no. 3, pp. 317–334.
  * [36] D. Needell and R. Vershynin, Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit, _IEEE J. Sel. Top. Signal Process._ , 4 (2010), no. 2, pp. 310–316.
  * [37] D. Needell and J. Tropp, CoSaMP: Iterative signal recovery from incomplete and inaccurate samples, _Appl. Comput. Harmon. Anal._ , 26 (2009), no. 3, pp. 301-321.
  * [38] Y.C. Pati, R. Rezaiifar and P.S. Krishnaprasad, Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition, in Proc. 27th Annu. Asilomar Conf. Signals, Systems and Computers, Nov. 1993.
  * [39] S. Satpathi, R. L. Das and M. Chakraborty, Improving the bound on the RIP constant in generalized orthogonal matching pursuit, _IEEE Signal Process. Lett._ , 20 (2013), no. 11, pp. 1074-1077.
  * [40] Y. Shen, B. Li, W. Pan and J. Li, Analysis of orthogonal matching pursuit using restricted isometry constant, _Electron. Lett._ , 50 (2014), no. 14, pp. 1020-1022.
  * [41] J. Shen and P. Li, A tight bound of hard thresholding, _J. Machine Learning Res._ , 18 (2018), pp. 1-42.
  * [42] J. Shen and S. Mousavi, Exact support and vector recovery of constrained sparse vectors via constrained matching pursuit, arXiv:1903.07236v3, Mar. 2020.
  * [43] C.-B. Song, S.-T. Xia and X.-J. Liu, Improved analysis for subspace pursuit algorithm in terms of restricted isometry constant, _IEEE Signal Process. Lett._ , 21 (2014), no. 11, pp. 1365-1369.
  * [44] V. Temlyakov, Nonlinear methods of approximation, _Found. Comp. Math._ , 3 (2003), no. 1, pp. 33–107.
  * [45] V. Temlyakov, Weak greedy algorithms, _Adv. Comput. Math._ , 12 (2000), no. 2-3, pp. 213-227.
  * [46] J. A. Tropp, Greed is good: Algorithmic results for sparse approximation, _IEEE Trans. Inf. Theory_ , 50 (2004), no. 10, pp. 2231–2242.
  * [47] J.A. Tropp, Just relax: Convex programming methods for subset selection and sparse approximation, _IEEE Trans. Inf. Theory_ , 52 (2006), no. 3, pp. 1030–1051.
  * [48] J.A. Tropp and A.C. Gilbert, Signal recovery from random measurements via orthogonal matching pursuit, _IEEE Trans. Inf. Theory_ , 53 (2007), no. 12, pp. 4655–4666.
  * [49] J. Wang, Support recover with orthogonal matching pursuit in the presence of noise, _IEEE Trans. Signal Process._ , 63 (2015), no. 21, pp. 5868–5877.
  * [50] J. Wang, S. Kwon and B. Shim, Generalized orthogonal matching pursuit, _IEEE Trans. Signal Process._ , 60 (2012), no. 12, pp. 6202–6216.
  * [51] J. Wang and B. Shim, On the recovery limit of sparse signals using orthogonal matching pursuit, _IEEE Trans. Signal Process._ , 60 (2012), no. 9, pp. 4973–4976.
  * [52] J. Wen, Z. Zhou, D. Li and X. Tang, A novel sufficient condition for generalized orthogonal matching pursuit, _IEEE Commun. Lett._ , 21 (2017), no. 4, pp. 805–808.
  * [53] R. Wu, W. Huang, and D.-R. Chen, The exact support recovery of sparse signals with noise via orthogonal matching pursuit, _IEEE Signal Process. Lett._ , 20 (2013), no. 4, pp. 403–406.
  * [54] T. Zhang, Sparse recovery with orthogonal matching pursuit under RIP, _IEEE Trans. Inf. Theory_ , 57 (2011), no. 9, pp. 6215–6221.
  * [55] Y.-B. Zhao, _Sparse Optimization Theory and Methods_ , CRC Press, Boca Raton, FL, 2018.
  * [56] Y.-B. Zhao, RSP-based analysis for sparsest and least $\ell_{1}$-norm solutions to underdetermined linear systems, _IEEE Trans. Signal Process._ , 61 (2013), no. 22, pp. 5777–5788.
  * [57] Y.-B. Zhao, Optimal $k$-thresholding algirithms for sparse optimization problems, _SIAM J. Optim._ , 30 (2020), no. 1, pp. 31-55.
  * [58] Y.-B. Zhao and Z.-Q. Luo, Improved RIP-based bounds for guaranteed performance of two compressed sensing algorithms, arXiv:2007.01451, Jul. 2020, to appear in _Sci. China Math._
  * [59] Y.-B. Zhao and Z.-Q. Luo, Analysis of optimal thresholding algorithms for compressed sensing, _Signal Process._ 187 (2021), p. 108148.