# Relaxed recovery conditions for OMP/OLS by exploiting both coherence and decay

Cédric Herzet, Angélique Drémeau, Charles Soussen

► To cite this version:

Cédric Herzet, Angélique Drémeau, Charles Soussen. Relaxed recovery conditions for OMP/OLS by exploiting both coherence and decay. IEEE Transactions on Information Theory, 2016, 62 (1), pp.459-470. 10.1109/TIT.2015.2490660. hal-01058077

HAL Id: hal-01058077

https://inria.hal.science/hal-01058077

Submitted on 25 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Relaxed Recovery Conditions for OMP/OLS
by Exploiting both Coherence and Decay

C. Herzet, A. Drémeau, C. Soussen, *Member, IEEE*

***Abstract***—We propose extended coherence-based conditions for exact sparse support recovery using orthogonal matching pursuit (OMP) and orthogonal least squares (OLS). Unlike standard uniform guarantees, we embed some information about the decay of the sparse vector coefficients in our conditions. As a result, the standard condition $\mu < 1/(2k-1)$ (where $\mu$ denotes the mutual coherence and $k$ the sparsity level) can be weakened as soon as the nonzero coefficients obey some decay, both in the noiseless and the bounded-noise scenarios. Furthermore, the resulting condition is approaching $\mu < 1/k$ for strongly decaying sparse signals. Finally, in the noiseless setting, we prove that the proposed conditions, in particular the bound $\mu < 1/k$, are the tightest achievable guarantees based on mutual coherence.

***Index Terms***—Orthogonal matching pursuit; orthogonal least-squares; mutual coherence; exact recovery; sparse decaying representations.

## I. INTRODUCTION

In this paper, we focus on two popular instances of greedy algorithms for sparse signal approximation from linear measurements, namely orthogonal matching pursuit (OMP) [1] and orthogonal least squares¹ (OLS) [6], [7]. These two iterative procedures gradually build an estimate of the support of a sparse representation by adding one new element to it at each iteration, and update the sparse approximation by computing the orthogonal projection of the data vector onto the subspace yielded by the selected support. OMP and OLS exclusively differ in the way the new support element is selected: OMP picks the atom leading to the maximum (absolute) correlation with the current residual while OLS selects the atom minimizing the $l_2$-norm of the new residual. In the rest of the paper, we will use the generic acronym Oxx to refer to both OMP and OLS in all the statements that are valid for the two procedures.

In the recent years, many researchers have studied conditions under which Oxx succeeds in recovering the true sparse vector. A popular approach to address this question relies on the derivation of *uniform* guarantees; the latter ensure the success of Oxx for a given sparsity level (or a given support).

C. Herzet is with INRIA Centre Rennes - Bretagne Atlantique, Campus de Beaulieu, F-35042 Rennes Cedex, France (e-mail: Cedric.Herzet@inria.fr).

A. Drémeau is with ENSTA Bretagne and Lab-STICC (UMR 6285), 42 rue François Verny, 29200 Brest, France (e-mail: angelique.dremeau@enstabretagne.fr).

C. Soussen is with the University of Lorraine and CNRS at the Centre de Recherche en Automatique de Nancy (CRAN, UMR 7039), 2 avenue de la forêt de Haye - TSA 60604 - F-54518 Vandoeuvre-lès-Nancy Cedex, France (e-mail: charles.soussen@univ-lorraine.fr).

C. Herzet and C. Soussen are sponsored by the French Agence Nationale de la Recherche (ANR), BECOSE project.

¹The OLS algorithm is also known as forward selection [2], Order Recursive Matching Pursuit (ORMP) [3], pure Orthogonal Matching Pursuit (OMP) [4] and Optimized Orthogonal Matching Pursuit (OOMP) [5] in the literature.

irrespective of the magnitude of the nonzero coefficients. This type of analyses was carried out for OMP in [8], [9] and also adapted to several extensions of OMP in [4], [10], [11]. Although OLS has been known in the literature for a few decades (under different names [12]), uniform exact recovery analyses of OLS have only appeared very recently, see [4], [13], [14].

On the one hand, uniform conditions are usually quite pessimistic since they cannot be satisfied as soon as Oxx fails for *one* particular sparse vector. As a matter of fact, it is now acknowledged that uniform conditions typically fail in properly characterizing the *average* behavior of the considered algorithm [15], [16]. In particular, in [17] the author emphasized that the empirical behavior of OMP is much dependent on the distribution defining the amplitudes of the nonzero coefficients. On the other hand, probabilistic analyses<fnref n="2" /> are usually quite involved to carry out for deterministic dictionaries because of the intricate nature of the recursions defining Oxx. It is noticeable that a probabilistic analysis of OMP has been proposed within the multiple measurement setup (i.e., when several data vectors having a common sparsity profile are to be simultaneously decomposed in the same dictionary) [20]. In this context, the uniform recovery guarantees can be significantly weakened within a probabilistic framework. Nevertheless, this result was shown to be only relevant when the number of measurement vectors is of the same order as the sparsity level and does therefore not apply to the single measurement case.

In this paper, we adopt a deterministic analysis technique for sparse vectors whose nonzero coefficients obey some decay. Our analysis is therefore no longer uniform since it restricts the success of Oxx to a certain class of sparse signals. To some extent, it may also provide insights into the success of Oxx for random input vectors as long as one can characterize the decay of “typical” realizations of the latter. From another point of view, let us mention that a number of authors empirically observed (and then conjectured) that the worst-case scenario for Oxx corresponds to the situation where all the nonzero coefficients have the same amplitude, see e.g., [17], [21]–[23]. The analysis of Oxx with decaying vectors is thus also expected to bring some answer to this question since vectors with equal nonzero coefficients correspond to the particular case of “no decay”.

Although sparse vectors with decaying nonzero coefficients

<footnote n="2">²We are referring here to analyses characterizing the success of Oxx with “high probability”, for a deterministic dictionary and a random sparse vector. This is in contrast with the probabilistic analyses performed in [18], [19], which focus on the *uniform* success of OMP for random dictionaries (and a given support).</footnote>
can be observed in many applications (see [24] and [25] for examples in the field of image and audio processing, respectively), we are only aware of a few works analyzing the success of Oxx in such a setup [9], [26]–[28]. In [26] the authors adopted an information-theoretical point of view: they derived “rates” (i.e., dictionary dimensions and sparsity levels) under which a “successive interference canceller” (which can be understood as an idealized version of Oxx) can asymptotically succeed. In particular, they showed that the achievable rates depend on the amplitudes of the nonzero coefficients (which, in their theoretical framework, must be known to the receiver), and thus on the decay. However, their results only apply to randomly-generated dictionaries. In [9], the authors provided an analysis of OMP in terms of restricted isometry constants (RIC) and showed that the success of OMP can be ensured by considering sufficiently decaying vectors. In [27], Ding et al. extended this type of result to the case of observation models corrupted by noise. Finally, Ehler et al. carried out the same kind of RIC-based analysis for some non-linear generalization of OLS in [28].

In the sequel, we propose novel conditions of success in $k$ steps for both OMP and OLS in terms of mutual coherence of the dictionary ($k$ denotes the number of nonzero coefficients in the sparse vector). We note that, as long as the success of OMP and OLS in $k$ steps is concerned$^3$, mutual coherence and RICs are dictionary features which offer different perspectives on the success of Oxx: as shown in [14, Examples 2 and 3], there are instances of dictionaries for which the uniform mutual coherence condition $\mu < 1/(2k - 1)$ is satisfied but the best-known uniform RIC conditions [29], [30] are not, and vice versa. The conditions derived in this paper relax several conditions previously proposed in the literature, and encompass them as particular cases.

We will consider a unified definition of Oxx based on the orthogonal projection of the dictionary atoms onto the orthogonal complement of the subspace spanned by the selected atoms, see e.g., [13]. This definition allows us to define both algorithms in a unifying framework and to carry out a parallel analysis of both OMP and OLS. Our derivations are then based on a fine analysis of the correlation between the projected atoms involved in the iterations of Oxx. Unlike previous works, we highlight that the decay conditions can be relaxed as the iterations of Oxx progress. Moreover, our guarantees are tight: these are the best achievable coherence-based guarantees exploiting the decay between successive ordered coefficients in the noiseless setup.

The rest of the paper is organized as follows. Our main results are stated in section II together with some relevant connections with the state of the art. The technical proofs of the results are reported in section III.

## II. CONTEXT AND MAIN RESULTS

Let $y \in \mathbb{R}^m$ obey the following model:

$$y = Ax + w, \quad (1)$$

**Algorithm 1** Oxx in $k$ steps

inputs: $y, A$

init: $Q = \emptyset$

while $\text{Card}(Q) < k$ do

$$Q = Q \cup \{j\}$$

where

$$j \in \begin{cases} \arg \max_{i \notin Q} |\langle a_i, r^Q \rangle| & (\text{OMP}) \\ \arg \min_{i \notin Q} \|r^Q \cup \{i\}\|_2 & (\text{OLS}) \end{cases}$$

and $r^Q$ is the data residual associated to active set $Q$

end while

output: $Q$ with $\text{Card}(Q) = k$

where $A \in \mathbb{R}^{m \times n}$ is a known dictionary, $x \in \mathbb{R}^n$ is an unknown vector and $w \in \mathbb{R}^m$ is some additive noise with $\|w\|_2 \le \epsilon$. The columns $a_i$ of the dictionary are supposed to be normalized: $\|a_i\|_2 = 1$. We investigate conditions ensuring that Oxx selects a subset $Q^*$ of $k$ dictionary atoms, where $Q^* \subseteq \{1, \dots, n\}$ matches the support of the $k$ largest elements of $x$. We have summarized the main recursions of Oxx in Algorithm 1. $\langle \cdot, \cdot \rangle$ denotes the vector inner product and $r^Q$ is the projection of $y$ onto the space orthogonal to the columns of $A$ indexed by $Q$. We refer the reader to section III-A for a more detailed description of Oxx.

Our derivations are based on the so-called “$k$-step” analysis of Oxx: Oxx will be assumed to fail as soon as one wrong atom $i \notin Q^*$ is included to the estimated support [8], [9], [13]. On the contrary, Oxx succeeds if and only if the atoms in $Q^*$ are selected during the first $k$ iterations. Alternative definitions of exact sparse recovery may be considered. In [4], [31], the authors focused on “delayed recovery”, where Oxx is assumed to succeed if the selected atoms contain the correct support, with possible false atom selections. This approach will not be pursued hereafter.

Several scenarios are considered. In sections II-A and II-B, we address the case where the observation model is noiseless ($\epsilon = 0$) and $x$ is $k$-sparse with support $Q^*(x_i \neq 0 \Leftrightarrow i \in Q^*)$. In section II-A, we focus on conditions ensuring the recovery of $Q^*$ from the first iteration, i.e., with the initial empty support, whereas a finer analysis at intermediate iterations is carried out in section II-B. This analysis allows us to provide weaker guarantees of good atom selection when (i) less than $k$ iterations are being performed, and when (ii) Oxx is known to have selected good atoms in the early iterations. In section II-C, we address the noisy scenario ($\epsilon > 0$), and the case where $x$ is compressible but possibly non-sparse. In this case, $Q^*$ can be thought of as the “head” of the signal $x$, obtained by gathering the indices of the largest amplitudes in $x$.

Some of the results presented below share connections. For example, the direct part of Theorem 2 (section II-A), dealing with $k$-step recovery and noiseless observations, can be seen as a particular case of the results presented in Theorems 3 and 5 (sections II-B and II-C). However, we chose to follow this editorial line to keep the discussion of the results and the relation to the current state of the art as simple as possible.

<footnote>$^3$This is in contrast with Basis Pursuit for which RICs usually lead to more favorable conditions.</footnote>
A. k-step Analysis in the Noiseless Setup

The first thoughtful “k-step” analysis of OMP is due to
Tropp in [8, Th. 3.1 and Th. 3.10]. He provided a sufficient and
worst-case necessary condition for the exact recovery of any
sparse vector with a given support $Q^*$. Moreover, he showed
that the condition

$$
\mu < \frac{1}{2k-1}, \tag{2}
$$

where $\mu \triangleq \max_{i \neq j} |\mathbf{a}_i^T \mathbf{a}_j|$ is the mutual coherence of $\mathbf{A}$, ensures the success of OMP. The derivation of similar conditions for OLS is more recent and is due to Soussen et al. in [13], [14].

Condition (2) is uniform, that is Oxx can recover any k-
sparse vector irrespective of the amplitude of the nonzero
coefficients when (2) is satisfied. On the other hand, it was
shown in [32, Th. 3.1] that (2) is tight: there exist a k-sparse
vector x and a dictionary A with μ = 1/2k-1 such that Oxx
selects a wrong atom at the first iteration<fnref n="4" />. This shows that
one cannot expect to weaken (2) for the recovery of arbitrary
k-sparse vectors. Nevertheless, it is noticeable that the specific
sparse vector involved in the example of [32] is “flat”, that is
such that

$$
x_i = \text{constant} \quad \forall i \in \mathcal{Q}^*. \quad (3)
$$

This is not a coincidence. In Theorem 1 below, we show
that weaker sufficient conditions than (2) can be obtained as
soon as the nonzero coefficients of x obey some decay.

**Theorem 1** If $\mathbf{x}$ is a $k$-sparse vector whose nonzero amplitudes are not all equal, there exists some $\mu^* > \frac{1}{2k-1}$ such that Oxx recovers $Q^*$ in $k$ steps for any dictionary with $\mu < \mu^*$.

Interestingly, as mentioned in the introduction, it has been
stated in many pieces of research (and accepted as a “folk
knowledge” [17]) that sparse vectors with nonzero coefficients
of equal magnitude correspond to the most difficult case for
many reconstruction algorithms, see e.g., [21]–[23]. The result
in Theorem 1 supports this observation by stating that, as long
as the satisfaction of mutual coherence conditions for exact
recovery is concerned, “flat” vectors correspond to the worst
possible case for Oxx. In particular, a condition of success
more favorable than $\mu < \frac{1}{2k-1}$ always exists as soon as the
coefficients of $\mathbf{x}$ exhibit some decay.

Unfortunately, the proof of Theorem 1 does not provide
an optimal value for $\mu^*$ (as a function of the rate of decay).
In fact, a precise characterization of $\mu^*$ for general decay
patterns may be a quite difficult task. In the next theorem, we
provide “horizon-1” decay conditions (i.e., conditions between
consecutive elements of the ordered nonzero coefficients)
ensuring that Oxx succeeds in $k$ steps. In our statement, we
assume without loss of generality that

$$
Q^* = \{1, 2, \dots, k\}, \quad (4)
$$

and

$$
|x_1| \ge |x_2| \ge \dots \ge |x_k| > 0. \tag{5}
$$

**Theorem 2 If**

$$
\mu < \frac{1}{k},
\quad (6)
$$

and

$$
|x_i| > \frac{2\mu(k-i)}{1-i\mu} |x_{i+1}| \quad \forall i \in \{1, \dots, k-1\}, \quad (7)
$$

then Oxx recovers $Q^*$ in $k$ steps.

Conversely, both conditions (6) and (7) are tight in the
following sense:

* There exists an instance of dictionary $\mathbf{A}$ with $\mu = \frac{1}{k}$ such that for all $k$-sparse vectors $\mathbf{x}$ supported by $Q^*$, Oxx selects a wrong atom during the first $k$ iterations.

* For all $j \in \{1, \dots, k-1\}$, there exists a vector $\mathbf{x}^{(j)}$ and a dictionary $\mathbf{A}$ of mutual coherence $\mu < \frac{1}{k}$, for which the inequalities (7) hold for $i \neq j$, and become an equality for $i = j$, and such that Oxx with $\mathbf{x}^{(j)}$ as input selects a wrong atom at the $j$-th iteration.

Theorem 2 encompasses the standard condition (2) as a
particular case. Indeed, the decay factor appearing in the right-
hand side of condition (7) is such that

$$
\frac{2\mu(k-i)}{1-i\mu} < 1, \quad (8)
$$

as soon as

$$
\mu < \frac{1}{2k - i}.
$$

Thus, by virtue of our convention (5), (8) implies that con-
dition (7) trivially holds for any *i* as soon as (2) is satisfied.
We also note that $\frac{2\mu(k-i)}{1-i\mu}$ is a decreasing function of *i* for
$\mu < 1/k$. Hence, the rate of decay in (7) becomes lower as *i* increases.

Condition (7) can be equivalently expressed as

$$
\mu < \mu_i^* \quad \text{with} \quad \mu_i^* = \frac{\frac{|x_i|}{|x_{i+1}|}}{2(k-i)+i \frac{|x_i|}{|x_{i+1}|}},
$$

$\forall i \in \{1, \dots, k-1\}$. The conditions of success stated in
Theorem 2 can thus also be rephrased as:

$$
\mu < \mu^* = \min \left( \frac{1}{k}, \mu_1^*, \dots, \mu_{k-1}^* \right).
$$

It can be seen that possible values for $\mu^*$ range in the interval
$[\frac{1}{2k-1}, \frac{1}{k}]$ and depend on the decay of the nonzero coefficients
of $\mathbf{x}$. On the one hand, the smallest value for $\mu_i^*$ occurs when
$|x_i| = |x_{i+1}|$, in which case $\mu_i^* = \frac{1}{2k-i}$. Hence, we recover the
standard condition (2) when $|x_1| = |x_2|$. On the other hand,
$\mu_i^* > \frac{1}{k}$ (and therefore $\mu^* = \frac{1}{k}$) as soon as $|x_i| > 2|x_{i+1}|$.
This leads to the following corollary:

**Corollary 1** If $\mu < 1/k$ and $|x_i| > 2|x_{i+1}| \quad \forall i \in \{1, \dots, k-1\}$, then Oxx recovers $Q^*$ in $k$ steps.

A graphical representation of these considerations is pro-
vided in Fig. 1 for $k = 5$: the decay factor $\frac{2\mu(k-i)}{1-i\mu}$ appearing

<footnote n="4">⁴Specifically, Cai et al. point out that there is an identifiability issue since some data vector can be decomposed using two *k*-sparse representations with distinct supports.</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1: Graphical representation of the decay constraints of Theorem 2 for different values of $\mu \in [\frac{1}{2k}, \frac{1}{k}]$, $k = 5$. Plain curves: plot of the decay constraint $2\mu(k-i)/(1-i\mu)$ with respect to $i$. We note that because of our convention (5), we must have $|x_i|/|x_{i+1}| \ge 1 \forall i$: this region corresponds to the shaded gray area.</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>Fig. 2: Probability of satisfying condition (7) for random realizations drawn from different distributions versus $k\mu$.</figcaption></figure>

in (7) is plotted as a function of $i$ for different values of $\mu \in [\frac{1}{2k}, \frac{1}{k}]$. For a given $\mu$, the region above the related curve characterizes the set of vectors $x$ satisfying the recovery conditions of Theorem 2. We notice that the size of the region of success increases as the mutual coherence decreases. In particular, when $\mu = \frac{1}{2k} < \frac{1}{2k-1}$, the curve is laying below the dashed line $|x_i|/|x_{i+1}| = 1$ and (7) is satisfied for any $k$-sparse representation since, by convention, the nonzero entries have been sorted according to (5). On the other side, the region of success is restricted to vectors satisfying $|x_i|/|x_{i+1}| \ge 2$ when $\mu$ is close to $\frac{1}{k}$. We note moreover that the decay constraints become less stringent as $i$ increases.

It is also insightful to see how often nonzero coefficients drawn from different distributions can satisfy (7). In Fig. 2, we have represented the empirical probability that coefficients drawn from Bernoulli, Uniform, Normal, Laplacian and LogLogistic distributions verify the decay conditions of Theorem 2. We consider again the case where $k = 5$ and the results are averaged over 2000 realizations. In accordance with Theorems 1 and 2, the Bernoulli distribution (which always generates “flat” vectors) leads to the worst results. In particular, conditions (7) cannot be verified as soon as $k\mu \ge \frac{k}{2k-1} \approx 0.55$. In contrast, the vectors drawn from the other distributions satisfy (7) with some nonzero probability for any $\mu < \frac{1}{k}$ (and are therefore ensured to yield a success of Oxx). Interestingly, our conclusions regarding the comparison of distributions is the same as the one observed in the empirical study of the average performance of OMP in [17].

It is worth noting that not all standard sparse-representation algorithms enjoy a relaxation of their recovery conditions when dealing with decaying vectors. For example, the standard condition $\mu < \frac{1}{2k-1}$ cannot be improved for Basis Pursuit [33]. Indeed, it has been shown in [32, Th. 3.1] that there exists a dictionary $\mathbf{A}$ with $\mu = \frac{1}{2k-1}$ and a flat $k$-sparse vector $\mathbf{x}$

such that Basis Pursuit leads to a wrong support detection.<fnref n="5" /> Now, it is well-known that tight conditions of success for Basis Pursuit only depend on the signed support of the sought sparse vector, see [34], [35]. The existence of a vector $\mathbf{x}$ for which BP fails thus shows that BP will fail for all other sparse vectors with the same signed support, irrespective of the decay of the coefficients.

The converse part of Theorem 2 emphasizes that the proposed recovery conditions (6)-(7) are worst-case necessary in some sense. The nature of the sharpness of (6) and (7) is however slightly different. The tightness of (7) is restricted to the set of “horizon-1” conditions, that is conditions exploiting the decay between pairs of consecutive elements in the ordered sparse vector. The tightness of (6) is of more fundamental nature since Theorem 2 states that there exists a dictionary such that Oxx will fail during the first $k$ iterations irrespective of the values of the nonzero coefficients in $\mathbf{x}$. Hence, any mutual coherence condition ensuring $k$-step recovery and valid for general deterministic dictionaries (and in particular for the specific dictionary considered in the proof of Theorem 2, see section III-C) must be of the form $\mu < \mu^*$ with $\mu^* \le \frac{1}{k}$. Said otherwise, the bound $\frac{1}{k}$ cannot be improved whatever the hypotheses made on the sparse vector.

## B. Partial Recovery and Successful Termination

In many applications, it is desirable to have some guarantees on the partial success of Oxx. Two main situations may be of interest:

1) **Successful Termination:** Oxx is assumed to have selected atoms in $Q \subset Q^*$, with cardinality $\text{Card}(Q) = g \ge 0$, during the first $g$ iterations, and one is interested in conditions guaranteeing the selection of atoms in $Q^* \setminus Q$ during the next $k-g$ iterations.

2) **Partial Support Recovery:** the focus is on conditions ensuring the selection of $p \le k$ elements of $Q^*$ during

<footnote n="5">⁵More precisely, there exists another $k$-sparse vector $\tilde{\mathbf{x}}$ such that $\|\mathbf{x}\|_1 = \|\tilde{\mathbf{x}}\|_1$ and $\mathbf{y} = \mathbf{A}\mathbf{x} = \mathbf{A}\tilde{\mathbf{x}}$.</footnote>
the first $p$ iterations.

Before we state our results, let us make a few remarks. First, the question of partial support recovery has a trivial answer in the standard “uniform” setup. Indeed, as mentioned previously, the authors of [32] provided an instance of problem in which $\mu = \frac{1}{2k-1}$ and Oxx selects a wrong atom at the first iteration. This shows that weaker coherence guarantees cannot be obtained for non-decaying vectors, even by restricting the success of Oxx to partial support recovery. On the contrary, we will emphasize that the paradigm of partial support recovery can be nicely addressed when accounting for the decay of the sparse vector.

Secondly, the question of the successful termination of Oxx has already been addressed in the uniform setting. In [13], the authors extended Tropp’s exact recovery condition (ERC) to this particular setup, both for OMP and OLS. The same type of conditions were expressed in terms of mutual coherence in [14, Th. 3]: if $Q \subsetneq Q^*$ is reached during the first $\text{Card}(Q) = g$ iterations, then Oxx selects atoms in $Q^* \setminus Q$ during the next $k-g$ iterations provided that

$$ \mu < \frac{1}{2k - g - 1}. \quad (9) $$

Similar to the standard $k$-step analysis [32], (9) was shown to be tight: there exist a $k$-sparse vector $\mathbf{x}$ with support $Q^*$, a subset $Q \subsetneq Q^*$ with $\text{Card}(Q) = g$ and a dictionary $\mathbf{A}$ with $\mu = \frac{1}{2k-g-1}$ such that Oxx selects atoms in $Q$ during the first $g$ steps and then makes a wrong decision. We show hereafter that this coherence bound can be relaxed when dealing with decaying sparse vectors.

In the statement of Theorem 3, following convention (5), we proceed to a re-ordering of the atoms $\mathbf{a}_i$ by decreasing values of their magnitudes $|x_i|$. Here, this convention is applied to the unselected atoms, which are therefore indexed by:

$$ Q^* \setminus Q = \{1, 2, \dots, k - g\}, \quad (10) $$

with

$$ |x_1| \ge |x_2| \ge \dots \ge |x_{k-g}| > 0. \quad (11) $$

Theorem 3 jointly addresses both questions of successful termination and partial support recovery.

**Theorem 3** Assume that Oxx has selected $Q \subsetneq Q^*$ with $\text{Card}(Q) = g$ during the first $g$ iterations and let $1 \le p \le r \le k-g$.

* If

$$ \mu < \frac{1}{k}, \quad (12) $$

and the largest magnitudes of the unselected atoms after iteration $g$ satisfy

$$ |x_i| > \frac{2\mu(k-g-i)}{1-(g+i)\mu} |x_{i+1}| \quad \forall i \in \{1, \dots, p\}, \quad (13) $$

then Oxx is guaranteed to select atoms in $Q^* \setminus Q$ until all the elements in $\{1, \dots, p\}$ have been selected.

* If

$$ \frac{1}{k} \le \mu < \frac{1}{g+r}, \quad (14) $$

and the largest magnitudes of the unselected atoms after iteration $g$ satisfy

$$ |x_i| > \frac{2\mu(k-g-r)}{1-(g+r)\mu} |x_{i+1}| \quad \forall i \in \{1, \dots, p\}, \quad (15) $$

then Oxx is ensured to select atoms in $Q^* \setminus Q$ until all the elements in $\{1, \dots, p\}$ have been selected or $g+r$ iterations have been carried out.

Let us discuss the implications of Theorem 3 on both problems of “successful termination” and “partial support recovery”. We specifically elaborate on the corresponding choices of $g, p$ and $r$.

The paradigm of successful termination corresponds to the case $p=r=k-g$. In this setup, we note that conditions (14)-(15) are irrelevant since $\frac{1}{g+r} = \frac{1}{k}$, thus (14) cannot be satisfied. On the other hand, the conditions (12)-(13) can be rewritten in terms of constraints on the mutual coherence $\mu$ involving the decay of the nonzero elements:

$$ \mu < \mu^* = \min \left( \frac{1}{k}, \mu_1^*, \dots, \mu_p^* \right), $$

with

$$ \mu_i^* = \frac{|x_i|}{|x_{i+1}|} \frac{2(k-g-i) + (g+i) \frac{|x_i|}{|x_{i+1}|}}{2(k-g-i) + (g+i) \frac{|x_i|}{|x_{i+1}|}}. $$

Depending on the decay of the nonzero coefficients, it can thus be seen that $\mu^* \in [\frac{1}{2k-g-1}, \frac{1}{k}]$. The strongest condition corresponds to (9) and is obtained for $|x_1| = |x_2|$; it ensures the uniform recovery of any $k$-sparse vector when $g$ good atoms have been selected during the first $g$ iterations. The weakest condition, $\mu < \frac{1}{k}$, is obtained as soon as $\frac{|x_i|}{|x_{i+1}|} \ge 2$ $\forall i \in \{1, \dots, k-g\}$. We thus recover a result similar to Corollary 1. Here, the decay constraints only apply to the elements in $Q^* \setminus Q$ since the elements in $Q$ have already been selected by assumption.

Let us now discuss the particularization of Theorem 3 to the problem of partial support recovery (here, $g$ is set to 0). We focus on the case where $p=r \le k$. We note that both (12)-(13) and (14)-(15) ensure the selection of elements of $Q^*$ during the first $p$ iterations of Oxx provided that the $p$ largest nonzero coefficients obey some “sufficient” decay (which is specified by either (13) or (15)). This leads to the following corollary for partial support recovery:

**Corollary 2** Let $p \in \{1, \dots, k\}$. If $\mu < \frac{1}{p}$ and the $p+1$ largest coefficients of $\mathbf{x}$ exhibit a sufficient decay (specified by (13) or (15)), then Oxx selects atoms in $Q^*$ during the first $p$ iterations.

We note that Corollary 2 (which makes use of the mild assumption $\mu < \frac{1}{p}$) does not guarantee that the selected atoms correspond to the $p$ largest coefficients of $\mathbf{x}$. Such guarantee can be obtained from (12)-(13) by imposing the stronger assumption $\mu < \frac{1}{k}$:

**Corollary 3** Let $p \in \{1, \dots, k\}$. If $\mu < \frac{1}{k}$ and the $p+1$ largest magnitudes in $\mathbf{x}$ exhibit a sufficient decay (13), then
Oxx selects atoms in $Q^*$ until the $p$ largest components of $\mathbf{x}$ have been selected.

Note that Corollary 3 does not state that Oxx will select the $p$ largest components of $\mathbf{x}$ during the first $p$ iterations. Their selection is however guaranteed during the first $k$ iterations.

### C. Compressible and Noisy Signals

In many situations, the sought vector $\mathbf{x}$ is not exactly $k$-sparse but rather compressible and possibly non-sparse. Furthermore, the observations are corrupted by some additive noise ($\mathbf{w} \neq \mathbf{0}_m$). We review hereafter some contributions of the literature dealing with the success of Oxx in this particular setup and provide new strongest results in Theorems 4 and 5. We will assume that the noise has a bounded $\ell_2$-norm, that is $\|\mathbf{w}\|_2 \le \epsilon$. In the following, a signal $\mathbf{x}$ will be referred to as “$k$-compressible” as soon as the sum of the absolute values of $k$ entries of $\mathbf{x}$ is large with respect to the remaining entries. Denoting by $\bar{Q}^* \triangleq \{1, \dots, n\} \setminus Q^*$ the complementary subset, the $k$-compressible assumption reads $\|\mathbf{x}_{\bar{Q}^*}\|_1 \gg \|\mathbf{x}_{\bar{Q}^*}\|_1$ for some subset $Q^*$ of cardinality $k$. $\mathbf{x}_{\bar{Q}^*}$ and $\mathbf{x}_{\bar{Q}^*}$ shall be thought of as the head and tail of the signal $\mathbf{x}$, respectively.

Let us first consider the $k$-sparse setup ($\mathbf{x}_{\bar{Q}^*} = \mathbf{0}_{n-k}$) with noisy observations ($\epsilon > 0$). Although many researchers have emphasized that the noiseless conditions can be generalized to the case where the noise level is low in comparison to the smallest nonzero coefficient of $\mathbf{x}$ [36]–[40], no tight condition of success for Oxx has been proposed so far. Among the noticeable coherence-based guarantees, we can nevertheless mention the work by Donoho et al. [36, Th. 5.1] (also rediscovered in [39, Th. 1]), stating that OMP succeeds if

$$ \mu < \frac{1}{2k-1}, \quad (16) $$

$$ |x_i| > \frac{2\epsilon}{1 - (2k-1)\mu}, \quad \forall i \in \{1, \dots, k\}. \quad (17) $$

To the best of our knowledge, the extension of these results to the success of OLS has never been made in the literature. We are neither aware of any contribution dealing with coherence-based conditions ensuring the recovery of a particular support for $k$-compressible vectors and noisy observations. We address these questions in the next theorems. The result stated in Theorem 4 implies, as a corollary, that (16)-(17) are sufficient conditions for both OMP and OLS. Theorem 5 is an extension of Theorem 2 to the noisy $k$-compressible setting. As in subsection II-A, we assume that the elements of $\mathbf{x}_{\bar{Q}^*}$ satisfy (4)-(5).

### Theorem 4 If

$$ \mu < \frac{1}{2k-1}, \quad (18) $$

and

$$ |x_i| > \frac{2(\|\mathbf{x}_{\bar{Q}^*}\|_1 + \epsilon)}{1 - (2k - i)\mu}, \quad \forall i \in \{1, \dots, k\}, \quad (19) $$

then Oxx selects atoms in $Q^*$ during the first $k$ iterations.

The conditions of Theorem 4 take the same form as those in (16)-(17) but depend on the $\ell_1$-norm of $\mathbf{x}_{\bar{Q}^*}$. Moreover,

condition (19) depends on the position $i$ of the ordered coefficients: the larger $i$, the weaker the constraint on their amplitude. As a result, when $\|\mathbf{x}_{\bar{Q}^*}\|_1 = 0$, Theorem 4 leads to weaker conditions than those previously proposed in [36], [39] as soon as $\mathbf{x}_{\bar{Q}^*}$ is not a flat vector. For flat vectors, (19) obviously reduces to (17). In such a case, Theorem 4 leads to the standard conditions by Donoho et al.

Let us mention that the conditions in Theorem 4 do not enforce any constraint on the decay of the coefficients in $Q^*$ (but only between the elements in $\bar{Q}^*$ and each component of $Q^*$). In the next theorem, we state “horizon-1” conditions of the same flavor as those presented in Theorems 2 and 3. Let us first define the following quantity:

$$ \gamma_k \triangleq \begin{cases} \frac{1-(k-2)\mu}{(\mu+1)(1-k\mu)} & \text{for OMP,} \\ \sqrt{\frac{1-(k-2)\mu}{\mu+1} \frac{\sqrt{1-(k-1)\mu}}{1-k\mu}} & \text{for OLS.} \end{cases} \quad (20) $$

Our result then writes as follows:

### Theorem 5 If

$$ \mu < \frac{1}{k}, \quad (21) $$

and $\forall i \in \{1, \dots, k\}$,

$$ |x_i| > \frac{2\mu(k-i)}{1-i\mu} |x_{i+1}| + 2\gamma_k(\epsilon + \|\mathbf{x}_{\bar{Q}^*}\|_1), \quad (22) $$

then Oxx selects atoms in $Q^*$ from noisy data during the first $k$ iterations.

Theorem 3 could be extended in a similar way to the framework of compressible and noisy signals but we do not detail this extension for conciseness.

## III. TECHNICAL DETAILS

In this section, we provide a proof of the theorems stated in section II. We first recall the main principles ruling OMP and OLS in section III-A. We then introduce some technical lemmas in section III-B. Finally the proof of the main results is exposed in section III-C.

### A. OMP and OLS

In order to precisely describe the update rules characterizing Oxx, let us first introduce some notations: given a set of indices $Q$, $A_Q$ represents the submatrix of $A$ specified by the columns indexed in $Q$; the projector onto the orthogonal complement of the column span of $A_Q$ is defined as $\mathbf{P}_{\bar{Q}}^{\perp} \triangleq \mathbf{I} - A_Q A_Q^{\dagger}$, where $A_Q^{\dagger}$ is the pseudo-inverse of $A_Q$; in particular, $\mathbf{r}^Q \triangleq \mathbf{P}_{\bar{Q}}^{\perp} \mathbf{y}$ is the residual error when projecting $\mathbf{y}$ onto the span of $A_Q$. Finally, $\langle \cdot, \cdot \rangle$ represents the vector inner product and $\mathbf{0}_m$ is the null vector of size $m \times 1$.

Oxx can be understood as an iterative procedure generating an estimate of $Q^*$ by sequentially adding one new element to the current support estimate, say $Q$. As detailed in Algorithm 1, OMP and OLS differ in the way this new element is selected. At each iteration, OLS selects the atom $a_j$ yielding the minimum residual error $\|\mathbf{r}^{Q \cup \{j\}}\|_2$:

$$ j \in \arg \min_{i \notin Q} \|\mathbf{r}^{Q \cup \{i\}}\|_2, $$
and $n - \text{Card}\{\mathcal{Q}\}$ least-square problems have to be solved to compute $\|\mathbf{r}^{\mathcal{Q}\cup\{i\}}\|_2$ for all $i \notin \mathcal{Q}$ [6]. On the contrary, OMP adopts the simpler rule

$$j \in \arg \max_{i \notin \mathcal{Q}} |\langle \mathbf{a}_i, \mathbf{r}^{\mathcal{Q}} \rangle|,$$

to select the new atom $\mathbf{a}_j$, and then solves only one least-square problem to update the new residual $\mathbf{r}^{\mathcal{Q}\cup\{j\}}$.

The selection rules described above can also be expressed in terms of the (normalized) projected atoms of the dictionary [13]. This formulation will turn out to be convenient in our proofs below. More specifically, let

$$\begin{aligned} \tilde{\mathbf{a}}_i &\triangleq \mathbf{P}_{\mathcal{Q}}^{\perp} \mathbf{a}_i, \\ \tilde{\mathbf{b}}_i &\triangleq \begin{cases} \tilde{\mathbf{a}}_i / \|\tilde{\mathbf{a}}_i\|_2 & \text{if } \tilde{\mathbf{a}}_i \neq \mathbf{0}_m \\ \mathbf{0}_m & \text{otherwise.} \end{cases} \end{aligned}$$

With these notations, the selection rule of Oxx can be re-expressed as (see e.g., [5])

$$j \in \arg \max_{i \notin \mathcal{Q}} |\langle \tilde{\mathbf{c}}_i, \mathbf{r}^{\mathcal{Q}} \rangle|, \quad (23)$$

where

$$\tilde{\mathbf{c}}_i \triangleq \begin{cases} \tilde{\mathbf{a}}_i & \text{for OMP,} \\ \tilde{\mathbf{b}}_i & \text{for OLS.} \end{cases}$$

For simplicity, the dependence of $\tilde{\mathbf{a}}_i$, $\tilde{\mathbf{b}}_i$ and $\tilde{\mathbf{c}}_i$ on $\mathcal{Q}$ does not appear in our notations. The reader should however keep this dependence in mind in our subsequent derivations.

## B. Some Useful Lemmas

We first state three useful lemmas, connecting different functions of the projected atoms to the mutual coherence of the dictionary.

**Lemma 1** Let $\text{Card}(\mathcal{Q}) = g \ge 0$. If $\mu < \frac{1}{g}$, then

$$\begin{aligned} \|\tilde{\mathbf{a}}_i\|_2^2 &\ge \frac{(\mu+1)(1-g\mu)}{1-(g-1)\mu} & \forall i \notin \mathcal{Q}, \\ |\langle \tilde{\mathbf{a}}_i, \tilde{\mathbf{a}}_j \rangle| &\le \frac{\mu(\mu+1)}{1-(g-1)\mu} & \forall j \ne i. \end{aligned} \quad (24)$$

*Proof:* The result is a direct consequence of Lemmas 4 and 10 in [14]. □

**Lemma 2** Let $\text{Card}(\mathcal{Q}) = g \ge 0$. If $\mu < \frac{1}{g}$, we have

$$\begin{aligned} |\langle \tilde{\mathbf{c}}_i, \tilde{\mathbf{a}}_i \rangle| &\ge \alpha_g > 0 & \forall i \notin \mathcal{Q}, \\ |\langle \tilde{\mathbf{c}}_i, \tilde{\mathbf{a}}_j \rangle| &\le \mu_g & \forall j \ne i, \end{aligned}$$

where

$$\alpha_g = \begin{cases} \frac{(\mu+1)(1-g\mu)}{1-(g-1)\mu} & \text{for OMP} \\ \sqrt{\frac{(\mu+1)(1-g\mu)}{1-(g-1)\mu}} & \text{for OLS} \end{cases} \quad (25)$$

$$\mu_g = \min \left\{ 1, \frac{\mu}{1-g\mu} \alpha_g \right\}. \quad (26)$$

*Proof:* The result immediately follows from Lemma 1 and from $\|\tilde{\mathbf{a}}_j\|_2 \le \|\mathbf{a}_j\|_2 = 1$ and $\|\tilde{\mathbf{c}}_i\|_2 \le 1$. Note that $\mu < \frac{1}{g}$ implies that $\tilde{\mathbf{a}}_i \ne \mathbf{0}_m$ (see (24)). Thus, $\tilde{\mathbf{b}}_i$ reads $\tilde{\mathbf{a}}_i / \|\tilde{\mathbf{a}}_i\|_2$. □

**Lemma 3** If $\mu \le \frac{1}{g+1}$, then (26) simplifies to:

$$\mu_g = \frac{\mu}{1-g\mu} \alpha_g. \quad (27)$$

*Proof:* $\mu \le \frac{1}{g+1}$ implies that $\mu \le 1 - g\mu$ and then

$$\frac{\mu}{1-g\mu} \alpha_g \le \alpha_g \le 1,$$

where $\alpha_g \le 1$ follows from $\forall i \notin \mathcal{Q}$, $\alpha_g \le \langle \tilde{\mathbf{c}}_i, \tilde{\mathbf{a}}_i \rangle \le \|\tilde{\mathbf{c}}_i\|_2 \|\tilde{\mathbf{a}}_i\|_2 \le 1$. □

Lemmas 2 and 3 are the building blocks of the next lemma, which provides sufficient conditions for Oxx to select a good atom at a given iteration:

**Lemma 4** Consider a (possibly non-sparse) signal $\mathbf{x}$ and a subset $\mathcal{Q}^*$ of cardinality $k$. Assume that Oxx, with $\mathbf{y}$ defined as in (1) as input, has selected atoms in $\mathcal{Q} \subsetneq \mathcal{Q}^*$ during the first $g$ iterations, with $0 \le g < k$. Let $\alpha_g$, $\mu_g$ be defined as in Lemma 2. If

$$\mu < \frac{1}{g}, \quad (28)$$

$$(\alpha_g + \mu_g) \|\mathbf{x}_{\mathcal{Q}^* \setminus \mathcal{Q}}\|_{\infty} - 2\mu_g \|\mathbf{x}_{\mathcal{Q}^* \setminus \mathcal{Q}}\|_1 > 2(\epsilon + \|\mathbf{x}_{\mathcal{Q}^*}\|_1), \quad (29)$$

then Oxx selects an atom in $\mathcal{Q}^* \setminus \mathcal{Q}$ at the next iteration.

*Proof:* We want to show that (28)-(29) implies

$$\max_{i \in \mathcal{Q}^* \setminus \mathcal{Q}} |\langle \tilde{\mathbf{c}}_i, \mathbf{r}^{\mathcal{Q}} \rangle| > |\langle \tilde{\mathbf{c}}_l, \mathbf{r}^{\mathcal{Q}} \rangle|, \quad \forall l \notin \mathcal{Q}^*. \quad (30)$$

First, using the definitions of the residual $\mathbf{r}^{\mathcal{Q}} = \mathbf{P}_{\mathcal{Q}}^{\perp} \mathbf{y}$ and the projected atoms $\tilde{\mathbf{a}}_i$, we have

$$\mathbf{r}^{\mathcal{Q}} = \mathbf{s}^{\mathcal{Q}} + \mathbf{P}_{\mathcal{Q}}^{\perp} \mathbf{w},$$

where

$$\mathbf{s}^{\mathcal{Q}} = \sum_{i \notin \mathcal{Q}} \tilde{\mathbf{a}}_i x_i.$$

Noticing that $\|\tilde{\mathbf{c}}_i\|_2 \le 1$ and $\|\mathbf{P}_{\mathcal{Q}}^{\perp} \mathbf{w}\|_2 \le \|\mathbf{w}\|_2 \le \epsilon$, a sufficient condition for (30) is then as follows:

$$\max_{i \in \mathcal{Q}^* \setminus \mathcal{Q}} |\langle \tilde{\mathbf{c}}_i, \mathbf{s}^{\mathcal{Q}} \rangle| - |\langle \tilde{\mathbf{c}}_l, \mathbf{s}^{\mathcal{Q}} \rangle| > 2\epsilon, \quad \forall l \notin \mathcal{Q}^*. \quad (31)$$

Let $j \in \arg \max_{i \in \mathcal{Q}^* \setminus \mathcal{Q}} |x_i|$. Since $\mu < \frac{1}{g}$, we can apply Lemma 2 and bound the terms in the left-hand side of (31) as follows:

$$\begin{aligned} \max_{i \in \mathcal{Q}^* \setminus \mathcal{Q}} |\langle \tilde{\mathbf{c}}_i, \mathbf{s}^{\mathcal{Q}} \rangle| &\ge |\langle \tilde{\mathbf{c}}_j, \mathbf{s}^{\mathcal{Q}} \rangle| \\ &\ge |\langle \tilde{\mathbf{c}}_j, \tilde{\mathbf{a}}_j \rangle| |x_j| - \sum_{i \notin \mathcal{Q} \cup \{j\}} |\langle \tilde{\mathbf{c}}_j, \tilde{\mathbf{a}}_i \rangle| |x_i| \\ &\ge \alpha_g |x_j| - \mu_g (\|\mathbf{x}_{\mathcal{Q}^* \setminus (\mathcal{Q} \cup \{j\})}\|_1 + \|\mathbf{x}_{\mathcal{Q}^*}\|_1), \end{aligned}$$

and $\forall l \notin \mathcal{Q}^*$,

$$\begin{aligned} |\langle \tilde{\mathbf{c}}_l, \mathbf{s}^{\mathcal{Q}} \rangle| &\le |\langle \tilde{\mathbf{c}}_l, \tilde{\mathbf{a}}_l \rangle| |x_l| + \sum_{i \notin \mathcal{Q} \cup \{l\}} |\langle \tilde{\mathbf{c}}_l, \tilde{\mathbf{a}}_i \rangle| |x_i| \\ &\le |x_l| + \mu_g (\|\mathbf{x}_{\mathcal{Q}^* \setminus \mathcal{Q}}\|_1 + \|\mathbf{x}_{\mathcal{Q}^* \setminus \{l\}}\|_1), \end{aligned}$$
where the last inequality follows from the fact that $|\langle \tilde{c}_l, \tilde{a}_l \rangle| \le 1$. Combining these two bounds, we easily obtain that

$$ (\alpha_g + \mu_g)|x_j| - 2\mu_g \|\mathbf{x}_{\mathcal{Q}^*} \setminus \mathcal{Q}\|_1 \\ > 2\epsilon + (1 - \mu_g)|x_l| + 2\mu_g \|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1 $$

is a sufficient condition for (31) and then (30). Finally, noticing that $\mu_g \le 1$ (Lemma 2) and $|x_l| \le \|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1$, we obtain (29). □

### C. Proofs of the Main Results

In this section, we provide a proof of the main theorems of the paper. We skip the proofs of the corollaries, which are straightforward. Theorems 1, 3, 4, 5 and the direct part of Theorem 2 are proved in section III-C1. The converse part of Theorem 2 (that is the tightness of the proposed conditions) is proved in section III-C2.

#### 1) Proofs of the Sufficient Conditions: All the proofs of this part use Lemma 4 as a key building block.

**Proof of Theorem 1:** We want to show that Oxx selects atoms in $\mathcal{Q}^*$ during the first $k$ iterations for all dictionaries obeying $\mu < \mu^*$, for some $\mu^* > \frac{1}{2k-1}$, as long as $\mathbf{x}_{\mathcal{Q}^*}$ is not a flat vector.

Let us first derive a condition on the mutual coherence ensuring that Oxx makes a correct decision at the first iteration. Particularizing the sufficient conditions of Lemma 4 to the case $\mathcal{Q} = \emptyset$ (with $\epsilon = 0$ and $\|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1 = 0$), we have that Oxx selects an element of $\mathcal{Q}^*$ provided that:

$$ \mu < \frac{\rho}{2 - \rho}, $$

with $\rho = \|\mathbf{x}_{\mathcal{Q}^*}\|_{\infty} / \|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1$. Now, since $\mathbf{x}_{\mathcal{Q}^*}$ is not flat, we have that $\rho > \frac{1}{k}$, and therefore $\frac{\rho}{2-\rho} > \frac{1}{2k-1}$.

On the other hand, if Oxx has selected any $g \ge 1$ atoms in $\mathcal{Q}^*$ during the first $g$ iterations, it was proved in [14, Th. 3] that Oxx makes good decisions during the remaining $k-g$ iterations provided that $\mu < \frac{1}{2k-g-1}$. A sufficient condition for Oxx to select correct atoms during the first $k$ steps thus simply writes

$$ \mu < \mu^* \quad \text{with} \quad \mu^* = \min \left( \frac{\rho}{2-\rho}, \frac{1}{2k-2} \right). $$

Clearly, $\mu^* > \frac{1}{2k-1}$ by definition. □

The direct part of Theorem 2 can be seen as a special case of Theorem 5 when $\epsilon = 0$ and $\mathbf{x}_{\bar{\mathcal{Q}}^*} = \mathbf{0}_{n-k}$, and of Theorem 3 with $g=0, r=p=k$. Hence, we focus on the latter proofs hereafter.

**Proof of Theorem 5:** Assume that Oxx has selected atoms in $\mathcal{Q} \subsetneq \mathcal{Q}^*$ when $g \le k-1$ iterations have been completed; we apply Lemma 4 to show that, under the hypotheses of Theorem 5, the next atom selected by Oxx belongs to $\mathcal{Q}^* \setminus \mathcal{Q}$.

The first condition of Lemma 4, $\mu < \frac{1}{g}$, is always verified since $\mu < \frac{1}{k}$ by hypothesis and $g \le k-1$. Let $j$ be the lowest

index such that:

$$ j \in \arg \max_{i \in \mathcal{Q}^* \setminus \mathcal{Q}} |x_i|. \quad (32) $$

Clearly, (5) implies that $j \le g+1$.

Because the nonzero coefficients have been sorted in the decreasing order, see (5), we have:

$$ \|\mathbf{x}_{\mathcal{Q}^* \setminus \mathcal{Q}}\|_1 \le |x_j| + (k - g - 1) |x_{j+1}|. \quad (33) $$

Hence,

$$ (\alpha_g - \mu_g)|x_j| - 2\mu_g(k - g - 1)|x_{j+1}| > 2(\epsilon + \|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1) \quad (34) $$

is a sufficient condition for (29). Since $g \le k-1$ and $\mu < \frac{1}{k}$ by assumption, we have $\mu < \frac{1}{g+1}$ and we can exploit the expression (27) of $\mu_g$ in Lemma 3 to rewrite:

$$ \alpha_g - \mu_g = \alpha_g \left( 1 - \frac{\mu}{1 - g\mu} \right) > 0. \quad (35) $$

It follows from (35) that

$$ \begin{aligned} \frac{\mu_g}{\alpha_g - \mu_g} &= \frac{\alpha_g}{\alpha_g - \mu_g} - 1, \\ &= \frac{1 - g\mu}{1 - (g+1)\mu} - 1, \\ &= \frac{\mu}{1 - (g+1)\mu}. \end{aligned} $$

Then, (34) can be rewritten as

$$ |x_j| > \frac{2\mu(k-g-1)}{1-(g+1)\mu} |x_{j+1}| + \frac{2(\epsilon + \|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1)}{\alpha_g - \mu_g}. \quad (36) $$

We finally obtain condition (22) by noticing that:

* $j \le g+1$ and the function $f(u) = \frac{2\mu(k-u)}{1-u\mu}$ is decreasing on $u \in [0, k]$ for $\mu < \frac{1}{k}$;

* $\alpha_g$ (see (25)) and $1 - \frac{\mu}{1-g\mu}$ are both decreasing with $g$ and non-negative, hence $1/(\alpha_g - \mu_g)$ (see (35)) is increasing with $g$. It is upper bounded by $1/(\alpha_{k-1} - \mu_{k-1})$, which is equal to $\gamma_k$ defined in (20).

We can thus conclude that (21)-(22) are sufficient conditions for (28)-(29) and the next atom selected by Oxx belongs to $\mathcal{Q}^* \setminus \mathcal{Q}$ by virtue of Lemma 4.

This proof applies recursively to the iterations of Oxx for increasing values of $g \in \{0, \dots, k-1\}$. □

The proofs of Theorems 3 and 4 follow a reasoning in the same vein as Theorem 5 but with some variations that we describe below.

**Proof of Theorem 3 (First Part):** By hypothesis, we assume that Oxx has selected atoms in $\mathcal{Q} \subsetneq \mathcal{Q}^*$ during the first $g$ iterations. We recursively show that, if (12) and (13) are satisfied, then Oxx keeps on picking atoms in $\mathcal{Q}^*$ as long as the $p$ largest elements of $\mathbf{x}_{\mathcal{Q}^* \setminus \mathcal{Q}}$ have not been selected.

Assume that after iteration $g+t$, $t \in \{0, \dots, k-g-1\}$, has been completed, Oxx has selected $\mathcal{Q}'$ with $\mathcal{Q} \subset \mathcal{Q}' \subsetneq \mathcal{Q}^*$ and $\{1, \dots, p\} \notin \mathcal{Q}'$ (that is, some atoms in $\{1, \dots, p\}$ have not yet been selected by Oxx). We apply Lemma 4 (with subset
$\mathcal{Q} \leftarrow \mathcal{Q}'$, and with $\epsilon \leftarrow 0$, $\mathbf{x}_{\bar{\mathcal{Q}}^*} \leftarrow \mathbf{0}_{n-k})$ to prove that the next atom selected by Oxx belongs to $\mathcal{Q}^*$. The first condition in Lemma 4, $\mu < \frac{1}{g+t}$, is verified since $\mu < \frac{1}{k}$ and $g+t < k$. Let $j$ be the lowest index such that

$$j \in \arg \max_{i \in \mathcal{Q}^* \setminus \mathcal{Q}'} |x_i|. \quad (37)$$

Because of our assumption $\{1, \dots, p\} \not\subseteq \mathcal{Q}'$ we necessarily have that $\{1, \dots, p\} \cap (\mathcal{Q}^* \setminus \mathcal{Q}') \neq \emptyset$, and then from convention (11), we must have $j \in \{1, \dots, p\}$. By the same arguments as those exposed in the proof of Theorem 5, we have that

$$|x_j| > \frac{2\mu(k-g-t-1)}{1-(g+t+1)\mu} |x_{j+1}| \quad (38)$$

is a sufficient condition for (29). Next, we have from the convention (11) that $j \le t+1$, and the function $f(u) = \frac{2\mu(k-u)}{1-u\mu}$ is decreasing on $u \in [0, k]$, hence on $u \in [g+j, g+t+1] \subseteq [0, k]$ for $\mu < 1/k$. So,

$$|x_j| > \frac{2\mu(k-g-j)}{1-(g+j)\mu} |x_{j+1}| \quad (39)$$

is sufficient for (38) and then (29). Since $j \in \{1, \dots, p\}$, (39) holds by virtue of (13) and the next atom selected by Oxx belongs to $\mathcal{Q}^*$.

**Proof of Theorem 3 (Second Part):** We show that (14) and (15) ensure that atoms in $\mathcal{Q}^* \setminus \mathcal{Q}$ are selected, provided that the $p$ largest elements of $\mathbf{x}_{\mathcal{Q}^* \setminus \mathcal{Q}}$ have not been selected and less than $g+r$ iterations have been carried out. The proof follows the same lines as the proof of the first part with some modifications that we describe hereafter.

Assume that Oxx has selected $\mathcal{Q}'$ with $\mathcal{Q} \subseteq \mathcal{Q}' \subsetneq \mathcal{Q}^*$ after iteration $g+t$ has been completed, with $t \in \{0, \dots, r-1\}$, and $\{1, \dots, p\} \not\subseteq \mathcal{Q}'$. We apply Lemma 4 (with subset $\mathcal{Q} \leftarrow \mathcal{Q}'$, $\epsilon \leftarrow 0$ and $\mathbf{x}_{\bar{\mathcal{Q}}^*} \leftarrow \mathbf{0}_{n-k})$ to show that the next atom selected by Oxx belongs to $\mathcal{Q}^*$. We note that the first condition of Lemma 4, $\mu < \frac{1}{g+t}$, is satisfied since $\mu < \frac{1}{g+r}$ by hypothesis and $t < r$.

Denoting by $j$ be the lowest index such that (37) is verified, we have by virtue of Lemma 4 that (38) is a sufficient condition for Oxx to select an atom in $\mathcal{Q}^*$ at the next iteration. From the same arguments as in proof of the first part, we must have $j \in \{1, \dots, p\}$.

Now, if $\frac{1}{k} \le \mu < \frac{1}{g+r}$, the function $f(u) = \frac{2\mu(k-u)}{1-u\mu}$ is nondecreasing on $u \in [g+t+1, g+r] \subseteq [0, g+r]$. As a consequence,

$$|x_j| > \frac{2\mu(k-g-r)}{1-(g+r)\mu} |x_{j+1}| \quad (40)$$

is a sufficient condition for (38) and then (29).

Since $j \in \{1, \dots, p\}$, (40) holds by virtue of (15) and the next atom selected by Oxx belongs to $\mathcal{Q}^*$.

**Proof of Theorem 4:** We first note that $\mu < \frac{1}{g+1} \quad \forall g \in \{0, \dots, k-1\}$ since $\mu < \frac{1}{2k-1}$ by hypothesis and $2k-1 \ge k \ge g+1$. The beginning of the proof follows the same lines as the proof of Theorem 5 but exploits that, by assumption

(5), $|x_j| \ge |x_{j+1}|$ for $j < k$. Let $j \le g+1$ be defined in (32). If $j < k$, (5) implies that:

$$(\alpha_g - \mu_g(2k - 2g - 1))|x_j| > 2(\epsilon + \|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1) \quad (41)$$

is a sufficient condition for (34). The same result holds in the case $j = k$, since then, $g = k-1$ and (41) identifies with (34).

Since $\mu < \frac{1}{g+1}$, Lemma 3 applies and we can use (27) to rewrite the latter condition as

$$\frac{\alpha_g}{1-g\mu}(1-(2k-g-1)\mu)|x_j| > 2(\epsilon + \|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1). \quad (42)$$

It can be easily checked from the definition of $\alpha_g$ in (25) that $\alpha_g \ge 1 - g\mu$ holds whenever $\mu < 1/g$. As a consequence, (42) can be relaxed as

$$(1 - (2k - g - 1)\mu) |x_j| > 2(\epsilon + \|\mathbf{x}_{\bar{\mathcal{Q}}^*}\|_1).$$

Finally, since $\mu < \frac{1}{2k-1} \le \frac{1}{2k-g-1}$ and $|x_j| \ge |x_{g+1}|$, this condition can be relaxed as (19). Hence, the atom selected by Oxx at iteration $g+1$ belongs to $\mathcal{Q}^* \setminus \mathcal{Q}$ by virtue of Lemma 4. $\square$

2) *Proof of the converse part of Theorem 2:* In this section, we prove that the conditions defined in (6)-(7) are worst-case necessary for the success of Oxx in the sense specified in Theorem 2. Our proof is based on the construction of an equiangular dictionary $\mathbf{A} \in \mathbb{R}^{(k+1) \times (k+1)}$ and a $k$-sparse vector $\mathbf{x} \in \mathbb{R}^{k+1}$ leading to a failure of Oxx during the first $k$ steps. More specifically, we show that the following type of situation occurs:

$$\max_{j \in \mathcal{Q}^*} |\langle \tilde{\mathbf{c}}_i, \mathbf{r}^Q \rangle| = |\langle \tilde{\mathbf{c}}_j, \mathbf{r}^Q \rangle| \quad \text{for some } j \notin \mathcal{Q}^*, \quad (43)$$

that is, there is an ambiguity in the choice of the next atom. In such a case, Oxx cannot be ensured to select a good atom.

Let $\mathbf{G} \in \mathbb{R}^{(k+1) \times (k+1)}$ be a matrix with ones on the diagonal and $-\mu$, with $\mu \le \frac{1}{k}$, elsewhere. $\mathbf{G}$ will play the role of the Gram matrix $\mathbf{G} = \mathbf{A}^T \mathbf{A}$. We will exploit the eigenvalue decomposition of $\mathbf{G}$ to construct a dictionary $\mathbf{A} \in \mathbb{R}^{(k+1) \times (k+1)}$ with the desired properties. Since $\mathbf{G}$ is symmetric, it can be expressed as

$$\mathbf{G} = \mathbf{U} \Lambda \mathbf{U}^T,$$

where $\mathbf{U}$ (respectively, $\Lambda$) is the unitary matrix whose columns are the eigenvectors (respectively, the diagonal matrix of eigenvalues) of $\mathbf{G}$. It is easy to check that $\mathbf{G}$ has only two distinct eigenvalues: $1+\mu$ with multiplicity $k$ and $1-k\mu$ with multiplicity one.

Because we assume $\mu \le \frac{1}{k}$, all the diagonal elements of $\Lambda$ are non-negative and the latter matrix can be factorized as $\Lambda = \Lambda^{1/2} \Lambda^{1/2}$. The dictionary $\mathbf{A}$ can then be defined as

$$\mathbf{A} = \Lambda^{1/2} \mathbf{U}^T. \quad (44)$$

We note that by definition, we have $\mathbf{A}^T \mathbf{A} = \mathbf{G}$, and therefore

$$|\langle \mathbf{a}_i, \mathbf{a}_j \rangle| = \mu \quad \forall i \neq j. \quad (45)$$

With this choice of dictionary, the following lemma holds:
**Lemma 5** Consider the dictionary **A** described above with $\mu \le \frac{1}{k}$. Then, we have for all $\mathcal{Q}$ with $\text{Card}(\mathcal{Q}) = g \le k - 1$:

$$ \begin{aligned} \langle \tilde{c}_i, \tilde{a}_i \rangle &= \alpha_g & \forall i \notin \mathcal{Q}, \\ \langle \tilde{c}_i, \tilde{a}_j \rangle &= -\mu_g & \forall i, j \notin \mathcal{Q}, i \neq j, \end{aligned} \quad (46) $$

where $\alpha_g$ and $\mu_g$ are defined in (25)-(27).

*Proof:* The expression (27) of $\mu_g$ holds since $\mu \le 1/(g+1)$.

The result (46) is obvious for $\mathcal{Q} = \emptyset$ since $\alpha_0 = 1$, $\mu_0 = \mu$ and $\forall i, \tilde{c}_i = \tilde{a}_i = \mathbf{a}_i$. We now address the case where $\mathcal{Q} \neq \emptyset$.

First notice that because $\text{Card}(\mathcal{Q}) = g \le k - 1$, the matrix $\mathbf{A}_{\mathcal{Q}}^T \mathbf{A}_{\mathcal{Q}}$ is invertible. Indeed, it is a symmetric matrix with ones on the diagonal and $-\mu$ elsewhere. Its eigenvalues (i.e., $1+\mu$ with multiplicity $g-1$ and $1-(g-1)\mu$ with multiplicity one) are therefore strictly positive if $\mu \le \frac{1}{k}$. Hence, the projected atoms $\tilde{a}_i$ can be expressed as

$$ \tilde{a}_i = \mathbf{a}_i - \mathbf{A}_{\mathcal{Q}} (\mathbf{A}_{\mathcal{Q}}^T \mathbf{A}_{\mathcal{Q}})^{-1} \mathbf{A}_{\mathcal{Q}}^T \mathbf{a}_i. $$

Using this expression, we also have

$$ \begin{aligned} \langle \tilde{a}_i, \tilde{a}_j \rangle &= \langle \mathbf{a}_i, \mathbf{a}_j \rangle - \mathbf{a}_i^T \mathbf{A}_{\mathcal{Q}} (\mathbf{A}_{\mathcal{Q}}^T \mathbf{A}_{\mathcal{Q}})^{-1} \mathbf{A}_{\mathcal{Q}}^T \mathbf{a}_j, \\ \| \tilde{a}_i \|_2^2 &= 1 - \mathbf{a}_i^T \mathbf{A}_{\mathcal{Q}} (\mathbf{A}_{\mathcal{Q}}^T \mathbf{A}_{\mathcal{Q}})^{-1} \mathbf{A}_{\mathcal{Q}}^T \mathbf{a}_i. \end{aligned} $$

Taking into account that the inner product between any pair of distinct atoms is equal to $-\mu$ by definition of $\mathbf{G} = \mathbf{A}^T \mathbf{A}$, we obtain for $i, j \notin \mathcal{Q}$:

$$ \begin{aligned} \langle \tilde{a}_i, \tilde{a}_j \rangle &= -\mu - \mu^2 \mathbf{1}_g^T (\mathbf{A}_{\mathcal{Q}}^T \mathbf{A}_{\mathcal{Q}})^{-1} \mathbf{1}_g, \\ \| \tilde{a}_i \|_2^2 &= 1 - \mu^2 \mathbf{1}_g^T (\mathbf{A}_{\mathcal{Q}}^T \mathbf{A}_{\mathcal{Q}})^{-1} \mathbf{1}_g, \end{aligned} \quad (47) $$

where $\mathbf{1}_g$ denotes the “all-ones” vector of dimension $g$.

Finally, we obtain the result for OMP ($\tilde{c}_i = \tilde{a}_i$) by noticing that $\mathbf{1}_g$ is an eigenvector of $(\mathbf{A}_{\mathcal{Q}}^T \mathbf{A}_{\mathcal{Q}})^{-1}$ with eigenvalue $\frac{1}{1-(g-1)\mu}$ and identifying the right-hand sides in (47) with (25) and (27). The proof of (46) for OLS ($\tilde{c}_i = \tilde{b}_i$) is a direct consequence of (46) in the case of OMP, using $\tilde{b}_i = \tilde{a}_i/\|\tilde{a}_i\|_2$. $\square$

To prove the tightness of each of the conditions (7), we need to introduce particular instances $\mathbf{x}^{(j)}$ of $\mathbf{x} \in \mathbb{R}^{k+1}$, for $j = 1, \dots, k-1$:

$$ \left\{ \begin{array}{ll} x_i^{(j)} & > \frac{2\mu(k-i)}{1-i\mu} x_{i+1}^{(j)} & \text{for } 1 \le i < j, \\ x_j^{(j)} & = \frac{2\mu(k-j)}{1-j\mu} x_{j+1}^{(j)} & \\ x_i^{(j)} & = 1 & \text{for } j+1 \le i \le k, \\ x_{k+1}^{(j)} & = 0. & \end{array} \right. \quad (48) $$

**Lemma 6** Consider the dictionary **A** described above with $\mu = \frac{1}{2k-j}$ and $\mathbf{x}^{(j)} \in \mathbb{R}^{k+1}$ defined as in (48), for $j \le k-1$. Then, the ordering (5) holds. Moreover, for $g \in \{0, \dots, j-1\}$, let $\mathcal{Q} = \{1, \dots, g\}$. Then, $\langle \tilde{c}_{g+1}, \mathbf{r}^Q \rangle \ge 0$ and

$$ (g+1) \in \arg \max_{i \in \mathcal{Q}} |\langle \tilde{c}_i, \mathbf{r}^Q \rangle|. \quad (49) $$

If $g < j - 1$, then $g+1$ is the unique minimizer of (49).

*Proof:* Let us first notice that $\mu = \frac{1}{2k-j}$ ensures that our working assumption (5) is met because $\frac{2\mu(k-i)}{1-i\mu} \ge 1$ for $i \le j$. Note also that $\mathbf{x}^{(j)}$ is non-negative.

Since $\mu = \frac{1}{2k-j}$ and $j \le k-1$, we have $\mu \le \frac{1}{k+1} < \frac{1}{g+1}$ and Lemma 3 applies, leading to $\frac{2\mu_g}{\alpha_g - \mu_g} = \frac{2\mu}{1-(g+1)\mu} > 0$. By virtue of (48), we have:

$$ (\alpha_g - \mu_g) x_{g+1}^{(j)} - 2\mu_g (k - g - 1) x_{g+2}^{(j)} \begin{cases} > 0 & \text{for } g < j - 1, \\ = 0 & \text{for } g = j - 1. \end{cases} \quad (50) $$

We first prove that $\langle \tilde{c}_{g+1}, \mathbf{r}^Q \rangle \ge 0$, $\forall g \le j - 1$. Indeed, applying Lemma 5, we have

$$ \begin{aligned} \langle \tilde{c}_{g+1}, \mathbf{r}^Q \rangle &= \langle \tilde{c}_{g+1}, \sum_{l \notin \mathcal{Q}} x_l^{(j)} \tilde{a}_l \rangle \\ &= \alpha_g x_{g+1}^{(j)} - \mu_g \sum_{l \notin \mathcal{Q} \cup \{g+1\}} x_l^{(j)} \\ &\ge \alpha_g x_{g+1}^{(j)} - \mu_g (k - g - 1) x_{g+2}^{(j)} \\ &\ge 0, \end{aligned} \quad (51) $$

where the first inequality follows from (5) and the second from (50) and $x_i^{(j)} \ge 0$ for all $i$.

We then show that (49) holds by proving that:

$$ \langle \tilde{c}_{g+1}, \mathbf{r}^Q \rangle - |\langle \tilde{c}_i, \mathbf{r}^Q \rangle| \ge 0, \quad \forall i \notin \mathcal{Q} \cup \{g+1\}. \quad (52) $$

For $s \in \{-1, 1\}$, let $f_i(s) \triangleq \langle \tilde{c}_{g+1}, \mathbf{r}^Q \rangle - s\langle \tilde{c}_i, \mathbf{r}^Q \rangle$. Obviously, (52) is satisfied if $f_i(s) \ge 0$, $\forall s \in \{-1, 1\}$. Applying Lemma 5 again, we obtain

$$ f_i(s) = \alpha_g x_{g+1}^{(j)} - \mu_g \sum_{l \notin \mathcal{Q} \cup \{g+1\}} x_l^{(j)} - s \left( \alpha_g x_i^{(j)} - \mu_g \sum_{l \notin \mathcal{Q} \cup \{i\}} x_l^{(j)} \right). \quad (53) $$

This leads to

$$ f_i(1) = (\alpha_g + \mu_g)(x_{g+1}^{(j)} - x_i^{(j)}) \ge 0, \quad (54) $$

since $x_{g+1}^{(j)} \ge x_i^{(j)} \ge 0$ from (5). Moreover,

$$ f_i(-1) = (\alpha_g + \mu_g)x_i^{(j)} + (\alpha_g - \mu_g)x_{g+1}^{(j)} - 2\mu_g \sum_{l \notin \mathcal{Q} \cup \{g+1\}} x_l^{(j)}. \quad (55) $$

Hence, from (50) and $x_i^{(j)} \ge 0$, we have that $f_i(s = -1)$ is non-negative, and strictly positive when $g < j - 1$.

Finally, we obtain that $g+1$ is the unique minimizer of (49) for $g < j - 1$ by noticing that $x_{g+1}^{(j)} > x_i^{(j)} \quad \forall i > g+1$, and that $\alpha_g > 0$ and $\mu_g > 0$ for $\mu < \frac{1}{g}$. The inequality in (54) is therefore strict for $g < j - 1$. $\square$

We are now ready to proceed with the proof of the converse of Theorem 2.

*Proof (converse of Theorem 2)*: We consider the dictionary defined above. We assume that $\mathcal{Q}^* = \{1, \dots, k\}$ and $\bar{\mathcal{Q}}^* = \{k+1\}$.

Let us first show that (6) is a universal bound for Oxx, i.e., it cannot be improved irrespective of the decay of the coefficients. By setting $\mu = \frac{1}{k}$, we show that Oxx leads to a failure during the first $k$ steps for any sparse representation $\mathbf{y} = \mathbf{A}\mathbf{x}$ supported by $\mathcal{Q}^*$. Indeed, suppose that Oxx has
selected atoms in $Q \subseteq Q^*$ during the first $k-1$ steps (if not, the result trivially holds). Then, denoting by $Q^* \setminus Q = \{i\}$ the remaining element in $Q^*$, we show that

$$|\langle \tilde{c}_i, \mathbf{r}^Q \rangle| = |\langle \tilde{c}_{k+1}, \mathbf{r}^Q \rangle|, \qquad (56)$$

i.e., a failure situation such as (43) occurs.

From the definition of the residual, we have $\mathbf{r}^Q = x_i \tilde{a}_i$. Since $x_i \neq 0$, proving (56) is equivalent to showing that

$$|\langle \tilde{c}_i, \tilde{a}_i \rangle| = |\langle \tilde{c}_{k+1}, \tilde{a}_i \rangle|,$$

or, by using Lemma 5, $\alpha_{k-1} = \mu_{k-1}$. The latter equality can indeed be seen to be true according to (27). We note that this result does not depend on a particular instance of k-sparse vector $\mathbf{x}$ (and thus on the decay) but only on the structure of the dictionary.

We now concentrate on the tightness of (7). Consider the specific dictionary described above and the k-sparse vector $\mathbf{x}^{(j)}$ defined in (48) with $\mu = \frac{1}{2k-j}$, $j \in \{1, \dots, k-1\}$. It is easy to verify that the inequality in (7) is met for $i \neq j$, but becomes an equality for $i = j$. It directly follows from Lemma 6 that our working hypothesis (5) is satisfied, and that $Q = \{1, \dots, j-1\}$ is selected during the first $j-1$ iterations. By virtue of the same lemma, we have

$$\max_{i \notin Q} |\langle \tilde{c}_i, \mathbf{r}^Q \rangle| = |\langle \tilde{c}_j, \mathbf{r}^Q \rangle| \qquad (57)$$

at the jth iteration ($g = j-1$). Moreover, using (55) and (50) with $i = k+1$ and $g = j-1$ yields $f_i(s = -1) = 0$, i.e., $\langle \tilde{c}_j, \mathbf{r}^Q \rangle + \langle \tilde{c}_{k+1}, \mathbf{r}^Q \rangle = 0$. We conclude from (57) that the failure situation $|\langle \tilde{c}_{k+1}, \mathbf{r}^Q \rangle| = |\langle \tilde{c}_j, \mathbf{r}^Q \rangle|$ occurs. $\square$

## IV. CONCLUSIONS

In this paper, we derived new guarantees of success for OMP and OLS. First, we showed that there exists a sufficient condition of success taking the form $\mu < \mu^*$ with $\mu^* \in (\frac{1}{2k-1}, \frac{1}{k}]$ as soon as the nonzero coefficients are not all equal (Theorem 1). This result thus shows that the traditional condition $\mu < 1/(2k-1)$ can be weakened for decaying vectors. We then presented a new “horizon-1” condition of success taking the decay of the nonzero coefficients into account (Theorem 2). In this condition, the specific upper bound $\mu^*$ is related to the rate of decay: the faster the decay, the larger $\mu^*$. This condition reduces to $\mu^* = 1/(2k-1)$ as soon as the two largest amplitudes in the sparse representation are equal ($|x_1| = |x_2|$). Because the sparse vector may not be flat in this situation, there is still room for further improvements. We note however that generalizing “horizon-1” conditions to more involved settings may not be an easy task.

Our decay-aware analysis of OMP/OLS also allowed us to carry out a finer analysis of these procedures at intermediate iterations. We considered both cases of “partial support recovery” and “successful termination” using a non-empty initial support. For these two cases, we showed that the resulting conditions of success can be improved with respect to the standard k-step analysis (Theorem 3).

In the compressible and noisy case (for bounded-noise), we extended our k-step analysis by showing that the constraint

on the mutual coherence is a function of the noise amplitude, the compressible part of the sparse vector and the coefficient decay (Theorems 4 and 5). One of our results improves over the conditions proposed by Donoho et al. for OMP [36] when the sparse vector obeys some decay.

In the noiseless setting, we proved the tightness of the proposed conditions (converse part of Theorem 2). First, we emphasized that $\mu < 1/k$ is a fundamental limit which cannot be improved. Moreover, we showed that the proposed conditions of success are the best achievable guarantees of this type. To some extent, our results thus provide a closure to the question of the characterization of the worst-case performance of OMP/OLS (in the noiseless setting) as a function of the mutual coherence of the dictionary.

Finally, let us mention that coherence-based conditions are easy to evaluate and thus, of practical interest to have some insights into the behavior of OMP/OLS. On the other side, coherence usually leads to quite pessimistic conditions. In particular, the conditions proposed in this paper, although improving over the standard uniform guarantees, still require a number of measurements scaling as $m \sim k^2$ to be satisfied for large underdetermined systems ($n \gg m$).<fnref n="6" /> We note that other lines of work have shown (in the uniform setting) that OMP/OLS can succeed in the regime $m \sim k$, see e.g., [4], [31]. The conditions derived in these works are however based on restricted isometry constants and of practical interest only for large random dictionaries since the explicit evaluation of restricted isometry constants is an NP-hard problem [42], [43].

## REFERENCES

[1] Y. C. Pati, R. Rezaiifar, and P. S. Krishnaprasad, “Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition,” in *Proc. 27th Ann. Asilomar Conf. Signals, Systems, and Computers*, 1993.

[2] A. Miller, *Subset Selection in Regression*, Second Editon, Chapman and Hall/CRC, 2 edition, Apr. 2002.

[3] S. F. Cotter, J. Adler, B. D. Rao, and K. Kreutz-Delgado, “Forward sequential algorithms for best basis selection,” *IEEE Proc. Vision, Image and Signal Processing*, vol. 146, no. 5, pp. 235–244, Oct. 1999.

[4] S. Foucart, “Stability and robustness of weak orthogonal matching pursuits,” in *Recent advances in harmonic analysis and applications*, D. Bilyk, L. De Carli, A. Petukhov, A. M. Stokolos, and B. D. Wick, Eds. 2013, vol. 25, pp. 395–405, Springer proceedings in Mathematics & Statistics.

[5] L. Rebollo-Neira and D. Lowe, “Optimized orthogonal matching pursuit approach,” *IEEE Signal Process. Lett.*, vol. 9, no. 4, pp. 137–140, Apr. 2002.

[6] S. Chen, S. A. Billings, and W. Luo, “Orthogonal least squares methods and their application to non-linear system identification,” *Int. J. Control*, vol. 50, no. 5, pp. 1873–1896, Nov. 1989.

[7] B. K. Natarajan, “Sparse approximate solutions to linear systems,” *SIAM J. Comput.*, vol. 24, pp. 227–234, Apr. 1995.

[8] J. A. Tropp, “Greed is good: algorithmic results for sparse approximation,” *IEEE Trans. Inf. Theory*, vol. 50, no. 10, pp. 2231–2242, Oct. 2004.

[9] M. A. Davenport and M. B. Wakin, “Analysis of orthogonal matching pursuit using the restricted isometry property,” *IEEE Trans. Inf. Theory*, vol. 56, no. 9, pp. 4395–4401, Sept. 2010.

[10] D. Needell and R. Vershynin, “Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit,” *Found. of Comput. Math.*, vol. 9, no. 3, pp. 317–334, June 2009.

<footnote n="6">⁶This can be seen by invoking the Welch bound $\mu \ge \sqrt{\frac{n-m}{m(n-1)}}$, see e.g., [41, Th 5.7].</footnote>
[11] 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*, vol. 58, no. 2, pp. 1094–1121, Feb. 2012.

[12] T. Blumensath and M. E. Davies, "On the difference between orthogonal matching pursuit and orthogonal least squares," Tech. Rep., University of Edinburgh, Mar. 2007.

[13] C. Soussen, R. Gribonval, J. Idier, and C. Herzet, "Joint *k*-step analysis of orthogonal matching pursuit and orthogonal least squares," *IEEE Trans. Inf. Theory*, vol. 59, no. 5, pp. 3158–3174, May 2013.

[14] C. Herzet, C. Soussen, J. Idier, and R. Gribonval, "Exact recovery conditions for sparse representations with partial support information," *IEEE Trans. Inf. Theory*, vol. 59, no. 11, pp. 7509–7524, Nov. 2013.

[15] Y. C. Eldar and H. Rauhut, "Average case analysis of multichannel sparse recovery using convex relaxation," *IEEE Trans. Inf. Theory*, vol. 56, no. 1, pp. 505–519, Jan. 2010.

[16] M. E. Davies and Y. C. Eldar, "Rank awareness in joint sparse recovery," *IEEE Trans. Inf. Theory*, vol. 58, no. 2, pp. 1135–1146, Feb. 2012.

[17] B. L. Sturm, "Sparse vector distributions and recovery from compressed sensing," Tech. Rep., Aalborg University Copenhagen, July 2011.

[18] J. A. Tropp and A. C. Gilbert, "Signal recovery from random measurements via orthogonal matching pursuit," *IEEE Trans. Inf. Theory*, vol. 53, no. 12, pp. 4655–4666, Dec. 2007.

[19] A. K. Fletcher and S. Rangan, "Orthogonal matching pursuit from noisy measurements: A new analysis," in *Neural Information Processing Systems*, Y. Bengio, D. Schuurmans, J. Lafferty, C. K. I. Williams, and A. Culotta, Eds. 2009, vol. 22, pp. 540–548, MIT Press.

[20] R. Gribonval, H. Rauhut, K. Schnass, and P. Vandergheynst, "Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms," *J. Fourier Anal. Appl.*, vol. 14, no. 5-6, pp. 655–687, Dec. 2008.

[21] W. Dai and O. Milenkovic, "Subspace pursuit for compressive sensing signal reconstruction," *IEEE Trans. Inf. Theory*, vol. 55, no. 5, pp. 2230–2249, May 2009.

[22] A. Maleki and D. L. Donoho, "Optimally tuned iterative reconstruction algorithms for compressed sensing," *IEEE J. Sel. Top. Signal Process.*, vol. 4, no. 2, pp. 330–341, Apr. 2010.

[23] J. D. Blanchard, J. Tanner, and K. Wei, "Conjugate gradient iterative hard thresholding: Observed noise stability for compressed sensing," *IEEE Trans. Signal Process.*, vol. 63, no. 2, pp. 528–537, Jan. 2015.

[24] S. Mallat, *A wavelet tour of signal processing*, Elsevier, Amsterdam, The Netherlands, 3rd edition, Dec. 2008.

[25] E. Vincent, N. Bertin, R. Gribonval, and F. Bimbot, "From blind to guided audio source separation: How models and side information can improve the separation of sound," *IEEE Signal Process. Mag.*, vol. 31, no. 3, pp. 107–115, Apr. 2014.

[26] Y. Jin and B. D. Rao, "Performance limits of matching pursuit algorithms," in *IEEE Int. Symp. on Information Theory*, July 2008, pp. 2444–2448.

[27] J. Ding, L. Chen, and Y. Gu, "Performance analysis of orthogonal matching pursuit under general perturbations," in *IEEE Int. Conf. Computing, Networking and Communications (ICNC)*, Jan. 2012, pp. 892–896.

[28] M. Ehler, M. Fornasier, and J. Sigl, "Quasi-linear compressed sensing," *SIAM J. Multiscale Model. Simul.*, vol. 12, no. 2, pp. 725–754, June 2014.

[29] Q. Mo and Y. Shen, "A remark on the restricted isometry property in orthogonal matching pursuit," *IEEE Trans. Inf. Theory*, vol. 58, no. 6, pp. 3654–3656, Jun 2012.

[30] 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*, vol. 60, no. 9, pp. 5702–5715, Sept. 2014.

[31] T. Zhang, "Sparse recovery with orthogonal matching pursuit under RIP," *IEEE Trans. Inf. Theory*, vol. 57, no. 9, pp. 6215–6221, Sept. 2011.

[32] T. T. Cai, L. Wang, and G. Xu, "Stable recovery of sparse signals and an oracle inequality," *IEEE Trans. Inf. Theory*, vol. 56, no. 7, pp. 3516–3522, July 2010.

[33] S. Chen, D. L. Donoho, and M. A. Saunders, "Atomic decomposition by Basis Pursuit," *SIAM J. Sci. Comp.*, vol. 20, no. 1, pp. 33–61, 1999.

[34] J. J. Fuchs, "On sparse representations in arbitrary redundant bases," *IEEE Trans. Inf. Theory*, vol. 50, no. 6, pp. 1341–1344, June 2004.

[35] M. D. Plumbley, "On polar polytopes and the recovery of sparse representations," *IEEE Trans. Inf. Theory*, vol. 53, no. 9, pp. 3188–3195, Sept. 2007.

[36] D. L. Donoho, M. Elad, and V. N. Temlyakov, "Stable recovery of sparse overcomplete representations in the presence of noise," *IEEE Trans. Inf. Theory*, vol. 52, no. 1, pp. 6–18, Jan. 2006.

[37] L. Denis, D. A. Lorenz, and D. Trede, "Greedy solution of ill-posed problems: error bounds and exact inversion," *Inverse Problems*, vol. 25, no. 11, pp. 115017+, Nov. 2009.

[38] Z. Ben-Haim, Y. C. Eldar, and M. Elad, "Coherence-based performance guarantees for estimating a sparse vector under random noise," *IEEE Trans. Sig. Process.*, vol. 58, no. 10, pp. 5030–5043, Oct. 2010.

[39] T. T. Cai and L. Wang, "Orthogonal matching pursuit for sparse signal recovery with noise," *IEEE Trans. Inf. Theory*, vol. 57, no. 7, pp. 4680–4688, July 2011.

[40] 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.*, vol. 20, no. 4, pp. 403–406, Apr. 2013.

[41] S. Foucart and H. Rauhut, *A mathematical introduction to compressive sensing*, Applied and Numerical Harmonic Analysis. Birkhäuser, Basel, June 2013.

[42] A. S. Bandeira, E. Dobriban, D. G. Mixon, and William F. Sawin, "Certifying the restricted isometry property is hard," *IEEE Trans. Inf. Theory*, vol. 59, no. 6, pp. 3448–3450, June 2013.

[43] A. M. Tillmann and M. E. Pfetsch, "The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing," *IEEE Trans. Inf. Theory*, vol. 60, no. 2, pp. 1248–1259, Feb. 2014.

PLACE
PHOTO
HERE

**Cédric Herzet** was born in Verviers, Belgium in 1978. He received the Electrical Engineering degree and the Ph.D. degree in Applied Science from the Université catholique de Louvain (UCL), Louvain-la-Neuve, Belgium, respectively in 2001 and 2006. From May 2006 to December 2007, he was a post-doctoral researcher within the "Ecole Normale Supérieure de Cachan", Paris, and the University of California, Berkeley (Fulbright scholarship). He is currently a researcher within the "Institut national de recherche en informatique et automatique" (INRIA),

Rennes, France. His topics of research include inverse problems, low-rank approximations and sparse representation algorithms.

PLACE
PHOTO
HERE

**Angélique Drémeau** was born in France in 1982. She received the State Engineering degree from Télécom Bretagne, Brest, France, in 2007 and the M.Sc. and the Ph.D. degree in signal processing and telecommunications from the Université de Rennes, Rennes, France, in 2007 and 2010, respectively. She is currently an associate professor at ENSTA Bretagne. Her research interests include inverse problems, sparse representation algorithms and underwater acoustics.

PLACE
PHOTO
HERE

**Charles Soussen** (M'12) was born in France in 1972. He graduated from the École Nationale Supérieure en Informatique et Mathématiques Appliquées, Grenoble, France in 1996. He received the Ph.D. degree in Physics from the Université de Paris-Sud, Orsay, France, in 2000 and his Habilitation à Diriger des Recherches in signal processing from the Université de Lorraine, France, in 2013. He is currently an Associate Professor at Université de Lorraine. He has been with the Centre de Recherche en Automatique de Nancy since 2005. His research

interests are in inverse problems and sparse approximation.