C Herzet

C Soussen

J Idier

R Gribonval
email: remi.gribonval@inria.fr

Exact Recovery Conditions for Sparse Representations with Partial Support Information

Keywords: Partial support information, ℓp relaxation, Orthogonal Matching Pursuit, Orthogonal Least Squares, mutual coherence, k-step analysis, exact support recovery

We address the exact recovery of a k-sparse vector in the noiseless setting when some partial information on the support is available. This partial information takes the form of either a subset of the true support or an approximate subset including wrong atoms as well. We derive a new sufficient and worst-case necessary (in some sense) condition for the success of some procedures based on ℓp-relaxation, Orthogonal Matching Pursuit (OMP) and Orthogonal Least Squares (OLS). Our result is based on the coherence µ of the dictionary and relaxes the wellknown condition µ < 1/(2k -1) ensuring the recovery of any k-sparse vector in the non-informed setup. It reads µ < 1/(2k -g + b -1) when the informed support is composed of g good atoms and b wrong atoms. We emphasize that our condition is complementary to some restrictedisometry based conditions by showing that none of them implies the other.

Because this mutual coherence condition is common to all procedures, we carry out a finer analysis based on the Null Space Property (NSP) and the Exact Recovery Condition (ERC). Connections are established regarding the characterization of ℓp-relaxation procedures and OMP in the informed setup. First, we emphasize that the truncated NSP enjoys an ordering property when p is decreased. Second, the partial ERC for OMP (ERC-OMP) implies in turn the truncated NSP for the informed ℓ 1 problem, and the truncated NSP for p < 1.

I. INTRODUCTION

Sparse representations aim at describing a signal as the combination of a few elementary signals (or atoms) taken from an overcomplete dictionary A. In particular, in a noiseless setting, one wishes to find the vector with the smallest number of non-zero elements satisfying a set of linear constraints, that is min x 0 subject to Ax = y, (P0)

where A ∈ R m×n , x ∈ R n , y ∈ R m . Unfortunately, problem (P0) is of combinatorial nature and, therefore, its resolution reveals to be intractable in most practical settings [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF].

In order to address this issue, suboptimal (but tractable) algorithms have been proposed in the literature. Among the most popular procedures, let us mention: i) the algorithms based on the ℓp-relaxation of the ℓ0 pseudo-norm; ii) the greedy algorithms, seen as suboptimal discrete search algorithms to address (P0). On the one hand, the ℓp relaxation of (P0) can be expressed as min x p subject to Ax = y, (Pp) with p ∈ (0, 1]. Practical implementations of (P1), also named Basis Pursuit [START_REF] Chen | Atomic decomposition by Basis Pursuit[END_REF] can be done optimally using linear programming algorithms, see e.g., [START_REF] Elad | Sparse and redundant representations: From theory to applications in signal and image processing[END_REF]; suboptimal procedures looking for a solution of (Pp) with p ∈ (0, 1) are for example derived in [START_REF] Gorodnitsky | Sparse signal reconstruction from limited data using FOCUSS: a re-weighted minimum norm algorithm[END_REF], [START_REF] Foucart | Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0 < q ≤ 1[END_REF].

On the other hand, (forward) greedy procedures build a sparse vector by gradually increasing the active subset starting from the empty set. At each iteration, a new atom is appended to the active subset. Standard greedy procedures include, by increasing order of complexity, Matching Pursuit (MP) [START_REF] Mallat | Matching pursuits with time-frequency dictionaries[END_REF], Orthogonal Matching Pursuit (OMP) [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF], Orthogonal Least Squares (OLS) [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF], [START_REF] Chen | Orthogonal least squares methods and their application to non-linear system identification[END_REF] and variants thereof, namely regularized OMP [START_REF] Needell | Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[END_REF], weak OMP [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF], stagewise OMP [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF], etc.

In this paper, we focus on a variation of the sparse representation problem in which the decoder has some information (possibly erroneous) about the support of the sparse vector. This new paradigm has recently been introduced independently in several contributions and finds practical and analytical interests in many setups.

In [START_REF] Von Borries | Compressed sensing using prior information[END_REF]- [START_REF] Bandeira | On partially sparse recovery[END_REF], the authors focussed on the problem of recovering a sequence of sparse vectors with a strong dependence on their supports. This type of settings occurs for example in video compression or dynamic magnetic resonance imaging where the supports of the sought vectors commonly evolve slowly with time. More specifically, this set of papers focusses on an ℓ1-relaxation of the following problem (or some slightly different variants thereof):

min x x Q 0 subject to Ax = y, (P0,Q)
where Q is an estimate of the sought support and x Q represents the vector made up of the elements of x whose index is not in Q.

More generally, the paradigm of sparse representation with side support information is of interest when some of the coefficients of the sparse decomposition can be easily identified a priori. For example, as mentioned in [START_REF] Jacques | A short note on compressed sensing with partially known signal support[END_REF], in wavelet image processing, the coefficients weighting the scaling functions are likely to be non-zero and this information should be (ideally) taken into account in any processing. It also happens in many practical situations that some coefficients of the sparse decomposition (typically those with high amplitudes) can be identified by simple thresholding. This observation is the essence of the algorithm proposed in [START_REF] Wang | Sparse signal reconstruction via iterative support detection[END_REF] where the authors look for a solution of (P0) by successively applying thresholding operations on the solution of ℓ1-relaxations of (P0,Q) to obtain a sequence of refined support estimates.

A slightly different, but related, perspective was considered in [START_REF] Karahanoglu | On the theoretical analysis of orthogonal matching pursuit with termination based on the residue[END_REF] for OMP and in [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF] for both OMP and OLS. In these papers, the authors derived guarantees of success for OMP and OLS by assuming that atoms belonging to some subset Q have been selected during the first iterations. The goal of such approaches is to provide a finer analysis of OMP/OLS at intermediate iterations by noting that the standard uniform recovery conditions ensuring the success of OMP/OLS from the first iteration are rather pessimistic. It is quite obvious that the conditions derived in these papers also apply to situations where OMP/OLS are initialized with support Q (rather than with the empty support). In the sequel, we will refer to this variant of OMP (resp. OLS) as OMPQ (resp. OLSQ). Clearly, OMPQ/OLSQ can be understood as greedy procedures looking for a solution of (P0,Q).

In this paper, we derive uniform recovery conditions for OMPQ/OLSQ and ℓp-relaxed versions of (P0,Q) in the paradigm of partially-informed decoders. Our conditions are valid for y = Ax ⋆ where x ⋆ is any k-sparse vector. Let us briefly summarize the related literature.

First, generalizing the well-known "Null-Space Property" (NSP) derived in [START_REF] Gribonval | Sparse representations in unions of bases[END_REF], the authors of [START_REF] Bandeira | On partially sparse recovery[END_REF], [START_REF] Wang | Sparse signal reconstruction via iterative support detection[END_REF], [START_REF] Chen | Convergence of reweighted ℓ 1 minimization algorithms and unique solution of truncated ℓp minimization[END_REF] proposed a "truncated" NSP, which is a sufficient and worst-case necessary condition for the success of

min x x Q p subject to Ax = y, (Pp,Q) with p ∈ [0, 1].
Secondly, in [START_REF] Vaswani | Modified-CS: Modifying compressive sensing for problems with partially known support[END_REF]- [START_REF] Friedlander | Recovering compressively sampled signals using partial support information[END_REF], a series of sufficient conditions based on restricted isometry constants (RICs) were proposed to guarantee the success of (P1,Q) (or some variants thereof).

Concerning OMPQ/OLSQ, the authors in [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF] derived a partial "Exact Recovery Condition" (ERC) extending Tropp's ERC to the partially-informed paradigm considered in this paper. The extended condition was shown to be sufficient but also worst-case necessary for the success of OMP/OLS when some support Q has been selected at an intermediate iteration. In [START_REF] Karahanoglu | On the theoretical analysis of orthogonal matching pursuit with termination based on the residue[END_REF], the authors proposed a sufficient condition based on RICs and depending on the number of "good" and "bad" atoms selected in Q, that is the number of elements of Q which are (resp. are not) in the support of x ⋆ .

In this paper, we derive a new simple recovery guarantee for OMPQ, OLSQ and (Pp,Q) for p ∈ [0, 1]. Our condition only depends on the mutual coherence of the dictionary µ and the number of good and bad atoms selected in the estimated support Q:

µ < 1 2k -g + b -1 , (1)
where g (resp. b) denotes the number of "good" (resp. "bad") atoms in Q. We show that (1) is sufficient for the success of (Pp,Q) with p ∈ [0, 1], OMPQ and OLSQ. We emphasize moreover that (1) is worst-case necessary in the following sense: there exists a dictionary A with µ = 1 2k-g+b-1 , a combination y of k columns of A and a support Q containing g good and b bad atoms such that neither (Pp,Q) nor OMPQ/OLSQ can recover x ⋆ . Our condition generalizes, within the informed paradigm, the well-known condition µ <1 2k-1 ensuring the success of Basis-Pursuit and OMP/OLS in the standard setup, see e.g., [START_REF] Gribonval | Sparse representations in unions of bases[END_REF], [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF], [START_REF] Gribonval | Highly sparse representations from dictionaries are unique and independent of the sparseness measure[END_REF]. In particular, we see that if the informed support Q contains more than 50% of good atoms, (1) leads to a weaker condition than its standard counterpart.

Although ensuring the success of (Pp,Q) and OMPQ/OLSQ, condition (1) does not allow for a discrimination of the performance achievable by these algorithms. In order to address this question, we analyze some connections existing between the conditions previously proposed in the literature. First, we show that the truncated NSP derived in [START_REF] Bandeira | On partially sparse recovery[END_REF], [START_REF] Wang | Sparse signal reconstruction via iterative support detection[END_REF], [START_REF] Chen | Convergence of reweighted ℓ 1 minimization algorithms and unique solution of truncated ℓp minimization[END_REF] enjoys a nesting property, namely: if the truncated NSP is satisfied for some p ∈ [0, 1], then it is also verified for any other q ∈ [0, p]. From a worst-case point of view, this result tends to show that the resolution of (Pp,Q) with p ∈ [0, 1) is more favorable than ℓ1-based approaches 1 . In particular, as a corrolary of this result, we have that all uniform conditions previously proposed for (P1,Q) also guarantee the success of (Pp,Q) with p ∈ [0, 1). Second, we establish that the partial ERC derived in [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF] for OMPQ is also a sufficient condition of success for (P1,Q). This generalizes the result derived by Tropp in the standard (non-informed) setup [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF] to the partially-informed context considered in this paper. On the other hand, we emphasize that, unlike in the standard setup, such a connection does not hold between (P1,Q) and OLSQ.

Finally, we also study the connection between the proposed coherence-based condition (1) and some RIC-based conditions previously proposed in the context of orthogonal greedy algorithms. First, we illustrate the complementarity of (1) with the RIC guarantees proposed in [START_REF] Karahanoglu | On the theoretical analysis of orthogonal matching pursuit with termination based on the residue[END_REF] for OMP. We emphasize that no condition implies the other one. Secondly, we show that the RIC condition proposed in [START_REF] Karahanoglu | On the theoretical analysis of orthogonal matching pursuit with termination based on the residue[END_REF] for the success of OMPQ also enjoys a form of quasi-tightness for both OMPQ and OLSQ.

The rest of this paper is organized as follows. In section II, we set the notations that will be used throughout the paper. In section III, we review the main expressions defining the recursions of OMP/OLS and briefly discuss their application to the informed problem (P0,Q). Our contributions and their positioning within the current state of the art are discussed in section IV. Finally, the remaining sections and appendices are dedicated to the proofs of our results.

II. NOTATIONS

The following notations will be used in this paper. . , . refers to the inner product between vectors and . stands for the Euclidean norm. . p with 0 ≤ p ≤ 1 will denote the ℓp (pseudo) norm. Of particular interest, the ℓ0 pseudo norm, . 0 , counts the number of non-zero elements in its argument. With a slight abuse of notation and for the sake of conciseness in some of our statements, we will assume that . 0 0 . 0. We will use the notation X † to denote the pseudo-inverse of a matrix X. For a full-rank and undercomplete matrix X, we have X † = (X T X) -1 X T where . T stands for the matrix transposition. When X is overcomplete, spark(X) denotes the minimum number of columns from X that are linearly dependent [START_REF] Donoho | Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization[END_REF]. 1m (resp 0m) denotes the all-one (resp. all-zero) vector of dimension m × 1. Im is the m × m identity matrix. Caligraphic letters (as Q, R, S, etc) will be used to denote some subsets of indices of the columns of the dictionary; the complementary of these sets in {1, . . . , n} will be denoted as Q, R, S, etc. In the main body of the paper, we will usually reserve the specific notations Q and Q ⋆ for, respectively, the informed support and the support of the sought sparse vector. XQ is the submatrix of X gathering the columns indexed by Q. For vectors, xQ denotes the subvector of x indexed by Q. We will denote the cardinality of Q as |Q|. We use the same notation to denote the absolute value of a scalar quantity. Given a subset of the columns of the dictionary AQ ∈ R m×|Q| , PQ = AQA † Q and P ⊥ Q = Im -PQ denote the orthogonal projection operators onto span(AQ) and span(AQ) ⊥ , where span(X) stands for the column span of X, span(X) ⊥ is the orthogonal complement of span(X). r Q = P ⊥ Q y = y -PQy denotes the data residual induced by the orthogonal projection of y onto span(AQ). Finally, we will use the notation ker(X) span(X T ) ⊥ to denote the null space of X; ker0(X) is the null-space of X minus the all-zero vector.

III. OMP AND OLS

In this section, we recall the selection rules defining OMP and OLS, and discuss their application to the support-informed problem (P0,Q). Throughout the paper, we will use the common acronym Oxx in statements that apply to both OMP and OLS.

First note that any vector x satisfying the constraint in (P0) must have a support, say Q = {i | xi = 0}, such that P ⊥ Qy = 0m since y must belong to span(A Q). Hence, problem (P0) can equivalently be rephrased as

min Q | Q| subject to P ⊥ Qy = 0m. (2)
Oxx can be understood as an iterative procedure searching for a solution of (2) by generating a sequence of support estimates {Q (ℓ) } as

Q (ℓ+1) = Q (ℓ) ∪ {j}, where j ∈ arg maxi | ai, r Q (ℓ) | for OMP arg mini r Q (ℓ) ∪{i} for OLS, (3)
r Q (ℓ) P ⊥ Q ℓ y is the current data residual and ai is the ith column of A. More specifically, Oxx adds one new atom to the estimated support at each iteration: OLS selects the atom minimizing the norm of the new residual r Q (ℓ) ∪{i} whereas OMP picks the atom maximizing the correlation with the current residual.

Oxx is commonly initialized with the empty set, i.e., Q (0) = ∅. However, when some initial estimate of the support, say Q, is available, nothing prevents us from initializing Oxx with Q (0) = Q. We will refer to this variant of Oxx as OxxQ 2 . On the one hand, OxxQ can readily be seen as a greedy procedure looking for a solution of (P0,Q). On the other hand, the behavior of OxxQ can be understood from a different perspective, namely the analysis of the standard Oxx algorithm at an intermediate iteration. Indeed, let us assume that Oxx has selected atoms in Q during the first |Q| iterations. Then, the next step of Oxx will be identical to the first iteration of OxxQ. Although we will mainly stick to the former vision hereafter, the results that will be derived in the paper can be interpreted from these two perspectives.

In the sequel, we will often use a slightly different, equivalent, formulation of (3) based on orthogonal projections. For some subset of the column indices R, let us define

ãR i P ⊥ R ai, bR i ãR i / ãR i if ãR i = 0m 0m
otherwise.

ãR i denotes the projection of ai onto span(AR) ⊥ whereas bR i is a normalized version of ãR i . With these notations, (3) can be reexpressed as

j ∈ arg max i | cQ (ℓ) i , r Q (ℓ) |, (4)
where

cR i ãR i for OMP, bR i for OLS.
The equivalence between (3) and ( 4) is straightforward for OMP by noticing that r Q (ℓ) ∈ span(A Q (ℓ) ) ⊥ . We refer the reader to [START_REF] Rebollo-Neira | Optimized orthogonal matching pursuit approach[END_REF] for a detailed derivation of the equivalence for OLS.

In the sequel, we will use the notations

ÃR (ã R 1 ãR 2 . . . ãR n ) ∈ R m×n , BR ( bR 1 bR 2 . . . bR n ) ∈ R m×n and CR (c R 1 cR 2 . . . cR n ) ∈ R m×n
to refer to the matrices whose columns are made up of the ãR i 's, bR i 's and cR i 's, respectively. When the set of indices R corresponds to the informed support Q, we will usually drop the dependence on R and use the simplified notations ãi, bi, ci, Ã, B and C.

IV. CONTEXT AND MAIN RESULTS

Let us assume that y is a linear combination of k columns of A indexed by Q ⋆ , that is

y = Ax ⋆ with x ⋆ i = 0 ⇔ i ∈ Q ⋆ , |Q ⋆ | = k. (5)
2 Let us note that, at the first iteration of Oxx Q , the residual is initialized by r Q P ⊥ Q y, i.e., the data y are being projected onto span(A Q ) ⊥ . In other words, Oxx Q behaves similarly with y or P ⊥ Q y as input vector.

In this section, we review some standard conditions ensuring the correct reconstruction of x ⋆ (with and without partial information on the support) and recast our contributions within these existing results. We will use the following conventions: the atoms whose indices are in Q ⋆ will be referred to as "good" atoms whereas atoms whose indices are not in Q ⋆ will be dubbed "bad" atoms. If an initial estimate of the support Q ⋆ is available, say Q, we will denote by g |Q ⋆ ∩ Q| the number of good atoms in Q and by b | Q⋆ ∩ Q| the number of bad atoms in Q. We will always implicitly assume that g < k since otherwise the informed problem (P0,Q) becomes trivial. Finally, we will suppose that the columns of A are normalized throughout the paper. Our contributions will be both at the level of OxxQ and (Pp,Q). In the next subsection we will focus on the conditions pertaining to Oxx and OxxQ whereas in subsection IV-B, we will describe the guarantees associated to the success of (Pp) and (Pp,Q). Let us mention that our contributions are uniform conditions derived within the context of worst-case analyses. Hence, hereafter, we will essentially limit our discussion to the contributions in this line of thought.

Before proceeding, we recall the standard definitions of the restricted isometry constant (RIC) and mutual coherence that will be used in our discussion: Definition 1 The k-th order restricted isometry constant of A is the smallest non-negative value δ k such that the following inequalities

(1 -δ k ) x 2 ≤ Ax 2 ≤ (1 + δ k ) x 2
are verified for any k-sparse vector x.

Definition 2

The mutual coherence µ of a dictionary A is defined as

µ = max i =j | ai, aj |.

A. Results and state-of-the-art conditions for Oxx and OxxQ

OMP has been widely studied in the recent years, including worstcase [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF], [START_REF] Davenport | Analysis of orthogonal matching pursuit using the restricted isometry property[END_REF] and probabilistic analyses [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF]. The existing exact recovery analyses of OMP were also adapted to several extensions of OMP, namely regularized OMP [START_REF] Needell | Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[END_REF], weak OMP [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF], and stagewise OMP [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF]. Although OLS has been known in the literature for a few decades (often under different names [START_REF] Blumensath | On the difference between orthogonal matching pursuit and orthogonal least squares[END_REF]), exact recovery analyses of OLS remain rare for two reasons. First, OLS is significantly more time consuming than OMP, therefore discouraging the choice of OLS for "real-time" applications, like in compressive sensing. Secondly, the selection rule of OLS is more complex, as the projected atoms are normalized. This makes the analysis of OLS more tricky. When the dictionary atoms are close to orthogonal, OLS and OMP have similar behaviors, as emphasized in [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF]. On the contrary, for correlated dictionaries (e.g., in ill-conditioned inverse problems), their behaviors significantly differ and OLS may be a better choice [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]. The above arguments motivate our analysis of both OMP and OLS.

Let us first rigorously define the notion of "success" that will be used for OxxQ throughout the paper: Definition 3 (Successful recovery) OxxQ with y defined in [START_REF] Foucart | Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0 < q ≤ 1[END_REF] as input succeeds if and only if it selects atoms in Q ⋆ \Q during the first kg iterations.

In particular, this definition implies that OxxQ exactly reconstructs x ⋆ after k-g iterations, as long as AQ⋆∪Q is full rank. When Q = ∅, OxxQ reduces to the standard implementation of Oxx. In this case, Definition 3 matches the classical "k-step" analysis encountered in many contributions of the literature.

We will assume that, in special cases where the OxxQ selection rule yields multiple solutions including a wrong atom, that is

max i∈Q ⋆ | cQ (ℓ) i , r Q (ℓ) | = max i / ∈Q ⋆ | cQ (ℓ) i , r Q (ℓ) |, (6)
OxxQ systematically makes a bad decision. Hence, situation ( 6) always leads to a recovery failure.

Let us mention that the notion of successful recovery may be defined in a weaker sense than in Definition 3: Plumbley [START_REF] Plumbley | On polar polytopes and the recovery of sparse representations[END_REF]Corollary 4] first pointed out that there exist problems for which "delayed recovery" occurs after more than k steps. Specifically, Oxx can select some wrong atoms during the first k iterations but ends up with a larger support including Q ⋆ with a number of iterations slightly greater than k. In the noise-free setting (for y ∈ span(AQ⋆ )), all atoms not belonging to Q ⋆ are then weighted by 0 in the solution vector (under some full-rank assumptions). Recently, a delayed recovery analysis of OMP using restricted-isometry constants was proposed in [START_REF] Zhang | Sparse recovery with orthogonal matching pursuit under RIP[END_REF] and then extended to the weak OMP algorithm (including OLS) in [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF].

To some extent, the definition of success considered in this paper also partially covers the setup of delayed recovery. Indeed, keeping in mind that OxxQ can be understood as a particular instance of Oxx in which atoms in Q have been selected during the first g + b iterations, any condition ensuring the success of OxxQ in the sense of Definition 3 also guarantees the success of Oxx in k + b iterations as long as atoms in Q are selected during the first g + b iterations. Conditions under which g good and b bad atoms are selected during the first iterations are however not discussed in the rest of the paper.

Regarding k-step analyses, the first thoughtful theoretical study of OMP is due to Tropp, see [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF]Th. 3.1 and Th. 3.10]. Tropp provided a sufficient and worst-case necessary condition for the exact recovery of any sparse vector with a given support Q ⋆ . The derivation of a similar condition for OLS is more recent and is due to Soussen et al. in [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]. In the latter paper, the authors carried out a narrow analysis of both OMP and OLS at any intermediate iteration of the algorithms. Their recovery conditions depend not only on Q ⋆ but also on the support Q (ℓ) estimated by Oxx at a given iteration ℓ. Recasting this analysis within the framework of sparse recovery with partial support information, Q (ℓ) plays the role of the estimated support Q, and the main result in [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF] can be rewritten as:

Theorem 1 (Soussen et al. 's partial ERC [20, Th. 3]) Assume that AQ⋆∪Q is full rank with |Q ⋆ | = k, |Q ⋆ ∩ Q| = g < k, and | Q⋆ ∩ Q| = b. If max i / ∈Q ⋆ C † Q ⋆ \Q ci 1 < 1, (7)
then for any y ∈ span(AQ⋆ ), OxxQ only selects atoms in Q ⋆ \Q during the first kg iterations. Conversely, if [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] does not hold, there exists y ∈ span(AQ⋆ ) for which OxxQ selects a bad atom j / ∈ Q ⋆ at the first iteration.

The proof of Theorem 1 is a straightforward adaptation of [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Th. 3]. For conciseness reasons, we therefore skip it. Let us just mention that the original formulation of [20, Th. 3] involves a vector y ∈ span(AQ⋆∪Q). Because any vector y ∈ span(AQ⋆∪Q) can be uniquely decomposed as y = y1 + y2 with y1 ∈ span(AQ⋆ ), y2 ∈ span(A Q⋆ ∩Q ) under full-rank conditions, and because OxxQ has the same behavior with y and y1 as inputs (the component y2 indexed by Q is not taken into account), both sufficient and necessary parts in Theorem 1 involve data vectors y ∈ span(AQ⋆ ).

Interestingly, when Q = ∅, Theorem 1 reduces to Tropp's ERC [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF]:

max i / ∈Q ⋆ A † Q ⋆ ai 1 < 1, (8)
which constitutes a sufficient and worst-case necessary condition for Oxx when no support information is available (or, equivalently, at the very first iteration of the algorithm).

A tight condition for the recovery of any k-sparse vector from any support estimate Q such that |Q ⋆ ∩ Q| = g, | Q⋆ ∩ Q| = b can therefore be expressed as

θOxx(k, g, b) < 1, where θOxx(k, g, b) max |Q ⋆ |=k max | Q⋆ ∩Q|=b |Q ⋆ ∩Q|=g max i / ∈Q ⋆ C † Q ⋆ \Q ci 1 . (9)
Unfortunately, the main drawback of ( 9) stands in its cumbersome (combinatorial) evaluation. In order to circumvent this issue, stronger conditions, but easier to evaluate, have been proposed in the literature. We can mainly distinguish between two types of "practical" guarantees: the conditions based on restricted-isometry constants and those based on the mutual coherence of the dictionary. The contributions [START_REF] Davenport | Analysis of orthogonal matching pursuit using the restricted isometry property[END_REF], [START_REF] Huang | Recovery of sparse signals using OMP and its variants: convergence analysis based on RIP[END_REF]- [START_REF] Wang | On the recovery limit of sparse signals using orthogonal matching pursuit[END_REF] provide RIC-based sufficient conditions for the exact recovery of the support Q ⋆ in k steps by OMP. The most recent and tightest results are due to Maleh [START_REF] Maleh | Improved RIP analysis of orthogonal matching pursuit[END_REF], Mo&Shen [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF] and Wang&Shim [START_REF] Wang | On the recovery limit of sparse signals using orthogonal matching pursuit[END_REF]. The authors proved that OMP succeeds in k steps if

δ k+1 < 1 √ k + 1 . (10)
In [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]Th. 3.2] and [36, Example 1], the authors showed moreover that this condition is almost tight, i.e., there exists a dictionary A with δ k+1 = 1

√ k and a k-term representation y for which OMP selects a wrong atom at the first iteration (this result was actually first conjectured by Dai&Milenkovic in [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF]). Let us mention that, by virtue of Theorem 1, these results remain valid for OLS. Indeed, when Q = ∅, (8) is a worst-case necessary condition of exact recovery for both OMP and OLS. Moreover, since (10) is a uniform sufficient condition for OMP, [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF] implies [START_REF] Chen | Orthogonal least squares methods and their application to non-linear system identification[END_REF]. Very recently, Karahanoglu and Erdogan [START_REF] Karahanoglu | On the theoretical analysis of orthogonal matching pursuit with termination based on the residue[END_REF] showed that the condition

δ k+b+1 < 1 √ k -g + 1 (11)
is sufficient for the success of OMPQ when some support information is available at the decoder. Similar conditions are still not available for OLSQ and remain an open problem in the literature.

In this paper, we emphasize that the RIC-based condition (11) also enjoys a type of worst-case necessity. In particular, the following result shows that [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] is almost tight for the success of OMPQ in the following sense: Lemma 1 (Quasi worst-case necessity of (11) for OxxQ) There exists a dictionary A, a k-term representation y and a set Q with

|Q ⋆ ∩ Q| = g and | Q⋆ ∩ Q| = b, such that: (i) δ k+b+1 = 1 √ k-g ;
(ii) OxxQ with y as input selects a bad atom at the first iteration.

The proof of this lemma is reported to section IX. Let us mention that the result stated in Lemma 1 is valid for both OMP and OLS. Hence, although [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] has not been proved to be a sufficient condition for the success of OLSQ, this result shows that one cannot expect to achieve much better guarantees in terms of RICs for this algorithm.

Regarding uniform conditions based on the mutual coherence of the dictionary, Tropp showed in [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF]Cor. 3.6

] that µ < 1 2k -1 (12)
is sufficient for the success of OMP in k steps. As a matter of fact, (12) therefore ensures that ( 8) is satisfied and thus also guarantees the success of OLS (Theorem 1 with Q = ∅). Moreover, Cai&Wang recently showed in [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF]Th. 3.1] that ( 12) is also worst-case necessary in the following sense: there exists (at least) one k-sparse vector x ⋆ and one dictionary A with µ = 1 2k-1 such that Oxx 3 cannot recover x ⋆ from y = Ax ⋆ . These results are summarized in the following theorem: The proof of this theorem is reported to sections V, VI and VIII. More specifically, we show in section V (resp. section VI) that ( 1) is sufficient for the success of OMPQ (resp. OLSQ) in kg iterations. The proof of this sufficient condition significantly differs for OMPQ and OLSQ. The result is shown for OMPQ by deriving an upper bound on Soussen et al. 's ERC-OMP condition [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] as a function of the restricted isometry bounds of the projected dictionary Ã. As for OLSQ, the proof is based on a connection between Soussen et al. 's ERC-OLS condition [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] and the mutual coherence of the normalized projected dictionary B. Finally, in section VIII we prove that (1) is worst-case necessary for OxxQ in the sense specified in Theorem 3. This proof is common to both OMPQ and OLSQ. If b = 0, we also prove a slightly stronger result by showing that the subset Q appearing in the converse part of Theorem 3 can indeed be "reached" by Oxx, initialized with the empty support. More formally, the following result holds: Lemma 2 (µ-based partial uniform condition for Oxx) There exist a dictionary A, a k-term representation y and a set Q ⊂ Q ⋆ with |Q| = g, such that:

(i) µ = 1 2k-g-1 ;
(ii) Oxx with y as input selects atoms in Q during the first g iterations and an atom ai, i / ∈ Q ⋆ \Q at the (g + 1)th iteration.

This result is of in interest in the analysis of Oxx at intermediate iterations since it shows that if µ < 1 2k-g-1 is not satisfied, there exist scenarios where Oxx selects good atoms during the first g iterations and then fails at the subsequent step. 3 and actually, any sparse representation algorithm.

B. Results and state-of-the-art conditions for (Pp) and (Pp,Q)

The performance associated to the resolution of (Pp) has been widely studied during the last decade. Among the noticeable works dealing with uniform and (worst-case) necessary conditions, one can first mention the seminal paper by Fuchs [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF] in which the author showed that the success of (P1) only depends on the sign of the nonzero components in x ⋆ . More recently, Wang et al. provided in [START_REF] Wang | On the performance of sparse recovery via ℓp-minimization[END_REF] sufficient and worst-case necessary conditions for the success of (Pp), with p ∈ (0, 1), depending on the sign-pattern of x ⋆ . On the other hand, Gribonval&Nielsen derived in [START_REF] Gribonval | Sparse representations in unions of bases[END_REF] the "Null-Space Property", a tight condition for the recovery of any k-sparse vector via (Pp).

Other conditions have also been proposed in terms of RIC and mutual coherence. On the one hand, the use of RIC-based conditions was ignited by Candes, Romberg and Tao in their seminal work [START_REF] Candes | Decoding by linear programming[END_REF]. Candes refined this result in [START_REF] Candes | The restricted isometry property and its implications for compressed sensing[END_REF] and some improvements were proposed by other authors in [START_REF] Foucart | Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0 < q ≤ 1[END_REF], [START_REF] Cai | Shifting inequality and recovery of sparse signals[END_REF].

On the other hand, guarantees for (P0) and (P1) based on the mutual coherence were early proposed in [START_REF] Donoho | Uncertainty principles and ideal atomic decomposition[END_REF] for the particular case of sparse representations in a union of two orthogonal bases. Several authors later proved independently that condition [START_REF] Von Borries | Compressed sensing using prior information[END_REF] ensures the success of (P0) and (P1) for any k-sparse vector in arbitrary redundant dictionaries, see e.g., [START_REF] Gribonval | Sparse representations in unions of bases[END_REF], [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF]. This condition was then shown to be valid for the success of (Pp) with p ∈ [0, 1] in [START_REF] Gribonval | Highly sparse representations from dictionaries are unique and independent of the sparseness measure[END_REF]. Finally, Cai&Wang emphasized in [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF]Th. 3.1] that ( 12) is also worst-case necessary (in some sense) for the success of (Pp).

Recently, several authors took a look at conditions ensuring the success of (Pp,Q) when some partial information Q is available about the support Q ⋆ . First, a "truncated" NSP generalizing the standard NSP has been derived in [17, Th. max

|Q ⋆ |=k max | Q⋆ ∩Q|=b |Q ⋆ ∩Q|=g max v∈ker 0 (A) v Q ⋆ \Q p p v Q∪Q ⋆ p p . ( 13
)
For any p ∈ [0, 1], if θp(k, g, b) ≤ 1, (14)
then any k-sparse vector x ⋆ is a minimizer of (Pp,Q) for any partial support estimate Q such that |Q ⋆ ∩ Q| = g and | Q⋆ ∩ Q| = b. Moreover, if the inequality in (14) holds strictly, x ⋆ is the unique solution of (Pp,Q). Conversely, if [START_REF] Vaswani | Modified-CS: Modifying compressive sensing for problems with partially known support[END_REF] is not satisfied, there exist a k-sparse vector x ⋆ and a support estimate Q satisfying |Q ⋆ ∩Q| = g and | Q⋆ ∩ Q| = b, such that x ⋆ is not a minimizer of (Pp,Q) with y = Ax ⋆ as input.

We note that the denominator in the right-hand side of ( 13) is always non-zero because of the hypothesis spark(A) > k + b = |Q ⋆ ∪ Q| (see also Appendix C). The direct part of Theorem 4 is proved in [START_REF] Wang | Sparse signal reconstruction via iterative support detection[END_REF] and [START_REF] Chen | Convergence of reweighted ℓ 1 minimization algorithms and unique solution of truncated ℓp minimization[END_REF] for (P1,Q) and (Pp,Q), respectively. In [START_REF] Bandeira | On partially sparse recovery[END_REF], the authors demonstrated both the direct and converse parts of Theorem 4 for (P1,Q). We verified that the converse part of Theorem 4 also holds for (Pp,Q), p ∈ [0, 1]. The proof is very similar to the exposition in [START_REF] Bandeira | On partially sparse recovery[END_REF] and [START_REF] Gribonval | Sparse representations in unions of bases[END_REF], and is therefore not reported here. We note that Theorem 4 reduces to the standard NSP as soon as g = b = 0. Several authors also proposed recovery guarantees in terms of RICs, see [START_REF] Vaswani | Modified-CS: Modifying compressive sensing for problems with partially known support[END_REF]- [START_REF] Friedlander | Recovering compressively sampled signals using partial support information[END_REF]. In [START_REF] Vaswani | Modified-CS: Modifying compressive sensing for problems with partially known support[END_REF], the authors identified a sufficient condition for the success of (P1,Q) and show that the latter condition is weaker than a condition derived in [START_REF] Candes | Decoding by linear programming[END_REF] for the non-informed setting as long as Q contains a "sufficiently" large number of good atoms. This result was later extended by Jacques [START_REF] Jacques | A short note on compressed sensing with partially known signal support[END_REF] to the cases of compressible signals and noisy observations. Finally, in [START_REF] Friedlander | Recovering compressively sampled signals using partial support information[END_REF], Friedlander et al. generalized the RIC condition derived in [START_REF] Candes | Decoding by linear programming[END_REF], [START_REF] Candes | The restricted isometry property and its implications for compressed sensing[END_REF] to the partially-informed paradigm considered in this paper. In particular, the authors showed that the following condition4

δ 2k < 1 + 2 1 + b -g k -1 , (15)
is sufficient for the success of (P1,Q). Interestingly, if g = b = 0, one recovers the standard condition δ 2k < (1 + √ 2) -1 by Candes for the success of (P1), [START_REF] Candes | The restricted isometry property and its implications for compressed sensing[END_REF]. Finally, we also mention the work by Khajehnejad et al. [START_REF] Amin Khajehnejad | Weighted ℓ 1 minimization for sparse recovery with prior information[END_REF] where a Grassman angle approach was used to characterize a class of signal which can be recovered by (a variant of) (P1,Q).

In this paper, we will show that the quantities θp(k, g, b) involved in the truncated NSP obey an ordering property and can be related to the partial ERC stated in Theorem 1 (see Theorems 6 and 7 below). As a consequence of these results, together with Theorem 3, we obtain that a coherence-based condition, similar to the one obtained for OxxQ, holds for the success of (Pp,Q):

Theorem 5 (µ-based uniform condition for (Pp,Q)) Consider a k-term representation y = Ax ⋆ and a support Q such that |Q ⋆ ∩ Q| = g and | Q⋆ ∩ Q| = b. If µ < 1 2k-g+b-1 holds, then
x ⋆ is the unique minimizer of (Pp,Q). Conversely, there exist a dictionary A and a k-term representation y = Ax ⋆ such that:

(i) µ = 1 2k-g+b-1 ; (ii) x ⋆ is not the unique minimizer of (Pp,Q).
The direct part of Theorem 5 is proved in section VII. The converse part will be shown in section VIII.

Interestingly, similar to the result by Friedlander et al. in [START_REF] Jacques | A short note on compressed sensing with partially known signal support[END_REF], we notice that our coherence-based condition becomes weaker than its standard counterpart [START_REF] Von Borries | Compressed sensing using prior information[END_REF] as soon as g > b, that is, when at least 50% of the atoms of Q belongs to Q ⋆ . In other words, the success of (Pp,Q) is ensured under conditions less restrictive than for (Pp) as soon as Q provides a "sufficiently reliable" information about Q ⋆ .

C. Relationships between conditions for (Pp,Q) and OxxQ

In this section, we discuss the implications (or non-implications) existing between some of the conditions mentioned above. First, we emphasize that an ordering property, similar to the one derived by Gribonval&Nielsen in [24, Lemma 7] for (Pp), still holds for the truncated NSPs defined in Theorem 4: Theorem 6 (Ordering property of truncated NSPs) If 0 ≤ q ≤ p ≤ 1 and spark(A) > k + b, the following ordering property holds:

θ0(k, g, b) ≤ θq(k, g, b) ≤ θp(k, g, b) ≤ θ1(k, g, b). ( 16
)
The proof of this result is reported to section VII. Clearly, one recovers Gribonval&Nielsen's ordering property as a particular case of ( 16) as soon as g = b = 0. This ordering property implies that any uniform condition for (Pp,Q) is also a sufficient condition of success for (Pq,Q) with q ∈ [0, p]. In particular, the guarantees derived in [START_REF] Vaswani | Modified-CS: Modifying compressive sensing for problems with partially known support[END_REF]- [START_REF] Friedlander | Recovering compressively sampled signals using partial support information[END_REF] for (P1,Q) also ensure the success of (Pp,Q) for p ∈ [0, 1]. Secondly, we show that the truncated NSPs share some connections with the partial ERC for OMP defined in [START_REF] Needell | Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[END_REF]. Specifically, we have

Theorem 7 If spark(A) > k + b, then θ1(k, g, b) ≤ θOMP(k, g, b). ( 17
)
The proof of this result is reported to section VII. This inclusion generalizes Tropp's result [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF]Th. 3.3] to the paradigm of sparse representation with partial support information, namely ERC-OMP is a sufficient condition of success for (P1,Q) (and thus for any (Pp,Q) with p ∈ [0, 1] by virtue of Theorems 4 and 6). As an important byproduct of this observation, it turns out that any uniform guarantee of success for OMPQ is also a sufficient condition of success for (Pp,Q).

It is noticeable that an ordering similar to [START_REF] Bandeira | On partially sparse recovery[END_REF] does not generally hold between θ1(k, g, b) and θOLS(k, g, b) for all k, g, b. Indeed, on the one hand, θOLS(k, 0, 0) ≥ θ1(k, 0, 0) since θOLS(k, 0, 0) = θOMP(k, 0, 0). On the other hand, we exhibit hereafter an example in which θOLS(k, g, b) < θ1(k, g, b): Example 1 In this example, we construct a dictionary such that

θ1(k, g, b) > 1, θOLS(k, g, b) < 1,
for some k, g, b. Let n ≥ 3 and define the matrix

G =   In-2 β1n-2 β1n-2 β1 T n-2 1 α β1 T n-2 α 1   , for α, β ∈ R,
which will play the role of the Gram matrix of the dictionary, that is G = A T A. Since G is symmetric it allows for the following eigenvalue decomposition:

G = UΛU T ,
where U (resp. Λ) is the unitary matrix whose columns are the eigenvectors (resp. the diagonal matrix of eigenvalues) of G. Letting

α = 1 2 γ 2 (n -2) -1, β = - γ 2 , with |γ| < (n -2) -1 ,
it is easy to see that G is a semi-definite positive matrix with one single zero eigenvalue. The zero eigenvalue is located in the lowerright corner of Λ and the corresponding eigenvector writes, up to a normalization factor, as

v = [γ1 T n-2 1 1] T . ( 18
)
We define A ∈ R n-1×n as

A = ΥU T ,
where Υ ∈ R n-1×n is such that

Υ(i, j) = Λ(i, i) if i = j, 0 otherwise. Hence, Υ T Υ = Λ and A T A = UΥ T ΥU T = UΛU T = G. Now, A is such that θOLS(k, g, b) < 1 < θ1(k, g, b) for k = 2, g = 1, b = 0.
Indeed, on the one hand it can easily be seen that ker(A) = ker(G) and ker(A) corresponds therefore to the one-dimensional subspace defined by v in [START_REF] Wang | Sparse signal reconstruction via iterative support detection[END_REF]. This implies that spark(A) = n. Moreover, considering Q ⋆ = {n -1, n} and Q = {n -1}, we have

θ1(2, 1, 0) ≥ v Q ⋆ \Q 1 v Q ⋆ ∪Q 1 = 1 (n -2)γ > 1
where the first inequality follows from the definition of θ1(2, 1, 0) and the last one from the fact that γ < (n -2) -1 . On the other hand, since spark(A) = n ≥ k + 1 and there is only one atom in Q ⋆ \Q, we have from [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Th. 6] that necessarily θOLS(2, 1, 0) < 1.

In the previous example, we provided a simple scenario where OLSQ succeeds in recovering x ⋆ when g = k -1. It can be observed that (P0,Q) also succeeds in this particular example. Indeed, using the definition of v in [START_REF] Wang | Sparse signal reconstruction via iterative support detection[END_REF], we have

θ0(2, 1, 0) = 1 (n -2) < 1.
More generally, it can be shown that there exists an equivalence between the success of (P0,Q) and OLSQ when g = k -1. This follows from the fact that the problem resolved by OLSQ when g = k -1, that is (3), is exactly equivalent to (P0,Q). From a more technical point of view, it can easily be seen that condition θ0(k, k -1, b) < 1 can be rephrased as

k + b + 1 < spark(A).
Now, by slightly extending the arguments developed in [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Th. 6], the latter condition is also sufficient and worst-case necessary for the success of OLSQ when g = k-1. This observation thus demonstrates the optimality of OLSQ when the informed support contains all the correct atoms but one.

D. Non-implication between the mutual and RIP conditions for OxxQ

In Theorem 3, we derived a novel guarantee of success for OxxQ in terms of mutual coherence of the dictionary. On the other hand, other conditions were previously proposed in terms of RICs for OMPQ, see [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF]. Hence, one legitimate question arises: is there any implication from (1) to [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] or vice versa? We show hereafter that the answer to this question is negative. In particular, we exhibit two particular instances of dictionary such that (1) is satisfied but [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] is not, and vice versa. We construct our examples in the case where b = 0 for the sake of conciseness. Similar constructions can however be applied to derive examples in the general case b = 0.

Example 2 (A satisfies (1) but not (11)) Let us consider A ∈ R (k+1)×(k+1) such that G A T A and Gi,j = -µ i = j 1 i = j with µ ≤ 1/k. We have therefore λmax(G) = 1 + µ (with multiplicity k), λmin(G) = 1 -kµ, and
δ k+1 = max{1 -λmin(G), λmax(G) -1} = kµ.
We can freely set µ = α/(2k -g -1) with 0 ≤ g < k and α ∈ (0, 1) since this yields µ < 1/k. Then, µ trivially satisfies [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF]. On the other hand, δ k+1 can be written as

δ k+1 = αk 2k -g -1 ≥ α/2. ( 19
)
For any g < k -1, there exist α ∈ (0, 1) and k such that (11) is not verified. For example, for k sufficiently large and fixed g < k -1, δ k+1 in [START_REF] Karahanoglu | On the theoretical analysis of orthogonal matching pursuit with termination based on the residue[END_REF] does not satisfy [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] since the right-hand side of [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] tends towards 0 when k tends to infinity.

Example 3 (A satisfies [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] but not (1)) Let

A a1 a2 H ∈ R (k+1)×(k+1) (20)
be such that

a T 1 a2 = µ, H T a1 = H T a2 = 0 k-1 , H T H = I k-1 .
Then, we easily have

λmax(G) = 1 + µ, λmin(G) = 1 -µ, and
δ k+1 = max{1 -λmin(G), λmax(G) -1} = µ. Let us set δ k+1 = µ = α/( √ k -g + 1)
with α ∈ (0, 1). Then, δ k+1 trivially satisfies [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF]. On the other hand, µ > 1/(2kg -1) holds for sufficiently large k and a fixed value of g < k.

Finally, we mention that, following the same procedures as above, one can derive examples for which [START_REF] Jacques | A short note on compressed sensing with partially known signal support[END_REF] is satisfied but (1) is not for some value of k, g, b, and vice versa. The details are however not reported here for the sake of conciseness.

V. SUFFICIENCY OF (1) FOR OMPQ

In this section, we prove the direct part of Theorem 3 for OMPQ. The result is a direct consequence of Proposition 1 stated below, which provides an upper bound on the left-hand side of (7) only depending on the mutual coherence of A:

Proposition 1 Let Q ⋆ and Q be such that |Q ⋆ | = k, |Q ⋆ ∩ Q| = g and | Q⋆ ∩ Q| = b. If µ < 1 k + b -1 , then max i / ∈Q ⋆ Ã † Q ⋆ \Q ãi 1 ≤ (k -g)µ 1 -(k + b -1)µ . (21)
The sufficient condition for OMPQ stated in Theorem 3 then derives from Proposition 1 and Theorem 1. Indeed, we see from Proposition 1 that

(k -g)µ 1 -(k + b -1)µ < 1 (22)
implies [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF]. Moreover, by reorganizing the latter expression, it is easy to see that ( 22) is equivalent to (1). To prove Theorem 3 it thus remains to apply Theorem 1. Now, the full-rankness of AQ⋆∪Q in the hypotheses of Theorem 1 is implicitly enforced by [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF]. Indeed, as shown in [23, Lemma 2.3], µ < 1 k+b-1 implies that AQ⋆∪Q is full rank whenever

|Q ⋆ ∪ Q| = k + b. Hence, since k + b -1 < 2k -g + b -1, (1)
in turn implies that any submatrix AQ⋆∪Q with |Q ⋆ ∪ Q| = k + b is full rank. Then, applying Theorem 1, we have that (1) is sufficient for the success of OMPQ in kg iterations.

Before proving Proposition 1, we need to define some quantities characterizing the projected dictionary à appearing in the implementation of OMP (see ( 4)) and state some useful lemmas. In the following definition, we generalize the concept of restricted isometry property (RIP) [START_REF] Candes | Decoding by linear programming[END_REF] to projected dictionaries, under the name projected RIP (P-RIP): Definition 4 Dictionary A satisfies the P-RIP(δ q,l , δq,l ) if and only if ∀R, S with |R| = l, |S| = q, R ∩ S = ∅, ∀xS we have

(1 -δ q,l ) xS 2 ≤ ÃR S xS 2 ≤ (1 + δq,l ) xS 2 .
The definition of the standard (asymmetric) restricted isometry constants corresponds to the tightest possible bounds when l = 0 (see e.g., [START_REF] Foucart | Sparsest solutions of underdetermined linear systems via ℓq-minimization for 0 < q ≤ 1[END_REF], [START_REF] Davies | Restricted isometry constants where ℓ p sparse recovery can fail for 0 ≪ p ≤ 1[END_REF]). For l ≥ 1, δ q,l and δq,l can be seen as (asymmetric) bounds on the restricted isometry constants of the projected dictionary ÃR . Note that δq,l might be negative since the columns of ÃR are not normalized ( ãR i ≤ 1). Note also that many well-known properties of the standard restricted isometry constants (see [START_REF] Needell | CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[END_REF]Proposition 3.1] for example) remain valid for δ q,l and δq,l .

The next lemma provides an upper bound on the left-hand side of (7) only depending on the P-RIP constants:

Lemma 3 Let Q ⋆ and Q be such that |Q ⋆ | = k, |Q ⋆ ∩ Q| = g and | Q⋆ ∩ Q| = b. If δ k-g,g+b < 1, then max i / ∈Q ⋆ Ã † Q ⋆ \Q ãi 1 ≤ (k -g) δ2,g+b + δ 2,g+b 2(1 -δ k-g,g+b ) . ( 23
)
The proof of Lemma 3 is reported to Appendix A. The next lemma provides some possible values for δ q,l and δq,l as a function of the mutual coherence of A:

Lemma 4 If µ < 1/(l -1), then A satisfies the P-RIP(δ q,l , δq,l ) for any q ≥ 0 with δq,l = (q -1)µ,

δ q,l = (q -1)µ + µ 2 ql 1 -(l -1)µ . ( (24)
) 25
The proof of this result is reported to Appendix A. We are now ready to prove Proposition 1:

Proof: (Proposition 1) We rewrite the right-hand side of (23) as a function of µ. From Lemma 4, we have that A satisfies the P-RIP(δ q,l , δq,l ) with constants defined in ( 24)-( 25) as long as

µ < 1 l -1 . (26)
Now, we have µ < 1/(k + b -1) by hypothesis, which implies µ < 1/(g + b -1). Thus, Lemma 4 can be applied with l = g + b.

Using ( 24) and ( 25), we calculate that: δ2,g+b + δ 2,g+b

2 = µ + µ 2 (g + b) 1 -(g + b -1)µ = µ(µ + 1) 1 -(g + b -1)µ , 1 -δ k-g,g+b = 1 -(k -g -1)µ - µ 2 (k -g)(g + b) 1 -(g + b -1)µ = 1 -(k + b -2)µ -(k + b -1)µ 2 1 -(g + b -1)µ = (µ + 1)(1 -(k + b -1)µ) 1 -(g + b -1)µ . ( 27
)
Therefore, the ratio in the right-hand side of ( 23) can be rewritten as δ2,g+b + δ 2,g+b

2(1 -δ k-g,g+b ) = µ 1 -(k + b -1)µ . ( 28
)
According to [START_REF] Davenport | Analysis of orthogonal matching pursuit using the restricted isometry property[END_REF], µ < 1/(k + b -1) ≤ 1/(g + b -1) implies that 1δ k-g,g+b > 0. Lemma 3 combined with [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF] implies that ( 21) is met.

VI. SUFFICIENCY OF (1) FOR OLSQ

We now prove the sufficient condition for OLSQ stated in Theorem 3. The result is a consequence of Proposition 2 and Lemma 5 stated below. We first need to introduce the coherence of the normalized projected dictionary BR : Definition 5 (Coherence of the normalized projected dictionary)

µ OLS l = max |R|=l max i =j | bR i , bR j |.
The following proposition gives a sufficient condition on µ OLS g+b under which ( 7) is satisfied:

Proposition 2 Let Q ⋆ and Q be such that |Q ⋆ | = k, |Q ⋆ ∩ Q| = g and | Q⋆ ∩ Q| = b. Assume that AQ⋆∪Q is full rank. If µ OLS g+b < 1/(2k -2g -1), then max i / ∈Q ⋆ B † Q ⋆ \Q bi 1 < 1. ( 29
)
Proof: When bi = 0, the result is obvious. When bi = 0, apply [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF]Cor. 3.6] (that is: if A has normalized columns and µ < 1/(2k -1) then Tropp's ERC is satisfied, i.e., ∀Q ⋆ such that

|Q ⋆ | = k, max i / ∈Q ⋆ A † Q ⋆ ai 1 < 1)
to the matrix B and to Q ⋆ \Q of size kg. The atoms of BQ ⋆ \Q are of unit norm (actually, BQ ⋆ \Q is full rank) because AQ⋆∪Q is full rank [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Cor. 3].

The next lemma provides a useful upper bound on µ OLS l as a function of the coherence µ of the dictionary A:

Lemma 5 If µ < 1/l, then µ OLS l ≤ µ 1 -lµ . ( 30
)
The proof of this result is reported to Appendix B. The sufficient condition stated in Theorem 3 for OLSQ then follows from the combination of Proposition 2 and Lemma 5. Indeed, [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF]

implies µ < 1/(k + b -1) ≤ 1/(g + b) since 2k -g + b -1 = k + b -1 + (k -g) > k + b -1 ≥ g + b.
Hence, the result follows by first applying Lemma 5 and (1):

µ OLS g+b ≤ µ 1 -(g + b)µ < 1 2k -2g -1 ,
and then Proposition 2, which implies [START_REF] Blumensath | On the difference between orthogonal matching pursuit and orthogonal least squares[END_REF]. µ < 1/(k+b-1) implies that the full rank assumption of Proposition 2 is met for any

Q ⋆ ∪ Q of cardinality k + b [23, Lemma 2.3].
VII. ORDERING PROPERTIES AND SUFFICIENCY OF [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF] FOR THE SUCCESS OF (Pp,Q) In this section, we elaborate on the proofs of Theorems 5 (direct part), 6 and 7. These results have been gathered in this section since they are all related to some guarantees of success for (Pp,Q): Theorem 5 shows that (1) is a sufficient and worst-case necessary condition for the success of (Pp,Q); Theorem 6 establishes an ordering property between the truncated NSPs for different values of p ∈ [0, 1]; Theorem 7 emphasizes that the ERC-OMP ( 9) is also a sufficient condition for the success of (P1,Q) and in turn, of (Pp,Q) for p < 1.

Theorems 6 and 7 follow from some technical lemmas which are stated below and proved in Appendix C. The proof of the direct part of Theorem 5 is a consequence of Theorems 6, 7 and is discussed at the end of this section. The proof of the converse part of Theorem 5 is reported to the next section.

We first turn our attention to the proof of the NSP ordering stated in Theorem 6. The result follows from the following lemma: Lemma 6 Assume spark(A) > k + b and let ∀v ∈ ker0(A):

θp(k, g, b, v) max |Q ⋆ |=k max | Q⋆ ∩Q|=b |Q ⋆ ∩Q|=g v Q ⋆ \Q p p v Q∪Q ⋆ p p . ( 31
)
Then, the following inequality holds for 0 ≤ q < p ≤ 1:

θq(k, g, b, v) ≤ θp(k, g, b, v). (32)
Obviously, taking the supremum with respect to v ∈ ker0(A) of both sides in [START_REF] Huang | Recovery of sparse signals using OMP and its variants: convergence analysis based on RIP[END_REF] leads to the result stated in Theorem 6.

Secondly, the inequality relating θ1(k, g, b) to θOMP(k, g, b) in Theorem 7 is a consequence of the next result:

Lemma 7 If spark(A) > k + b, then v Q ⋆ \Q 1 v Q ⋆ ∪Q 1 ≤ max i / ∈Q ⋆ Ã † Q ⋆ \Q ãi 1 ( 33
)
for any v ∈ ker0(A) and

Q ⋆ , Q with |Q ⋆ | = k, |Q ⋆ ∩ Q| = g < k, | Q⋆ ∩ Q| = b.
Theorem 7 then follows by taking the supremum of both sides of [START_REF] Liu | The orthogonal super greedy algorithm and applications in compressed sensing[END_REF] with respect to v ∈ ker0(A) and

Q ⋆ , Q with |Q ⋆ | = k, |Q ⋆ ∩Q| = g and | Q⋆ ∩ Q| = b.
We are now ready to prove the sufficiency of ( 1) for (Pp,Q):

Proof: (Direct part of Theorem 5) On the one hand, let us first note that (1) is sufficient for the success of OMPQ for any ksparse representation y = Ax ⋆ (Theorem 3). Hence, (1) implies that θOMP(k, g, b) < 1 since the latter condition is worst-necessary for the success of OMPQ (Theorem 1). On the other hand, from [23, Th. The result then follows from Theorem 4.

VIII. WORST-CASE NECESSITY OF (1)

A. General case b ≥ 0

Cai&Wang recently showed in [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF]Th. 3.1] that there exist dictionaries A with µ = 1 2k-1 and a vector y ∈ span(A) having two disjoint k-sparse representations in A. In other words, if µ < 1 2k-1 is not satisfied, there exist instances of dictionaries such that no algorithm can univocally recover some k-sparse representations. In the context of Oxx, their result can be rephrased as the following worst-case necessary condition: there exists a dictionary A with µ = 1 2k-1 and a support Q ⋆ , with |Q ⋆ | = k, such that Oxx selects a wrong atom at the first iteration.

In this section, we show that (1) is worst-case necessary for (Pp,Q) and OxxQ in the sense defined in Theorems 3 and 5, respectively. To prove the result for (Pp,Q), we will construct a dictionary A satisfying µ =

The result then immediately follows from Theorem 4. Invoking Theorem 7 and the converse part of Theorem 1, (34) also leads to the result for OMPQ: in particular, θOMP(k, g, b) ≥ 1. On the other hand, since θOLS(k, g, b) and θ1(k, g, b) do not enjoy a nesting property similar to [START_REF] Bandeira | On partially sparse recovery[END_REF], specific arguments need to be derived to prove the worst-case necessity of (1) for OLSQ. Regarding OLSQ (and actually, also OMPQ), we will show using the same dictionary as for (Pp,Q), that there exists a k-term representation y = Ax ⋆ satisfying the hypotheses of Theorem 3 and such that OxxQ selects a wrong atom at the first iteration. The proofs for OxxQ and (Pp,Q) use a dictionary construction similar to Cai&Wang's in [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF].

Let G ∈ R (2k-g+b)×(2k-g+b) be the matrix with ones on the diagonal and -µ -1 2k-g+b-1 elsewhere. G will play the role of the Gram matrix G = A T A. We will exploit the eigenvalue decomposition of G to construct the dictionary A ∈ R (2k-g+b-1)×(2k-g+b) with the desired properties. Since G is symmetric, it can be expressed as

G = UΛU T ,
where U (resp. Λ) is the unitary matrix whose columns are the eigenvectors (resp. the diagonal matrix of eigenvalues) of G. It is easy to check (see Example 2) that G has only two distinct eigenvalues: 1 + µ with multiplicity 2kg + b -1 and 0 with multiplicity one; moreover, the eigenvector associated to the null eigenvalue is equal to 1 2k-g+b . The eigenvalues are sorted in the decreasing order so that 0 appears in the lower right corner of Λ.

We define A ∈ R (2k-g+b-1)×(2k-g+b) as

A = ΥU T , (35)
where Υ ∈ R (2k-g+b-1)×(2k-g+b) is such that

Υ(i, j) = √ 1 + µ if i = j, 0 otherwise.
Note that Υ T Υ = Λ. Hence, A satisfies the statement (i) in the converse part of Theorems 3 and 5 since

A T A = UΥ T ΥU T = UΛU T = G,
and therefore ai, aj = -µ ∀i = j.

Since G = A T A, we have Gx = 0 2k-g+b if and only if Ax = 0 2k-g+b . Moreover, since G has one single zero eigenvalue with eigenvector 1 2k-g+b , the null-space of A is the one-dimensional space spanned by 1 2k-g+b . Therefore, any l < 2kg + b columns of A are linearly independent, i.e., spark(

A) = 2k -g + b > k + b.
Taking these observations into account, it easily follows that (34) holds since

v Q ⋆ \Q p p = v Q ⋆ ∪Q p p = k -g, for v = 1 2k-g+b ∈ ker0(A), and ∀ Q ⋆ ,Q with |Q ⋆ | = k, |Q ⋆ ∩ Q| = g and | Q⋆ ∩ Q| = b.
This proves the necessary part of Theorem 5.

We now address the case of OLS. Although the OMP necessity result is already obtained from the (Pp,Q) necessity result, the construction related to OLS is also valid for OMP. For the sake of generality, we develop our arguments for both OMP and OLS hereafter. We first need the following technical lemma whose proof is reported to Appendix D: Lemma 8 Let A be defined as in [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]. Then, for any subset Q with |Q| = g + b, there exists a vector ỹ having two (kg)term representations with disjoint supports in the projected dictionary C\Q C{1,...,2k-g+b}\Q ∈ R (2k-g+b-1)×(2k-2g) .

We are now ready to prove the worst-case necessity of (1) for OxxQ:

Proof: (Converse part of Theorem 3) We show that there exists a k-sparse representation y such that OxxQ selects a wrong at the first iteration with the dictionary A defined in [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]. Our construction of such y is as follows. Let Q be a subset of cardinality g + b, arbitrarily chosen (say, the first g + b atoms of the dictionary). We consider the following decomposition Q = Qg ∪ Q b where Qg and Q b are the subsets collecting respectively the good and the bad atoms in Q, with Qg ∩ Q b = ∅. Let ỹ2 be a vector having two (kg)term representations in the projected dictionary C\Q . We note that such a vector ỹ2 exists by virtue of Lemma 8. We will denote the respective supports of the two representations of ỹ2 by Q1 and Q2 with Q1 ∩ Q2 = ∅. Hence,

ỹ2 = CQ 1 xQ 1 = CQ 2 xQ 2 ,
for some vectors xQ 1 and xQ 2 . We then define the k-sparse representation y y1 + y2, where y1 = AQ g 1 |Qg | and y2 = AQ i xQ i ∈ span(AQ i ) with i = 1 or i = 2. The specific value of i will be determined hereafter so that a failure situation occurs. The selection rule (4) indicates that the atom ãj selected by OxxQ at the first iteration satisfies:

j ∈ arg max i | ci, P ⊥ Q y | = arg max i | ci, ỹ2 |, since P ⊥ Q y = P ⊥ Q y2 = ỹ2
. Now, we set Q ⋆ in such a way that j / ∈ Q ⋆ :

Q ⋆ = Qg ∪ Q1 if j ∈ Q2, Qg ∪ Q2 if j ∈ Q1. (37)
To complete the proof, it is easy to check that y = y1 + y2 ∈ span(AQ⋆ ): indeed, y1 ∈ span(AQ g ) ⊂ span(AQ⋆ ) and y2 ∈ span(A Q ⋆ \Q ) ⊂ span(AQ⋆ ).

B. Special case b = 0

We now turn our attention to the proof of Lemma 2, which is related to the standard version of Oxx, initialized with the empty support. We first need to define the concept of "reachability" of a subset Q: Definition 6 A subset Q is said to be reachable by Oxx if there exists y ∈ span(AQ) such that Oxx with y as input selects atoms in Q during the first |Q| iterations.

The concept of reachability was first introduced in [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]. The authors showed that any subset Q with |Q| ≤ spark(A) -2 is reachable by OLS, see [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Lemma 3]. On the other hand, they emphasized that there exist dictionaries for which some subsets Q can never be reached by OMP, see [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Example 1]. This scenario does however not occur for the dictionary defined in [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF] as stated in the next lemma: Lemma 9 Let A be defined as in [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF] with b = 0. Then any subset Q with |Q| = g < k is reachable by Oxx.

The proof of this result is reported to Appendix D. We are now ready to prove Lemma 2:

Proof: (Lemma 2) Consider the dictionary A defined in [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF] with b = 0. Let Q be a subset of cardinality g, arbitrarily chosen (say, the first g atoms of the dictionary). We will exhibit a subset Q ⋆ ⊃ Q for which the result of Lemma 2 holds.

We first apply Lemma 9: there exists an input y1 ∈ span(AQ) for which Oxx selects all atoms in Q during the first g iterations. Then, we apply Lemma 8: there exists a vector ỹ2 having two (kg)-term representations in the projected dictionary C\Q . We will denote their respective supports by Q1 and Q2 with Q1 ∩Q2 = ∅. We then define y2 as in the proof of the converse of Theorem 3.

By virtue of [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Lemma 15], Oxx with y = y1 + εy2 as input selects the same atoms (i.e., Q) as with y1 as input during the first g iterations as long as ε > 0 is sufficiently small. Moreover, defining Q ⋆ as in [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF] and applying the same reasoning as in the proof of the converse part of Theorem 3, we have that y ∈ span(AQ⋆ ) and is such that Oxx selects a bad atom at iteration g + 1.

IX. QUASI-TIGHTNESS OF [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF] FOR OMPQ In this section, we provide an instance of dictionary such that δ k+b+1 = 1/ √ kg and OxxQ fails at the first iteration. Our dictionary construction is along the same lines as [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]Th. 3.2].

Proof: (Lemma 1) We first consider the case g ≤ k -2. Let us define A ∈ R (k+b+1)×(k+b+1) as

A = I g+b 0 (g+b)×(k-g+1) 0 (k-g+1)×(g+b) M (38)
where

M       1 k-g I k-g
. . . On the other hand, there exist Q ⋆ and Q satisfying the hypotheses of Lemma 1 and such that OxxQ fails at the first iteration for some representation y = Ax ⋆ indexed by Q ⋆ . Let us set Q = {1, . . . , g + b}, Q ⋆ = {b + 1, . . . , k + b} in such a way that there is only one wrong atom outside of Q ∪ Q ⋆ , namely the last atom. We set Since k + b + 1 / ∈ Q ⋆ , a failure situation as in (6) occurs. The special case g = k -1 leads to the degenerate situation δ k+b+1 = 1 in Lemma 1. This case is handled by proposing a dictionary having two identical columns. We define A as in [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF] with

x ⋆ i = 1 if i ∈ Q ⋆ 0 otherwise.
M = 1 1 0 0 ∈ R 2×2 .

Theorem 2 [

 2 µ-based uniform condition for Oxx[START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF] Cor. 3.6],[START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF] Th. 3.1]] If[START_REF] Von Borries | Compressed sensing using prior information[END_REF] is satisfied, then Oxx succeeds in recovering any k-term representation. Conversely, there exist an instance of dictionary A and a k-term representation for which: (i) µ = 1 2k-1 ; (ii) Oxx selects a wrong atom at the first iteration.In this paper, we provide a coherence-based sufficient and worstcase necessary condition for the success of OxxQ. Our result generalizes Theorem 2 as follows: Theorem 3 (µ-based uniform condition for OxxQ) Consider a kterm representation y = Ax ⋆ and a subset Q such that |Q ⋆ ∩Q| = g and | Q⋆ ∩ Q| = b. If µ < 1 2k-g+b-1 holds, then OxxQ recovers x ⋆ in kg iterations. Conversely, there exist a dictionary A and a kterm representation y such that: (i) µ = 1 2k-g+b-1 ; (ii) OxxQ with y as input selects a bad atom at the first iteration.

  2.1], [18, Th. 3.1] and [22, Th. 3.1]: Theorem 4 (Truncated NSP) Assume that spark(A) > k + b and let θp(k, g, b)

  2.4], we have that (1) is sufficient for spark(A) > 2kg + b > k + b. Applying successively Theorems 7 and 6, we have θp(k, g, b) < 1 ∀p ∈ [0, 1].

1 2k-

 1 g+b-1 and such that θp(k, g, b) = 1 ∀p ∈ [0, 1].

  On the one hand, it can be seen that the eigenvalues of the Gram matrix G = A T A are λ = 1 with multiplicity k + b -1 and λ = 1 ± 1 √ k-g with multiplicity 1. Hence, δ k+b+1 = 1 √ k-g .

  With this particular choice, we have y = AQ⋆ 1 k and:C{1,...,k+b+1}\Q = A {1,...,k+b+1}\Q = 0 g+b×k-g+1 M , r Q = CQ ⋆ \Q 1 k-g = ci, r Q = 1 ∀i ≥ g + b + 1.

We note however that, unlike the convex ℓ 1 problem, reaching the global minimum of ℓp problems is not guaranteed in practice.

We have adapted the formulation of the condition derived in[START_REF] Friedlander | Recovering compressively sampled signals using partial support information[END_REF] to the particular setup and notations considered in this paper.

We have obviously δ k+b+1 = 1 since that the dictionary has two identical columns. OxxQ then trivially fails with y, Q ⋆ and Q defined as above.

X. CONCLUSIONS

We derived a new sufficient and worst-case necessary condition, µ < 1 2k-g+b-1 , for the success of OMP, OLS and some procedures based on ℓp relaxation. Our result both applies to the context of sparse representations with support side information, and to the analysis of greedy algorithms at intermediate iterations. Our condition relaxes the well-known coherence-based result µ < 1 2k-1 derived in the noninformed setup by several authors, see e.g., [START_REF] Gribonval | Sparse representations in unions of bases[END_REF], [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF], [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF]. Moreover, it is shown to be complementary with some similar conditions based on restricted isometry constants [START_REF] Friedlander | Recovering compressively sampled signals using partial support information[END_REF], [START_REF] Karahanoglu | On the theoretical analysis of orthogonal matching pursuit with termination based on the residue[END_REF].

We also carried out a fine analysis of some relations existing between conditions of success for OMP/OLS and ℓp-relaxed procedures in the informed setup. We showed that the truncated NSP, characterizing the success of ℓp-relaxed procedures in the informed setup, enjoys some ordering property. Moreover, we established a direct implication between the ERC-OMP derived in [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF] and the truncated NSP for the informed ℓ1-relaxed problem.

APPENDIX A PROOF OF THE RESULTS OF SECTION V

This section contains the proofs of Lemmas 3 and 4 together with some useful technical lemmas.

Lemma 10 Assume A satisfies the P-RIP(δ 2,l , δ2,l ) and let

Then, we have

.

Proof: By definition of δ2,l and δ 2,l we must have for all R, S with |R| = l, |S| = 2 and R ∩ S = ∅:

where λmax(M) (resp. λmin(M)) denotes the largest (resp. smallest) eigenvalue of M and we used the short-hand notation à = ÃR . Moreover, if S = {i, j}, it is easy to check that the eigenvalues of ÃT S ÃS can be expressed as

where

Using (39)-( 40), we thus obtain ∀i, j / ∈ R:

Now, this inequality also holds if i ∈ R or j ∈ R since the right hand-side of ( 41) is then equal to zero. The result then follows from the definition of µ OM P l .

Lemma 11 Let |R|=l and

Proof: Let us use the short-hand notation à = ÃR . We have:

Using Lemmas 10 and 11, we can now prove Lemmas 3 and 4:

Proof: (Lemma 3) ∀ i / ∈ Q ⋆ , the following inequalities hold:

,

where the first inequality follows from the equivalence of norms; the second from RIC properties (see [START_REF] Needell | CoSaMP: Iterative signal recovery from incomplete and inaccurate samples[END_REF]Prop. 3.1]); the third from Lemma 11 and the fourth from Lemma 10.

Proof: (Lemma 4) First, notice that A satisfies the P-RIP(δ q,0 , δq,0) ∀ q with δq,0 = δ q,0 = (q -1)µ, see e.g., [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF]Lemma 2.3]. Let R, S with |R| = l, |S| = q, R ∩ S = ∅. Then, ( 24) is a consequence of the following inequalities:

Lower bound ( 25) is derived by noticing that

and

where inequality [START_REF] Candes | The restricted isometry property and its implications for compressed sensing[END_REF] follows from standard relationships between the RIC properties of A and transforms of A, and 43) is a consequence of Lemma 11.

APPENDIX B PROOF OF THE RESULTS OF SECTION VI

Proof: (Lemma 5) The proof is recursive. Obviously, the result holds for l = 0 since µ OLS 0 = µ.

Let R with |R| = l ≥ 1 and assume that the result holds for l -1.

Let us then consider the case where j / ∈ R and j ′ / ∈ R. First, from the assumption µ < 1/l, we have that A R∪{j} is full column rank as a family of l + 1 atoms [23, Lemma 2.3]. Let us then consider S such that R = S ∪ {i} with |S| = l -1 and let us apply [20, Lemma 5]. We obtain the following orthogonal decomposition:

Exploiting this decomposition, we can thus write:

Taking the absolute value of both sides and majorizing the inner products on the right-hand side by µ OLS l-1 , we obtain:

where the last inequality follows from the fact that ( 30) is assumed to hold for l -1. This proves the result for |R| = l and completes the recursion.

APPENDIX C PROOF OF THE RESULTS OF SECTION VII

Before proceeding to the proofs of Lemmas 6 and 7, we emphasize that spark(A) > k + b and v ∈ ker0 (A) are sufficient conditions for v Q ⋆ ∪Q not to be equal to zero because Q ⋆ ∪ Q is composed of k + b elements. This implies that (13), [START_REF] Zhang | Sparse recovery with orthogonal matching pursuit under RIP[END_REF] and [START_REF] Liu | The orthogonal super greedy algorithm and applications in compressed sensing[END_REF] are always well-defined, as their denominators are nonzero.

Proof: (Lemma 6) As an initial remark, let us mention that, for any v ∈ ker0(A), a couple (Q ⋆ , Q) maximizing the right-hand side of (31) should be such that v Q ⋆ \Q (resp. v Q ⋆ ∪Q ) collects the elements of v with the largest (resp. smallest) amplitudes, because t → t p is an increasing function on R + . In the rest of the proof, we will therefore assume that Q ⋆ and Q satisfy this requirement.

Let

Taking our initial remark into account, θp(k, g, b, v) can be expressed as

. which can also be rewritten as

Now, in [24, Th. 5], it is proved that (44) holds for any vector w whose kg first elements have the largest magnitudes. Observing that w satisfies the latter condition, we obtain the result.

Proof: (Lemma 7) For any v ∈ ker0(A), we have

Applying the orthogonal projector onto span(AQ) ⊥ to both sides, we obtain

Let us note that AQ⋆∪Q is full-rank by hypothesis and, by virtue of [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Cor. 3], ÃQ ⋆ \Q is therefore also a full-rank matrix. This leads to

Taking the ℓ1 norm of both sides and using the definition of the ℓ1 matrix induced norm, we have

The result then follows from the fact that ãi = 0m ∀i ∈ Q.

APPENDIX D PROOF OF THE RESULTS OF SECTION VIII

In this appendix, we provide a proof of Lemmas 8 and 9. We first need to prove the following technical lemma: Lemma 12 Let A be defined as in [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]. Then, we have for all R with |R| < 2kg + b and i, j / ∈ R, i = j:

Proof: First recall that spark(A) = 2kg + b (see section VIII). Therefore, AR is full rank when |R| < 2kg + b and ãR i reads

Using this expression, we have

Taking into account that the inner product between any pair of atoms is equal to -µ by definition of G = A T A, we obtain the result.

Proof: (Lemma 8) Using Lemma 12 for |R| = g + b, we notice that CQ \Q = β ÃQ \Q for some β > 0 since ãQ i does not depend on i. Moreover, ãQ i = 0m (and therefore

since 1 2k-g+b belongs to the null-space of A.

Let us partition the elements of v = 1 2k-2g into two subsets Q1 ∪Q2 with Q1 ∩Q2 = ∅ and |Q1| = |Q2| = k-g, and define ỹ CQ 1 \Q 1 k-g . According to (48), ỹ rereads -CQ 2 \Q 1 k-g , therefore ỹ has two (kg)-sparse representations with disjoint supports in C\Q .

Proof: (Lemma 9) Let us first recall that b is set to 0 in this lemma. We prove a result slightly more general than the statement of Lemma 9: for the dictionary defined as in [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF], any subset R with p |R| ≤ 2kg -2 can be reached by Oxx. Lemma 9 corresponds to the case p = g (p ≤ 2kg -2 is always satisfied as long as g < k).

The result is true for OLS by virtue of [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Lemma 3] which states that any subset R of an arbitrary dictionary A is reachable as long as |R| ≤ spark(A) -2. In particular, the latter condition is verified by the dictionary A and the subset R considered here since spark(A) = 2kg and |R| ≤ 2kg -2 by hypothesis.

We prove hereafter that the result is also true for OMP. Without loss of generality, we assume that the elements of R correspond to the first p atoms of A (the analysis performed hereafter remains valid for any other support R of cardinality p since the content of the Gram matrix A T R AR is constant whatever the support R: see ( 36)). For arbitrary values of ε2, . . . , εp > 0, we define the following recursive construction:

• y1 = a1, • yp+1 = yp + εp+1ap+1 (yp+1 implicitly depends on ε2, . . . , εp+1). We show by recursion that for all p ∈ {1, . . . , 2kg -2}, there exist ε2, . . . , εp > 0 such that OMP with the dictionary defined as in [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF] and yp as input successively selects a1, . . . , ap during the first p iterations. In particular, the selection rule (4) always yields a unique maximum.

The statement is obviously true for y1 = a1. Assume that it is true for yp (p < 2kg -2) with some ε2, . . . , εp > 0 (these parameters will remain fixed in the following). According to [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]Lemma 15], there exists εp+1 > 0 such that OMP with yp+1 = yp +εp+1ap+1 as input selects the same atoms as with yp during the first p iterations, i.e., a1, . . . , ap are successively chosen. At iteration p, the current active set reads R = {1, . . . , p} and the corresponding residual takes the form

Thus, ap+1 is chosen at iteration p + 1 if and only if

Now, |R| = p < 2kg by hypothesis, then Lemma 12 applies (we remind the reader that we assume that b = 0). Using ( 46)-(47), it is easy to see that (49) is equivalent to

Since µ = 1 2k-g-1 < 1 p+1 < 1 p-1 , we have 1 -(p -1)µ > 0. Then, [23, Lemma 2.3] and 1p 2 = p yield:

Using the fact that µ < 1/(p + 1), it follows that:

which proves that the condition (50), and then (49) is met. OMP therefore recovers the subset R ∪ {p + 1} = {1, . . . , p + 1}.