Mehdi Latif

Jérôme Idier

Thomas Carlier

Simon Stute

Multi-class maximum likelihood expectation-maximization list-mode image reconstruction

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

In nuclear imaging, some scanner prototypes based on Compton imaging allow the detection of different types of events. For instance,

• The MACACO camera [START_REF] Muñoz | Performance evaluation of MACACO: a multilayer Compton camera[END_REF] is a Compton telescope with three layers of plane detectors having different energy resolutions. Photon (or gamma) interactions in different combinations of layers lead to events with different spatial resolution properties.

• The WGI preclinical prototype [START_REF] Tashima | 3D Compton image reconstruction method for whole gamma imaging[END_REF] has a full-ring geometry with a scatterer detector close to the scanned subject and an absorber further away. In addition to Compton imaging, WGI performs positron emission tomography (PET) imaging by detecting annihilation photons in coincidence. With radio-isotopes emitting nearly simultaneously a positron and a (third) gamma, 3-gamma (3γ) imaging can be performed [START_REF] Mohammadi | Feasibility of triple gamma ray imaging of 10 C for range verification in ion therapy[END_REF]. The emission point can be localized near the intersection of the Compton cone-of-response (COR) of the third gamma and the PET line-of-response (LOR) of the annihilation photons.

• The XEMIS2 preclinical prototype [START_REF] Gallego Manzano | XEMIS2: A liquid xenon detector for small animal medical imaging[END_REF] is a Compton telescope using liquid xenon as a single continuous detection medium. It has been specifically designed for 3γ imaging.

All scanners described above detect distinct types of events during a single acquisition. To avoid the widespread term type, we call them classes of events hereafter.

In terms of image reconstruction, the WGI prototype separately considers Compton or PET image reconstructions [START_REF] Tashima | 3D Compton image reconstruction method for whole gamma imaging[END_REF]. With 3γ, a single back-projection is performed [START_REF] Mohammadi | Feasibility of triple gamma ray imaging of 10 C for range verification in ion therapy[END_REF]. For XEMIS2, a method has been proposed to transform 3γ data into TOF PET data in order to use conventional PET reconstruction methods [START_REF] Giovagnoli | A Pseudo-TOF Image Reconstruction Approach for Three-Gamma Small Animal Imaging[END_REF]. Only 3γ data were used while single or double γ events were discarded. For MACACO, all event classes were considered together in the reconstruction process. An extension of the MLEM algorithm was proposed lacking a theoretical derivation, where the update term is the sum of contributions from each event class and weighted by the sum of the sensitivities of each class [START_REF] Roser | Joint image reconstruction algorithm in Compton cameras[END_REF].

Here, we first introduce a theoretical framework for the reconstruction of a single activity map from multi-class events.

In particular, we derive a proper list-mode MLEM algorithm suited to the multi-class case. In a second stage, we consider 3γ imaging based on XEMIS2 as a specific case. As a preliminary step towards effective multi-class reconstruction, we generate a sensitivity map for each class using a dedicated Monte Carlo simulator.

Derivation of the multi-class list-mode MLEM

In what follows, λ λ λ := {λ j } j∈ 1,J denotes a voxelized density of events, where each λ j represents the expected number of emitted events from the jth voxel. As mentioned earlier, we consider a multi-class data approach, where the available information about λ λ λ arises from several distinct datasets.

Multi-class data

Let y y y := {y y y n } n∈ 1,N be the set of N collected data. It is composed of K ∈ N * disjoint classes of physically independent events. A class refers to a specific type of event that can be detected and identified. We assume that each observed event can be attributed to one class, so that the set y y y can be expressed as the union of K independent classes:

y y y := K k=1 y y y k n n∈ 1,N k , N = K ∑ k=1 N k , (1)
where each y y y k n ∈ R d k is a measurement vector containing photon interaction coordinates and deposited energies for the nth event.

Multi-class likelihood

We assume that within each class k, the events y y y k n n∈ 1,N k are independent and identically distributed (iid) according to the probability density function of sampling y y y k from any point of the λ λ λ distribution:

y y y k n ∼ p k y y y k |λ λ λ ∀k ∈ 1, K . (2)
The log-likelihood function then reads:

l(λ λ λ |y y y) := K ∑ k=1 N k ∑ n=1 ln p k y y y k n |λ λ λ = K ∑ k=1 l k λ λ λ |y y y k (3)
where l k (λ λ λ |y y y k ) denotes the log-likelihood of the kth class. Under standard Poisson assumptions, we can decompose l k λ λ λ |y y y k as

l k λ λ λ |y y y k := N k ∑ n=1 ln J ∑ j=1 a k n j λ j -N k ln J ∑ j=1 λ j s k j , (4)
where a k n j := A k j y y y k n defines an element of the system matrix specific to class k and voxel j, expressed as a continuous function of the nth measurement vector, and s k j denotes the sensitivity of voxel j for class k:

s k j := v∈Ω k A k j (v) dv ∀ j ∈ 1, J , k ∈ 1, K , (5)
where Ω k denotes the continuous detection domain related to the kth class.

Multi-class list-mode MLEM

To perform the estimation of λ λ λ , we must extend the list-mode MLEM algorithm [START_REF] Parra | List-mode likelihood: EM algorithm and image quality estimation demonstrated on 2-D PET[END_REF][START_REF] Wilderman | List-mode maximum likelihood reconstruction of Compton scatter camera images in nuclear medicine[END_REF] to simultaneously account for the K classes. The result is the following update equation:

λ (t+1) j := λ (t) j × 1 ∑ k s k j K ∑ k=1 N k ∑ n=1 a k n j 1 ∑ j ′ a k n j ′ λ (t) j ′ + ε k n , (6)
where ε k n can be used to modelled random and scatter detections for each class. For a complete derivation of (6), we first need to express the log-likelihood of the complete dataset, along the same lines as in [START_REF] Parra | List-mode likelihood: EM algorithm and image quality estimation demonstrated on 2-D PET[END_REF]. In the multi-class framework, a specific property is that the latter is a sum over the K classes. The update equation ( 6) is then obtained from (3) within the model of the EM algorithm [START_REF] Dempster | Maximum Likelihood from Incomplete Data Via the EM Algorithm[END_REF] and allowing the decomposition of the auxiliary function Q(λ λ λ |λ λ λ (t) ) into a sum of lower bound approximation on the likelihood for each class:

Q k λ λ λ |λ λ λ (t) := E z z z k |y y y k ,λ λ λ (t) ln p k (y y y k , z z z k | λ λ λ ) ∀k ∈ 1, K (7)
where z z z k denotes the latent data vector.

3 Application to three-gamma imaging

XEMIS2 camera

The above results can be applied to XEMIS2, in the context of 3γ imaging. This imaging modality makes use of an isotope that quasi-simultaneously emits a positron (leading to the annihilation in two photons of 511 keV) and a socalled third photon. In our application, scandium-44 ( 44 Sc) is used where the third photon is isotropically emitted with an energy of 1157 keV. The XEMIS2 camera is a preclinical prototype based on a continuous cylindrical liquid xenon (LXe) detector [START_REF] Gallego Manzano | XEMIS2: A liquid xenon detector for small animal medical imaging[END_REF]. The axial length of the active zone is 24 cm with an internal (resp. external) radius of 7 cm (resp. 19 cm). The design of the camera only allows to operate at low count rates resulting in low random rates. The energy resolution at 511 keV is 9% (FWHM) which would allowed to remove most of scattered photon using a tight energy window.

Classes of detections with XEMIS2

Based on the energy of the detected photons, K = 5 classes of events are possible:

• 1γ 511 COR events correspond to the detection of a single annihilation photon. Its emission position belongs to a COR with a half-opening angle β ∈ [0, π] given by the Compton scattering angle formula:

β := acos 1 - m e c 2 E 1 E 0 (E 0 -E 1 ) (8)
where m e c 2 is the mass energy of an electron, E 0 is the total energy of the incident photon, i.e. E 0 = 511 keV for this class, and E 1 is the energy deposited in the detection medium during the scattering effect.

• 1γ 1157 COR events correspond to the detection of the third photon. Akin to the former case, it is possible to define a COR using eq. ( 8) with E 0 = 1157 keV.

• 2γ LOR events correspond to the detection of both annihilation photons. As standard PET imaging, the source of annihilation belongs to a LOR.

• 2γ COR events correspond to the detection of a single annihilation photon and the third photon (combination of 1γ 511 COR and 1γ 1157 COR ). The origin of the decay belongs to the intersection of the two CORs.

• 3γ events correspond to the independent combination of a 2γ LOR event with a 1γ 1157 COR one. The imaging procedures currently available for XEMIS2 (e.g., [START_REF] Giovagnoli | A Pseudo-TOF Image Reconstruction Approach for Three-Gamma Small Animal Imaging[END_REF]) only exploit 3γ events. The other classes correspond to partial detections. Yet, they could bring additional information to the image reconstruction process, and thus lead to estimated activity maps λ λ λ of enhanced quality using a suited multi-class reconstruction algorithm such as eq. ( 6).

Monte Carlo simulator

Multi-class image reconstruction can be first assessed through simulation. To this end, a Monte Carlo simulator was implemented to generate 3γ emissions and their detection in a continuous medium, according to the geometry of XEMIS2.

It is based on a ray-tracing method, allowing us to simulate emissions from voxels within the field-ov-view (FOV) by randomly selecting three directional vectors to define the positron range, the trajectories of the annihilation photons along the LOR, and the third photon. Once a photon reaches the LXe zone, new random draws were performed to simulate the mean free path and the radiation-matter interactions that may occur, such as Compton scattering, Rayleigh scattering and photoelectric effect. Cross-section values were extracted from the XCOM database [START_REF]XCOM: Photon Cross Sections Database[END_REF]. We neglect the Rayleigh effect since its normalized cross-section is strictly lower than 10% over the entire energy range of interest i.e. for energies lower than 1157 keV. The resulting code, named Pollux, is open-source and freely available at mlatif/tep3g-pollux. Fig. 1 presents examples of detection for each event class obtained with Pollux.

Sensitivity computation of XEMIS2

The mathematical expression of the voxelwise sensitivity (5) involves multi-integrals that cannot be evaluated analytically. We thus used Pollux to generate approximate maps of the sensitivity for an empty FOV. To this end, the whole FOV was discretized into 19 × 19 × 24 voxels of 5 × 5 × 10 mm 3 . M = 2 × 10 5 3γ emission points were uniformly generated in each voxel and the event class was recorded for each emission. Fig. 2 displays the sensitivity map obtained for each class for a transaxial cross-section at the center of the FOV, while Fig. 3 shows the same maps along the axial direction. The sensitivity distributions of the different classes are spatially heterogeneous, and tend to complement each other, which is an interesting observation in the perspective of multi-class reconstruction. For instance, the sensitivity maps of classes 3γ and 2γ LOR are maximal at the center of the FOV, while the trend is reversed for the sensitivity of 1γ 511 COR and 1γ 1157 COR . Let us remark that non-detected events can be gathered in a sixth class 0γ, whose "sensitivity map" (as displayed in Fig. 3) can rather be understood as a non-sensitivity one.

Table 1 displays the distribution of detected events by class, which represent 69% of the emissions that led to the detection of at least one photon. We note that approximately 13% of the emissions lead to the detection of 3γ , which is small compared to the partially detected events, totalizing almost 87% of all cases. Obviously, we expect the most informative events to be in the 3γ class, and the 2γ LOR events to be more informative than the other events on CORs. However, 3γ and 2γ LOR classes represent about a quarter of the detected events.

Class

Discussion and perspectives

Our contribution focuses at designing an image reconstruction process for specific Compton imaging systems able to detect multiple classes of events, in the field of nuclear imaging. First, we introduced a theoretical framework for the reconstruction of a single activity map from multi-class events, from which we deduced the suited list-mode MLEM update equation. The latter is potentially applicable to several existing prototypes of Compton imaging systems, such as MACACO, WGI, and XEMIS2. Let us also mention that the multi-class version of MLEM could be extended to cases where a regularization term is considered, as proposed in [START_REF] Pierro | A modified expectation maximization algorithm for penalized likelihood estimation in emission tomography[END_REF], for instance. In a second part, we made a step further towards an application to XEMIS2, which is a preclinical prototype of a Compton telescope for 3γ imaging. In the XEMIS2 case, four distinct classes of partial detections coexist with the 3γ class. Using a dedicated Monte Carlo simulator, we determined a sensitivity map specific to each class, which is prerequisite to implement our multi-class version of MLEM. Besides, the obtained sensitivity maps clearly indicate that partial detections are far more frequent than perfect detections. Moreover, we noticed that some partial detection classes spatially complement the 3γ class. On the one hand, each partial detection is less informative than a full detection, but on the other hand, partial detections are more frequent. An interesting task will be to determine the amount of information brought by each class. This could be formally achieved by expressing the Fisher Information Matrix in the multi-class case, as an extension of the standard framework of [START_REF] Parra | List-mode likelihood: EM algorithm and image quality estimation demonstrated on 2-D PET[END_REF]. We could then anticipate which classes are worth to be incorporated, despite the increased computational cost. The next important step of our project will be the implementation of the proposed multi-class MLEM algorithm on the CASToR (Customizable and Advanced Software for Tomographic Reconstruction) platform [START_REF] Merlin | CASToR: a generic data organization and processing code framework for multi-modal and multi-dimensional tomographic reconstruction[END_REF]. Based on Pollux simulations, we are currently working at allowing continuous measurements and COR events within the CASToR framework. We also plan to implement a more realistic simulator using the GEANT4 toolkit [START_REF] Agostinelli | Geant4-a simulation toolkit[END_REF].

Figure 1 :

 1 Figure 1: Examples of detection obtained with the Monte Carlo simulator dedicated to XEMIS2. The LXe continuous detection medium is represented by the hollow cylinder, and the studied image by the box in the center. Blue LORs and CORs are obtained from annihilation photon(s), and red CORs from the third photon.

Figure 2 :

 2 Figure 2: A cross-section of the sensitivity maps (%) for each class of event at z = 0.

Figure 3 :

 3 Figure 3: Mean sensitivity (%) along the axial direction for each class of event. The 0γ curve corresponds to the mean distribution of non-detected emissions.

Table 1 :

 1 Classification of detected events (≈ 69%) for emissions uniformly distributed within the set voxels in the discretized FOV.

	1γ 511 COR 1γ 1157 COR 2γ LOR 2γ COR 3γ
	% of detection 22.86 32.07 10.2 21.67 13.2

Acknowledgments

The authors thank Nicolas Beaupère for valuable discussions about the XEMIS2 detector and events processing. This work has been partly funded by the NExT Junior Talent project TRAC through the French "Programme d'Investissement Avenir".


C Herzet

A Drémeau

Member, IEEE C Soussen

Relaxed Recovery Conditions for OMP/OLS by Exploiting both Coherence and Decay

Keywords: Orthogonal matching pursuit, orthogonal leastsquares, mutual coherence, exact recovery, sparse decaying representations

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 µ < 1/(2k -1) (where µ 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 µ < 1/k for strongly decaying sparse signals. Finally, in the noiseless setting, we prove that the proposed conditions, in particular the bound µ < 1/k, are the tightest achievable guarantees based on mutual coherence.

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) [START_REF] Pati | Orthogonal matching pursuit: recursive function approximation with applications to wavelet decomposition[END_REF] and orthogonal least squares 1 (OLS) [START_REF] Chen | Orthogonal least squares methods and their application to non-linear system identification[END_REF], [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF]. 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 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 Franc ¸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. 1 The OLS algorithm is also known as forward selection [START_REF] Miller | Subset Selection in Regression, Second Editon[END_REF], Order Recursive Matching Pursuit (ORMP) [START_REF] Cotter | Forward sequential algorithms for best basis selection[END_REF], pure Orthogonal Matching Pursuit (OMP) [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF] and Optimized Orthogonal Matching Pursuit (OOMP) [START_REF] Rebollo-Neira | Optimized orthogonal matching pursuit approach[END_REF] in the literature.

irrespective of the magnitude of the nonzero coefficients. This type of analyses was carried out for OMP in [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 also adapted to several extensions of OMP in [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF], [START_REF] Needell | Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[END_REF], [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 (under different names [START_REF] Blumensath | On the difference between orthogonal matching pursuit and orthogonal least squares[END_REF]), uniform exact recovery analyses of OLS have only appeared very recently, see [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF], [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF], [START_REF] Herzet | Exact recovery conditions for sparse representations with partial support information[END_REF].

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 [START_REF] Eldar | Average case analysis of multichannel sparse recovery using convex relaxation[END_REF], [START_REF] Davies | Rank awareness in joint sparse recovery[END_REF]. In particular, in [START_REF] Sturm | Sparse vector distributions and recovery from compressed sensing[END_REF] 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 analyses2 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) [START_REF] Gribonval | Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms[END_REF]. 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., [START_REF] Sturm | Sparse vector distributions and recovery from compressed sensing[END_REF], [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF]- [START_REF] Blanchard | Conjugate gradient iterative hard thresholding: Observed noise stability for compressed sensing[END_REF]. 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 can be observed in many applications (see [START_REF] Mallat | A wavelet tour of signal processing[END_REF] and [START_REF] Vincent | From blind to guided audio source separation: How models and side information can improve the separation of sound[END_REF] 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 [START_REF] Davenport | Analysis of orthogonal matching pursuit using the restricted isometry property[END_REF], [START_REF] Jin | Performance limits of matching pursuit algorithms[END_REF]- [START_REF] Ehler | Quasi-linear compressed sensing[END_REF]. In [START_REF] Jin | Performance limits of matching pursuit algorithms[END_REF] 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 [START_REF] Davenport | Analysis of orthogonal matching pursuit using the restricted isometry property[END_REF], 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 [START_REF] Ding | Performance analysis of orthogonal matching pursuit under general perturbations[END_REF], 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 [START_REF] Ehler | Quasi-linear compressed sensing[END_REF].

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 µ < 1/(2k -1) is satisfied but the best-known uniform RIC conditions [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF], [START_REF] Chang | An improved RIP-based performance guarantee for sparse signal recovery via orthogonal matching pursuit[END_REF] 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., [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]. 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 ∈ R m obey the following model:

y = Ax + w, (1)
Algorithm 1 Oxx in k steps inputs: y, A init: Q = ∅ while Card(Q) < k do Q = Q ∪ {j} where j ∈ arg max i / ∈Q | a i , r Q | (OMP) arg min i / ∈Q r Q∪{i} 2 (OLS)
and r Q is the data residual associated to active set Q end while ouput: Q with Card(Q) = k where A ∈ R m×n is a known dictionary, x ∈ R n is an unknown vector and w ∈ R m is some additive noise with w 2 ≤ . 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 ⊆ {1, . . . , n} matches the support of the k largest elements of x. We have summarized the main recursions of Oxx in Algorithm 1. •, • 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 / ∈ Q is included to the estimated support [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], [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]. 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 [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF], [START_REF] Zhang | Sparse recovery with orthogonal matching pursuit under RIP[END_REF], 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 ( = 0) and x is k-sparse with support Q (x i = 0 ⇔ i ∈ 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 ( > 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.

A. k-step Analysis in the Noiseless Setup

The first thoughtful "k-step" analysis of OMP is due to Tropp in [START_REF] Tropp | Greed is good: algorithmic results for sparse approximation[END_REF]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

µ < 1 2k -1 , (2)
where µ max i =j |a T i a j | is the mutual coherence of A, ensures the success of OMP. The derivation of similar conditions 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], [START_REF] Herzet | Exact recovery conditions for sparse representations with partial support information[END_REF].

Condition (2) is uniform, that is Oxx can recover any ksparse vector irrespective of the amplitude of the nonzero coefficients when (2) is satisfied. On the other hand, it was shown in [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF]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 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 [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF] is "flat", that is such that

x i = constant ∀ i ∈ Q . (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 x is a k-sparse vector whose nonzero amplitudes are not all equal, there exists some µ > 1 2k-1 such that Oxx recovers Q in k steps for any dictionary with µ < µ .

Interestingly, as mentioned in the introduction, it has been stated in many pieces of research (and accepted as a "folk knowledge" [START_REF] Sturm | Sparse vector distributions and recovery from compressed sensing[END_REF]) that sparse vectors with nonzero coefficients of equal magnitude correspond to the most difficult case for many reconstruction algorithms, see e.g., [START_REF] Dai | Subspace pursuit for compressive sensing signal reconstruction[END_REF]- [START_REF] Blanchard | Conjugate gradient iterative hard thresholding: Observed noise stability for compressed sensing[END_REF]. 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 µ < 1 2k-1 always exists as soon as the coefficients of x exhibit some decay.

Unfortunately, the proof of Theorem 1 does not provide an optimal value for µ (as a function of the rate of decay). In fact, a precise characterization of µ 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, . . . , k}, (4)
and

|x 1 | ≥ |x 2 | ≥ . . . ≥ |x k | > 0. (5) Theorem 2 If µ < 1 k , (6)
and

|x i | > 2µ(k -i) 1 -iµ |x i+1 | ∀i ∈ {1, . . . , k -1}, (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 A with µ = 1 k such that for all k-sparse vectors x supported by Q , Oxx selects a wrong atom during the first k iterations.

• For all j ∈ {1, . . . , k -1}, there exists a vector x (j) and a dictionary A of mutual coherence µ < 1 k , for which the inequalities (7) hold for i = j, and become an equality for i = j, and such that Oxx with 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 righthand side of condition ( 7) is such that

2µ(k -i) 1 -iµ < 1, (8)
as soon as

µ < 1 2k -i .
Thus, by virtue of our convention ( 5), ( 8) implies that condition [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF] trivially holds for any i as soon as ( 2) is satisfied. We also note that 2µ(k-i)

1-iµ is a decreasing function of i for µ < 1/k. Hence, the rate of decay in [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF] becomes lower as i increases.

Condition [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF] can be equivalently expressed as

µ < µ i with µ i = |x i | |x i+1 | 2(k-i)+i |x i | |x i+1 | , ∀ i ∈ {1, . . . , k -1}.
The conditions of success stated in Theorem 2 can thus also be rephrased as:

µ < µ = min 1 k , µ 1 , . . . , µ k-1 .
It can be seen that possible values for µ range in the interval

[ 1 2k-1 , 1
k ] and depend on the decay of the nonzero coefficients of x. On the one hand, the smallest value for µ i occurs when

|x i | = |x i+1 |, in which case µ i = 1 2k-i . Hence, we recover the standard condition (2) when |x 1 | = |x 2 |. On the other hand, µ i > 1 k (and therefore µ = 1 k ) as soon as |x i | > 2|x i+1 |.
This leads to the following corollary:

Corollary 1 If µ < 1/k and |x i | > 2|x i+1 | ∀ i ∈ {1, . . . , k - 1}, then Oxx recovers Q in k steps.
A graphical representation of these considerations is provided in Fig. 1 for k = 5: the decay factor 2µ(k-i)

1-iµ appearing

1 2 3 4 0 1 2 3 µ = 1 2k µ = 0.7 k µ = 0.9 k µ = 1 k i |xi|/|xi+1| Fig. 1: Graphical representation of the decay constraints of Theorem 2 for different values of µ ∈ [ 1 2k , 1 k ], k = 5.
Plain curves: plot of the decay constraint 2µ(ki)/(1 -iµ) with respect to i. We note that because of our convention (5), we must have |x i |/|x i+1 | ≥ 1 ∀i: this region corresponds to the shaded gray area. in ( 7) is plotted as a function of

i for different values of µ ∈ [ 1 2k , 1 k ].
For a given µ, 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 µ = 1 2k < 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 [START_REF] Rebollo-Neira | Optimized orthogonal matching pursuit approach[END_REF]. On the other side, the region of success is restricted to vectors satisfying |x i |/|x i+1 | ≥ 2 when µ is close to 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 [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF]. 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µ ≥ k 2k-1 0.55. In contrast, the vectors drawn from the other distributions satisfy [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF] with some nonzero probability for any µ < 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 [START_REF] Sturm | Sparse vector distributions and recovery from compressed sensing[END_REF].

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 µ < 1 2k-1 cannot be improved for Basis Pursuit [START_REF] Chen | Atomic decomposition by Basis Pursuit[END_REF]. Indeed, it has been shown in [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF]Th. 3.1] that there exists a dictionary A with µ = such that Basis Pursuit leads to a wrong support detection. 5Now, it is well-known that tight conditions of success for Basis Pursuit only depend on the signed support of the sought sparse vector, see [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF], [START_REF] Plumbley | On polar polytopes and the recovery of sparse representations[END_REF]. The existence of a vector 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 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 µ < µ with µ ≤ 1 k . Said otherwise, the bound 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 Q , with cardinality Card(Q) = g ≥ 0, during the first g iterations, and one is interested in conditions guaranteeing the selection of atoms in Q \Q during the next k -g iterations.

2) Partial Support Recovery: the focus is on conditions ensuring the selection of p ≤ k elements of Q during 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 [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF] provided an instance of problem in which µ = 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 [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF], 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 [START_REF] Herzet | Exact recovery conditions for sparse representations with partial support information[END_REF]Th. 3

]: if Q Q is reached during the first Card(Q) = g iterations, then Oxx selects atoms in Q \Q during the next k -g iterations provided that µ < 1 2k -g -1 . (9)
Similar to the standard k-step analysis [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF], ( 9) was shown to be tight: there exist a k-sparse vector x with support Q , a subset Q Q with Card(Q) = g and a dictionary A with µ = 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 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 \Q = {1, 2, . . . , k -g}, (10)
with

|x 1 | ≥ |x 2 | ≥ . . . ≥ |x k-g | > 0. (11)
Theorem 3 jointly addresses both questions of successful termination and partial support recovery.

Theorem 3 Assume that Oxx has selected Q Q with Card(Q) = g during the first g iterations and let 1 ≤ p ≤ r ≤ k -g. • If µ < 1 k , (12)
and the largest magnitudes of the unselected atoms after iteration g satisfy

|x i | > 2µ(k -g -i) 1 -(g + i)µ |x i+1 | ∀i ∈ {1, . . . , p}, ( 13
)
then Oxx is guaranteed to select atoms in Q \Q until all the elements in {1, . . . , p} have been selected.

• If 1 k ≤ µ < 1 g + r , ( 14
)
and the largest magnitudes of the unselected atoms after iteration g satisfy

|x i | > 2µ(k -g -r) 1 -(g + r)µ |x i+1 | ∀i ∈ {1, . . . , p}, (15)
then Oxx is ensured to select atoms in Q \Q until all the elements in {1, . . . , 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 1 g+r = 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 µ involving the decay of the nonzero elements:

µ < µ = min 1 k , µ 1 , . . . , µ p , with µ i = |xi| |xi+1| 2(k -g -i) + (g + i) |xi| |xi+1| .
Depending on the decay of the nonzero coefficients, it can thus be seen that µ

∈ [ 1 2k-g-1 , 1 k ].
The strongest condition corresponds to [START_REF] Davenport | Analysis of orthogonal matching pursuit using the restricted isometry property[END_REF] 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, µ < 1 k , is obtained as soon as |xi| |xi+1| ≥ 2 ∀ i ∈ {1, . . . , k -g}. We thus recover a result similar to Corollary 1. Here, the decay constraints only apply to the elements in Q \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 ≤ 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 [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF] or [START_REF] Eldar | Average case analysis of multichannel sparse recovery using convex relaxation[END_REF]). This leads to the following corollary for partial support recovery:

Corollary 2 Let p ∈ {1, . . . , k}. If µ < 1
p and the p + 1 largest coefficients of x exhibit a sufficient decay (specified by [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF] or (15)), then Oxx selects atoms in Q during the first p iterations.

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

Corollary 3 Let p ∈ {1, . . . , k}. If µ < 1 k and the p + 1 largest magnitudes in x exhibit a sufficient decay (13), then Oxx selects atoms in Q until the p largest components of x have been selected.

Note that Corollary 3 does not state that Oxx will select the p largest components of 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 x is not exactly k-sparse but rather compressible and possibly non-sparse. Furthermore, the observations are corrupted by some additive noise (w = 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 2 -norm, that is w 2 ≤ . In the following, a signal x will be referred to as "k-compressible" as soon as the sum of the absolute values of k entries of x is large with respect to the remaining entries. Denoting by Q {1, . . . , n}\Q the complementary subset, the k-compressible assumption reads x Q 1

x Q 1 for some subset Q of cardinality k. x Q and x Q shall be thought of as the head and tail of the signal x, respectively.

Let us first consider the k-sparse setup (x Q = 0 n-k ) with noisy observations ( > 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 x [36]- [START_REF] Wu | The exact support recovery of sparse signals with noise via orthogonal matching pursuit[END_REF], 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. [START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF]Th. 5.1] (also rediscovered in [39, Th. 1]), stating that OMP succeeds if

µ < 1 2k -1 , ( 16
)
|x i | > 2 1 -(2k -1)µ , ∀i ∈ {1, . . . , k}. (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 kcompressible setting. As in subsection II-A, we assume that the elements of x Q satisfy (4)- [START_REF] Rebollo-Neira | Optimized orthogonal matching pursuit approach[END_REF].

Theorem 4 If µ < 1 2k -1 , (18)
and

|x i | > 2( x Q 1 + ) 1 -(2k -i)µ ∀i ∈ {1, . . . , k}, (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 1 -norm of x Q . Moreover, condition [START_REF] Fletcher | Orthogonal matching pursuit from noisy measurements: A new analysis[END_REF] depends on the position i of the ordered coefficients: the larger i, the weaker the constraint on their amplitude. As a result, when x Q 1 = 0, Theorem 4 leads to weaker conditions than those previously proposed in [START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF], [START_REF] Cai | Orthogonal matching pursuit for sparse signal recovery with noise[END_REF] as soon as x Q is not a flat vector. For flat vectors, [START_REF] Fletcher | Orthogonal matching pursuit from noisy measurements: A new analysis[END_REF] obviously reduces to [START_REF] Sturm | Sparse vector distributions and recovery from compressed sensing[END_REF]. 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 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:

γ k    1-(k-2)µ (µ+1)(1-kµ) for OMP, 1-(k-2)µ µ+1 √ 1-(k-1)µ 1-kµ for OLS. ( 20
)
Our result then writes as follows:

Theorem 5 If µ < 1 k , (21)
and ∀i ∈ {1, . . . , k},

|x i | > 2µ(k -i) 1 -iµ |x i+1 | + 2γ k ( + x Q 1 ), (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

P ⊥ Q I-A Q A † Q , where A † Q is the pseudo-inverse of A Q ; in particular, r Q P ⊥
Q y is the residual error when projecting y onto the span of A Q . Finally, •, • represents the vector inner product and 0 m is the null vector of size m × 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 r Q∪{j} 2 :

j ∈ arg min i / ∈Q r Q∪{i} 2 ,
and n -Card{Q} least-square problems have to be solved to compute r Q∪{i} 2 for all i / ∈ Q [START_REF] Chen | Orthogonal least squares methods and their application to non-linear system identification[END_REF]. On the contrary, OMP adopts the simpler rule

j ∈ arg max i / ∈Q | a i , r Q |,
to select the new atom a j , and then solves only one leastsquare problem to update the new residual r Q∪{j} .

The selection rules described above can also be expressed in terms of the (normalized) projected atoms of the dictionary [START_REF] Soussen | Joint k-step analysis of orthogonal matching pursuit and orthogonal least squares[END_REF]. This formulation will turn out to be convenient in our proofs below. More specifically, let

ãi P ⊥ Q a i , bi ãi / ãi 2 if ãi = 0 m 0 m otherwise.
With these notations, the selection rule of Oxx can be reexpressed as (see e.g., [START_REF] Rebollo-Neira | Optimized orthogonal matching pursuit approach[END_REF])

j ∈ arg max i / ∈Q | ci , r Q |, (23)
where ci ãi for OMP, bi for OLS.

For simplicity, the dependence of ãi , bi and ci on 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 Card(Q) = g ≥ 0. If µ < 1 g , then ãi 2 2 ≥ (µ+1) (1-gµ) 1-(g-1)µ ∀i / ∈ Q, | ãi , ãj | ≤ µ (µ+1) 1-(g-1)µ ∀j = i. ( 24
)
Proof: The result is a direct consequence of Lemmas 4 and 10 in [START_REF] Herzet | Exact recovery conditions for sparse representations with partial support information[END_REF].

Lemma 2 Let Card(Q) = g ≥ 0. If µ < 1 g , we have ci , ãi ≥ α g > 0 ∀i / ∈ Q, | ci , ãj | ≤ µ g ∀j = i,
where

α g =    (µ+1) (1-gµ) 1-(g-1)µ for OMP (µ+1)(1-gµ) 1-(g-1)µ
for OLS (25)

µ g = min 1, µ 1 -gµ α g . ( 26
)
Proof: The result immediately follows from Lemma 1 and from ãj 2 ≤ a j 2 = 1 and ci 2 ≤ 1. Note that µ < 1 g implies that ãi = 0 m (see [START_REF] Mallat | A wavelet tour of signal processing[END_REF]). Thus, bi reads ãi / ãi 2 .

Lemma 3 If µ ≤ 1 g+1 , then (26) simplifies to:

µ g = µ 1 -gµ α g . ( 27
) Proof: µ ≤ 1 g+1 implies that µ ≤ 1 -gµ and then µ 1 -gµ α g ≤ α g ≤ 1,
where

α g ≤ 1 follows from ∀i / ∈ Q, α g ≤ ci , ãi ≤ ci 2 ãi 2 ≤ 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 x and a subset Q of cardinality k. Assume that Oxx, with y defined as in (1) as input, has selected atoms in Q Q during the first g iterations, with 0 ≤ g < k. Let α g , µ g be defined as in Lemma 2. If

µ < 1 g , (28)
(α g + µ g ) x Q \Q ∞ -2µ g x Q \Q 1 > 2 ( + x Q 1 ), (29)
then Oxx selects an atom in Q \Q at the next iteration.

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

max i∈Q \Q | ci , r Q | > | cl , r Q |, ∀l / ∈ Q . ( 30
)
First, using the definitions of the residual r Q = P ⊥ Q y and the projected atoms ãi , we have

r Q = s Q + P ⊥ Q w, where s Q = i / ∈Q ãi x i .
Noticing that ci 2 ≤ 1 and P ⊥ Q w 2 ≤ w 2 ≤ , a sufficient condition for ( 30) is then as follows:

max i∈Q \Q | ci , s Q | -| cl , s Q | > 2 , ∀l / ∈ Q . ( 31
)
Let j ∈ arg max i∈Q \Q |x i |. Since µ < 1 g , we can apply Lemma 2 and bound the terms in the left-hand side of (31) as follows:

max i∈Q \Q | ci , s Q | ≥ | cj , s Q | ≥ | cj , ãj | |x j | - i / ∈Q∪{j} | cj , ãi ||x i | ≥ α g |x j | -µ g ( x Q \(Q∪{j}) 1 + x Q 1 ), and ∀l / ∈ Q , | cl , s Q | ≤ | cl , ãl | |x l | + i / ∈Q∪{l} | cl , ãi ||x i | ≤ |x l | + µ g ( x Q \Q 1 + x Q \{l} 1 ),
where the last inequality follows from the fact that | cl , ãl | ≤ 1. Combining these two bounds, we easily obtain that

(α g + µ g )|x j | -2µ g x Q \Q 1 > 2 + (1 -µ g )|x l | + 2µ g x Q 1
is a sufficient condition for [START_REF] Zhang | Sparse recovery with orthogonal matching pursuit under RIP[END_REF] and then [START_REF] Chang | An improved RIP-based performance guarantee for sparse signal recovery via orthogonal matching pursuit[END_REF]. Finally, noticing that µ g ≤ 1 (Lemma 2) and |x l | ≤ x Q 1 , we obtain [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF].

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 Q during the first k iterations for all dictionaries obeying µ < µ , for some µ > 1 2k-1 , as long as x 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 Q = ∅ (with = 0 and x Q 1 = 0), we have that Oxx selects an element of Q provided that:

µ < ρ 2 -ρ , with ρ = x Q ∞ / x Q 1 . Now, since x Q is not flat, we have that ρ > 1 k
, and therefore ρ 2-ρ > 1 2k-1 . On the other hand, if Oxx has selected any g ≥ 1 atoms in Q during the first g iterations, it was proved in [START_REF] Herzet | Exact recovery conditions for sparse representations with partial support information[END_REF]Th. 3] that Oxx makes good decisions during the remaining k -g iterations provided that µ < 1 2k-g-1 . A sufficient condition for Oxx to select correct atoms during the first k steps thus simply writes

µ < µ with µ = min ρ 2 -ρ , 1 2k -2 .
Clearly, µ > 1 2k-1 by definition.

The direct part of Theorem 2 can be seen as a special case of Theorem 5 when = 0 and x Q = 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 Q Q when g ≤ 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 Q \Q.

The first condition of Lemma 4, µ < 1 g , is always verified since µ < 1 k by hypothesis and g ≤ k -1. Let j be the lowest index such that:

j ∈ arg max i∈Q \Q |x i |. (32)
Clearly, (5) implies that j ≤ g + 1.

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

x Q \Q 1 ≤ |x j | + (k -g -1) |x j+1 |. (33)
Hence,

(α g -µ g )|x j | -2µ g (k -g -1)|x j+1 | > 2 ( + x Q 1 ) (34)
is a sufficient condition for [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]. Since g ≤ k -1 and µ < 1

k
by assumption, we have µ < 1 g+1 and we can exploit the expression ( 27) of µ g in Lemma 3 to rewrite:

α g -µ g = α g 1 - µ 1 -gµ > 0. (35)
It follows from ( 35) that

µ g α g -µ g = α g α g -µ g -1, = 1 -gµ 1 -(g + 1)µ -1, = µ 1 -(g + 1)µ .
Then, (34) can be rewritten as

|x j | > 2µ(k -g -1) 1 -(g + 1)µ |x j+1 | + 2( + x Q 1 ) α g -µ g . (36)
We finally obtain condition [START_REF] Maleki | Optimally tuned iterative reconstruction algorithms for compressed sensing[END_REF] by noticing that: [START_REF] Vincent | From blind to guided audio source separation: How models and side information can improve the separation of sound[END_REF]) and 1-µ 1-gµ are both decreasing with g and non-negative, hence 1/(α g -µ g ) (see [START_REF] Plumbley | On polar polytopes and the recovery of sparse representations[END_REF]) is increasing with g. It is upper bounded by 1/(α k-1 -µ k-1 ), which is equal to γ k defined in [START_REF] Gribonval | Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms[END_REF].

• j ≤ g + 1 and the function f (u) = 2µ(k-u) 1-uµ is decreasing on u ∈ [0, k] for µ < 1 k ; • α g (see
We can thus conclude that ( 21)-( 22) are sufficient conditions for ( 28)-( 29) and the next atom selected by Oxx belongs to Q \Q by virtue of Lemma 4. This proof applies recursively to the iterations of Oxx for increasing values of g ∈ {0, . . . , 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 Q Q during the first g iterations. We recursively show that, if [START_REF] Blumensath | On the difference between orthogonal matching pursuit and orthogonal least squares[END_REF] and ( 13) are satisfied, then Oxx keeps on picking atoms in Q as long as the p largest elements of x Q \Q have not been selected.

Assume that after iteration g + t, t ∈ {0, . . . , k -g -1}, has been completed, Oxx has selected Q with Q ⊆ Q Q and {1, . . . , p} Q (that is, some atoms in {1, . . . , p} have not yet been selected by Oxx). We apply Lemma 4 (with subset Q ← Q , and with ← 0, x Q ← 0 n-k ) to prove that the next atom selected by Oxx belongs to Q . The first condition in Lemma 4, µ < 1 g+t , is verified since µ < 1 k and g + t < k. Let j be the lowest index such that

j ∈ arg max i∈Q \Q |x i |. (37)
Because of our assumption {1, . . . , p} Q we necessarily have that {1, . . . , p}∩(Q \Q ) = ∅, and then from convention [START_REF] Donoho | Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[END_REF], we must have j ∈ {1, . . . , p}. By the same arguments as those exposed in the proof of Theorem 5, we have that

|x j | > 2µ(k -g -t -1) 1 -(g + t + 1)µ |x j+1 | (38)
is a sufficient condition for [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]. Next, we have from the convention (11) that j ≤ t+1, and the function

f (u) = 2µ(k-u) 1-uµ is decreasing on u ∈ [0, k], hence on u ∈ [g+j, g+t+1] ⊆ [0, k] for µ < 1/k. So, |x j | > 2µ(k -g -j) 1 -(g + j)µ |x j+1 | (39)
is sufficient for [START_REF] Ben-Haim | Coherence-based performance guarantees for estimating a sparse vector under random noise[END_REF] and then [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]. Since j ∈ {1, . . . , p}, (39) holds by virtue of ( 13) and the next atom selected by Oxx belongs to Q .

Proof of Theorem 3 (Second Part): We show that ( 14) and ( 15) ensure that atoms in Q \Q are selected, provided that the p largest elements of x Q \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 Q with Q ⊆ Q Q after iteration g+t has been completed, with t ∈ {0, . . . , r-1}, and {1, . . . , p} Q . We apply Lemma 4 (with subset Q ← Q , ← 0 and x Q ← 0 n-k ) to show that the next atom selected by Oxx belongs to Q . We note that the first condition of Lemma 4, µ < 1 g+t , is satisfied since µ < 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 Q at the next iteration. From the same arguments as in proof of the first part, we must have j ∈ {1, . . . , p}.

Now, if 1 k ≤ µ < 1 g+r , the function f (u) = 2µ(k-u) 1-uµ is nondecreasing on u ∈ [g + t + 1, g + r] ⊆ [0, g + r]. As a consequence, |x j | > 2µ(k -g -r) 1 -(g + r)µ |x j+1 | (40)
is a sufficient condition for [START_REF] Ben-Haim | Coherence-based performance guarantees for estimating a sparse vector under random noise[END_REF] and then [START_REF] Mo | A remark on the restricted isometry property in orthogonal matching pursuit[END_REF]. Since j ∈ {1, . . . , p}, [START_REF] Wu | The exact support recovery of sparse signals with noise via orthogonal matching pursuit[END_REF] holds by virtue of [START_REF] Eldar | Average case analysis of multichannel sparse recovery using convex relaxation[END_REF] and the next atom selected by Oxx belongs to Q .

Proof of Theorem 4:

We first note that µ < 1 g+1 ∀g ∈ {0, . . . , k -1} since µ < 1 2k-1 by hypothesis and 2k -1 ≥ k ≥ g + 1. The beginning of the proof follows the same lines as the proof of Theorem 5 but exploits that, by assumption [START_REF] Rebollo-Neira | Optimized orthogonal matching pursuit approach[END_REF], |x j | ≥ |x j+1 | for j < k. Let j ≤ g + 1 be defined in [START_REF] Cai | Stable recovery of sparse signals and an oracle inequality[END_REF]. If j < k, (5) implies that:

(α g -µ g (2k -2g -1))|x j | > 2 ( + x Q 1 ) (41)
is a sufficient condition for [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF]. The same result holds in the case j = k, since then, g = k -1 and (41) identifies with [START_REF] Fuchs | On sparse representations in arbitrary redundant bases[END_REF]. Since µ < 1 g+1 , Lemma 3 applies and we can use [START_REF] Ding | Performance analysis of orthogonal matching pursuit under general perturbations[END_REF] to rewrite the latter condition as

α g 1 -gµ (1 -(2k -g -1)µ)|x j | > 2 ( + x Q 1 ). ( 42
)
It can be easily checked from the definition of α g in ( 25) that α g ≥ 1 -gµ holds whenever µ < 1/g. As a consequence, (42) can be relaxed as

(1 -(2k -g -1)µ) |x j | > 2( + x Q 1 ).
Finally, since µ < 1 2k-1 ≤ 1 2k-g-1 and |x j | ≥ |x g+1 |, this condition can be relaxed as [START_REF] Fletcher | Orthogonal matching pursuit from noisy measurements: A new analysis[END_REF]. Hence, the atom selected by Oxx at iteration g + 1 belongs to Q \Q by virtue of Lemma 4.

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 A ∈ R (k+1)×(k+1) and a k-sparse vector x ∈ 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 i∈Q | ci , r Q | = | cj , r Q | for some j / ∈ Q , ( 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 G ∈ R (k+1)×(k+1) be a matrix with ones on the diagonal and -µ, with µ ≤ 1 k , elsewhere. G will play the role of the Gram matrix G = A T A. We will exploit the eigenvalue decomposition of G to construct a dictionary A ∈ R (k+1)×(k+1) with the desired properties. Since G is symmetric, it can be expressed as

G = UΛU T ,
where U (respectively, Λ) is the unitary matrix whose columns are the eigenvectors (respectively, the diagonal matrix of eigenvalues) of G. It is easy to check that G has only two distinct eigenvalues: 1 + µ with multiplicity k and 1 -kµ with multiplicity one.

Because we assume µ ≤ 1 k , all the diagonal elements of Λ are non-negative and the latter matrix can be factorized as Λ = Λ 1/2 Λ 1/2 . The dictionary A can then be defined as

A = Λ 1/2 U T . ( 44
)
We note that by definition, we have A T A = G, and therefore

| a i , a j | = µ ∀i = j. (45)
With this choice of dictionary, the following lemma holds:

Lemma 5 Consider the dictionary A described above with µ ≤ 1 k . Then, we have for all

Q with Card(Q) = g ≤ k -1: ci , ãi = α g ∀ i / ∈ Q, ci , ãj = -µ g ∀ i, j / ∈ Q, i = j, (46)
where α g and µ g are defined in (25)- [START_REF] Ding | Performance analysis of orthogonal matching pursuit under general perturbations[END_REF].

Proof: The expression ( 27) of µ g holds since µ ≤ 1/(g +1).

The result (46) is obvious for Q = ∅ since α 0 = 1, µ 0 = µ and ∀ i, ci = ãi = a i . We now address the case where Q = ∅.

First notice that because Card(Q) = g ≤ k -1, the matrix A T Q A Q is invertible. Indeed, it is a symmetric matrix with ones on the diagonal and -µ elsewhere. Its eigenvalues (i.e., 1+µ with multiplicity g -1 and 1-(g -1)µ with multiplicity one) are therefore strictly positive if µ ≤ 1 k . Hence, the projected atoms ãi can be expressed as

ãi = a i -A Q (A T Q A Q ) -1 A T Q a i .
Using this expression, we also have

ãi , ãj = a i , a j -a T i A Q (A T Q A Q ) -1 A T Q a j , ãi 2 2 = 1 -a T i A Q (A T Q A Q ) -1 A T Q a i .
Taking into account that the inner product between any pair of distinct atoms is equal to -µ by definition of G = A T A, we obtain for i, j / ∈ Q:

ãi , ãj = -µ -µ 2 1 T g (A T Q A Q ) -1 1 g , ãi 2 2 = 1 -µ 2 1 T g (A T Q A Q ) -1 1 g , (47)
where 1 g denotes the "all-ones" vector of dimension g. Finally, we obtain the result for OMP (c i = ãi ) by noticing that 1 g is an eigenvector of (A T Q A Q ) -1 with eigenvalue 1 1-(g-1)µ and identifying the right-hand sides in (47) with [START_REF] Vincent | From blind to guided audio source separation: How models and side information can improve the separation of sound[END_REF] and [START_REF] Ding | Performance analysis of orthogonal matching pursuit under general perturbations[END_REF]. The proof of (46) for OLS (c i = bi ) is a direct consequence of (46) in the case of OMP, using bi = ãi / ãi 2 .

To prove the tightness of each of the conditions (7), we need to introduce particular instances x (j) of x ∈ R k+1 , for j = 1, . . . , k -1:

         x (j) i > 2µ(k-i) 1-iµ x (j) i+1 for 1 ≤ i < j, x (j) j = 2µ(k-j) 1-jµ x (j) j+1 x (j) i = 1 for j + 1 ≤ i ≤ k, x (j) k+1 = 0. ( 48
)
Lemma 6 Consider the dictionary A described above with µ = 1 2k-j and x (j) ∈ R k+1 defined as in (48), for j ≤ k -1. Then, the ordering (5) holds. Moreover, for g ∈ {0, . . . , j -1}, let Q = {1, . . . , g}. Then, cg+1 , r Q ≥ 0 and

(g + 1) ∈ arg max i / ∈Q | ci , r Q |. ( 49
)
If g < j -1, then g + 1 is the unique minimizer of (49).

Proof : Let us first notice that µ = 1 2k-j ensures that our working assumption ( 5) is met because 2µ(k-i) 1-iµ ≥ 1 for i ≤ j. Note also that x (j) is non-negative.

Since µ = 1 2k-j and j ≤ k -1, we have µ ≤ 1 k+1 < 1 g+1 and Lemma 3 applies, leading to 2µg αg-µg = 2µ 1-(g+1)µ > 0. By virtue of (48), we have:

(α g -µ g )x (j) g+1 -2µ g (k -g -1)x (j) g+2 > 0 for g < j -1, = 0 for g = j -1. (50)
We first prove that cg+1 , r Q ≥ 0, ∀g ≤ j -1. Indeed, applying Lemma 5, we have

cg+1 , r Q = cg+1 , l / ∈Q x (j) l ãl = α g x (j) g+1 -µ g l / ∈Q∪{g+1} x (j) l ≥ α g x (j) g+1 -µ g (k -g -1)x (j) g+2 ≥ 0, (51)
where the first inequality follows from ( 5) and the second from (50) and x (j) i ≥ 0 for all i. We then show that (49) holds by proving that :

cg+1 , r Q -| ci , r Q | ≥ 0, ∀i / ∈ Q ∪ {g + 1}. ( 52
) For s ∈ {-1, 1}, let f i (s) cg+1 , r Q -s ci , r Q . Obvi- ously, (52) is satisfied if f i (s) ≥ 0, ∀s ∈ {-1, 1}. Applying Lemma 5 again, we obtain f i (s) = α g x (j) g+1 -µ g l / ∈Q∪{g+1} x (j) l -s   α g x (j) i -µ g l / ∈Q∪{i} x (j) l   . (53)
This leads to

f i (1) = (α g + µ g )(x (j) g+1 -x (j) i ) ≥ 0, (54) since x
(j) g+1 ≥ x (j)
i ≥ 0 from (5). Moreover,

f i (-1) = (α g +µ g )x (j) i +(α g -µ g )x (j) g+1 -2µ g l / ∈Q∪{g+1}
x (j) l .

(55) Hence, from (50) and x (j) i ≥ 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

(j) g+1 > x (j) i ∀i > g + 1,
and that α g > 0 and µ g > 0 for µ < 1 g . The inequality in (54) is therefore strict for g < j -1.

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 Q = {1, . . . , k} and 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 µ = 1 k , we show that Oxx leads to a failure during the first k steps for any sparse representation y = Ax supported by Q . Indeed, suppose that Oxx has selected atoms in Q Q during the first k -1 steps (if not, the result trivially holds). Then, denoting by Q \Q = {i} the remaining element in Q , we show that

| ci , r Q | = | ck+1 , r Q |, (56)
i.e., a failure situation such as [START_REF] Tillmann | The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing[END_REF] occurs.

From the definition of the residual, we have r Q = x i ãi . Since x i = 0, proving (56) is equivalent to showing that

| ci , ãi | = | ck+1 , ãi |,
or, by using Lemma 5, α k-1 = µ k-1 . The latter equality can indeed be seen to be true according to [START_REF] Ding | Performance analysis of orthogonal matching pursuit under general perturbations[END_REF]. We note that this result does not depend on a particular instance of k-sparse vector x (and thus on the decay) but only on the structure of the dictionary.

We now concentrate on the tightness of [START_REF] Natarajan | Sparse approximate solutions to linear systems[END_REF]. Consider the specific dictionary described above and the k-sparse vector x (j) defined in (48) with µ = 1 2k-j , j ∈ {1, . . . , k -1}. It is easy to verify that the inequality in ( 7) is met for i = 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, . . . , j -1} is selected during the first j -1 iterations. By virtue of the same lemma, we have

max i / ∈Q | ci , r Q | = | cj , r Q | (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., cj , r Q + ck+1 , r Q = 0. We conclude from (57) that the failure situation | ck+1 , r Q | = | cj , r Q | occurs.

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 µ < µ with µ ∈ ( 1 2k-1 , 1 k ] as soon as the nonzero coefficients are not all equal (Theorem 1). This result thus shows that the traditional condition µ < 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 µ is related to the rate of decay: the faster the decay, the larger µ . This condition reduces to µ = 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 [START_REF] Donoho | Stable recovery of sparse overcomplete representations in the presence of noise[END_REF] 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 µ < 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 ∼ k 2 to be satisfied for large underdetermined systems (n m). 6 We note that other lines of work have shown (in the uniform setting) that OMP/OLS can succeed in the regime m ∼ k, see e.g., [START_REF] Foucart | Stability and robustness of weak orthogonal matching pursuits[END_REF], [START_REF] Zhang | Sparse recovery with orthogonal matching pursuit under RIP[END_REF]. 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 [START_REF] Bandeira | Certifying the restricted isometry property is hard[END_REF], [START_REF] Tillmann | The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing[END_REF].

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[START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF],[START_REF] Fletcher | Orthogonal matching pursuit from noisy measurements: A new analysis[END_REF], which focus on the uniform success of OMP for random dictionaries (and a given support).

This is in contrast with Basis Pursuit for which RICs usually lead to more favorable conditions.

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.

More precisely, there exists another k-sparse vector x such that x 1 = x 1 and y = Ax = Ax.


domain: phys spi

text:
W Al Saidi

R Sbiaa

Yannick Dusch

N Tiercelin
email: nicolas.tiercelin@iemn.fr

A multi-state memory device based on the Manipulation of a single skyrmion using spin-polarized current

Keywords: Ferromagnetic materials, Micromagnetics, Skyrmion, spin systems, spintronics

Towards a multistate skyrmionic device, Firstly, the motion of a single skyrmion under spin-transfer-torque (STT) is studied in the conventional and constricted wire the study reveals the possibility to pin, depin and annihilate skyrmion. Later, a stepped nano-track with bottom and top confinements has been proposed, to stabilize the skyrmion in each confinement. The adjustment of the current density magnitude and its duration enabled the displacement of the skyrmion at any position. More interestingly, it was observed that only one skyrmion can be stabilized in each confinement when a large number is displaced by current pulses. These results open the way for large-capacity memory devices and neuromorphic computing.

I. INTRODUCTION

Magnetic skyrmion are particle-like magnetic configurations that attracted attention due to their small size, stable structure, easily moved, and provide a new route to denser information storage. Driven by the need for higher storage devices, there is a shift to control the magnetic skyrmion rather than magnetization and domain wall (DW). Intensive studies have been carried out, but the major challenge is device heating has been a serious issue because a large current density is necessary to overcome the pinning, and, therefore, the experiments usually have been done using a short pulse of electric current.

Skyrmions show inertia-driven drift shortly after the current pulse is removed as reported by Morshed et al. [START_REF] Morshed | Positional stability of skyrmions in a racetrack memory with notched geometry[END_REF]. a stepped nanowire is proposed with a stepped barrier to control and stabilize skyrmions under a pulsed current. Later, a constricted wire is designed to stabilize the skyrmion at every site. Opening a path to a new concept of promising magnetic memories based on skyrmion motion in nano tracks, should help future studies to design new memories based on a very dense encoding of information.

II. THEORETICAL METHOD

Numerical solutions for Neel-skyrmion in constricted nanowire were performed using micromagnetic simulation Mumax3 [START_REF] Vansteenkiste | The design and verification of mumax3[END_REF] based on Landau-Lifshitz-Gilbert (LLG) to investigate the spin transfer-induced motion of skyrmions in magnetic tracks with the stepped region. The stepped region is added to the nanowire with the objective to act as a pinning site for stabilizing and controlling the motion of the skyrmions' position and the dimensions were varied. The intrinsic material parameters used in this work were fixed while the device dimension was changed. Following a previous study, the exchange stiffness constant Aex, the damping constant α, the interfacial Dzyaloshinskii-Moriya strength D, the saturation magnetization and the perpendicular uniaxial anisotropy energy Ku were fixed to 15pJm -1 , 0.1, 3.3mJm -2 , 500KAm -1 and 0.8MJm -3 , respectively. The pulsed current is applied in the form of a rectangular pulse along the direction of the wire which flows to the left, so the electron would flow toward the right with a strength of the nonadiabatic STT fixed to 0.2 and the spin polarization P to 0.4. Illustration of the nano-track is shown in fig. 1.

III. RESULTS AND DISCUSSIONS

A. Stabilizing magnetic skyrmion in constricted nanowires

The ability to exceed the edge is predicted through the competition between the force due to the edge generated by the geometrical structure and the driving force. If the current density is small as the skyrmion approaches the edge the velocity will decrease and then vanishes completely skyrmion, for intermediate current values the driving current overcomes the repulsive force without being annihilated, For even larger values the skyrmion collides with the edge and is destroyed as shown in figure . 2. The threshold current density to overcome the edge is related to step size and the skyrmion size. The larger the step size (narrower passage) results in higher barrier energy which will lead to shrinking the size. The larger the size of the skyrmion, the harder for it to shrink and move to the second region resulting in pinning. Fig. 2. snapshots of skyrmion within a stepped nanowire for (a) J = 2.010 11 Am -2 where it is pinned(b) J = 2.510 11 Am -2 where the skyrmion could overcome the stepped region and (c) J = 7.010 11 Am -2 where it was annihilated.

B. Stabilizing magnetic skyrmions in multi-constricted nanowires

In the second part of this study, the pinning and reliable depinning of the skyrmion from the pinning centers under current pulses to have a multistate memory device has been investigated. It can be seen from Figure3 that it is possible to achieve 8 states by pinning the skyrmion in the confinement regions where each region represents one bit, which corresponds to "0" if the region does not contain a skyrmion, and "1" if the region contains one skyrmion. It can be seen in4 that the skyrmion moves with a constant velocity when the current is applied as indicated by an almost straight line when the current stops it bounces back and stabilizes. Alternating the amplitude and number of pulses makes it possible to reach the required states.

Interestingly, the repulsive force from the edge causes the size of the skyrmion to shrink near the edges, if this force is too large in the case of a larger skyrmion or narrower channel or larger current density, the skyrmion will annihilate. It is possible to access any position by changing only the pulse width or/and current density within the nanowire without being pinned in specific confinement.

IV. CONCLUSION

In this study, the dynamics and stability of magnetic skyrmions within a nano-track with multiple confinements were investigated. the study reveals the possibility to pin and stabilize the skyrmion in each confinement. These results open the door for denser memory devices and neuromorphic computing.

Fig. 1 .

 1 Fig. 1. (a), (b), and (c) are schematic drawings of the conventional, stepped nanowires and nano-track with multiple confinements. The length L and the width W were fixed to 300nm, and 75nm, respectively for (a) and (b), in (c) We consider a 2nm thick nano-track with a length of 780nm and a width of 80nm, stepped regions with a size of 3070nm 2 .

Fig. 3 .

 3 Fig.3. snapshots of magnetic states, the length of the wire is L = 780nm, the width w = 80nm and the thickness is 2nm. The color scale shows the out-of-plane component of magnetization.

Fig. 4 .

 4 Fig. 4. skyrmion position at different current pulse values as function of the time. The current density magnitude is shown in the inset.