Anthony Bourrier

Mike E Davies

Tomer Peleg

Patrick Pérez

Rémi Gribonval

Lab M E Davies

Fundamental performance limits for ideal decoders in high-dimensional linear inverse problems

The primary challenge in linear inverse problems is to design stable and robust "decoders" to reconstruct high-dimensional vectors from a low-dimensional observation through a linear operator. Sparsity, low-rank, and related assumptions are typically exploited to design decoders which performance is then bounded based on some measure of deviation from the idealized model, typically using a norm.

This paper focuses on characterizing the fundamental performance limits that can be expected from an ideal decoder given a general model, i.e., a general subset of "simple" vectors of interest. First, we extend the so-called notion of instance optimality of a decoder to settings where one only wishes to reconstruct some part of the original high dimensional vector from a low-dimensional observation. This covers practical settings such as medical imaging of a region of interest, or audio source separation when one is only interested in estimating the contribution of a specific instrument to a musical recording. We define instance optimality relatively to a model much beyond the traditional framework of sparse recovery, and characterize the existence of an instance optimal decoder in terms of joint properties of the model and the considered linear operator. Noiseless and noise-robust settings are both considered. We show somewhat surprisingly that the existence of noise-aware instance optimal decoders for all noise levels implies the existence of a noise-blind decoder.

A consequence of our results is that for models that are rich enough to contain an orthonormal basis, the existence of an 2 / 2 instance optimal decoder is only possible when the linear operator is not substantially dimension-reducing. This covers well-known cases (sparse vectors, low-rank matrices) as well as a number of seemingly new situations (structured sparsity and sparse inverse covariance matrices for instance).

We exhibit an operator-dependent norm which, under a model-specific generalization of the Restricted Isometry Property (RIP), always yields a feasible instance optimality property. This norm can be upper bounded by an atomic norm relative to the considered model.

Introduction

In linear inverse problems, one considers a linear measurement operator M mapping the signal space R n to a measurement space R m , where typically M is either ill-conditioned or dimensionality 1 reducing. The reconstruction of x from Mx is thus a hopeless task unless one can exploit prior knowledge on x to complete the incomplete observation Mx.

Sparsity is a well-known enabling model for this type of inverse problems: it has been proven that for certain such operators M, one can expect to recover the signal x from its measure Mx provided that x is sufficiently sparse, i.e., it has few nonzero components [START_REF] Candès | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF]. If the set of k-sparse signals is denoted Σ k = {x ∈ R n , x 0 ≤ k}, where . 0 is the pseudo-norm counting the number of nonzero components, then this recovery property can be interpreted as the existence of a decoder ∆ : R m → R n such that ∀x ∈ Σ k , ∆(Mx) = x, thus making M a linear encoder associated to the (typically nonlinear) decoder ∆.

Further, the body of theoretical work around sparse recovery in linear inverse problems has given rise to the notion of compressive sensing (CS) [START_REF] Donoho | Compressed sensing[END_REF], where the focus is on choosing -among a more or less constrained set of operators -a dimensionality reducing M to which a decoder can be associated 1 . It is now well-established that this can be achieved in scenarii where m n, showing that a whole class of seemingly high-dimensional signals can thus be reconstructed from far lower dimensional linear measurements than their apparent dimension.

Instance optimal sparse decoders

A good decoder ∆ is certainly expected to have nicer properties than simply reconstructing Σ k . Indeed, the signal x to be reconstructed may not belong exactly in Σ k but "live near" Σ k under a distance d, meaning that d(x, Σ k ) is "small" in a certain sense. In this case, one wants to be able to build a sufficiently precise estimate of x from Mx, that is a quantity ∆(Mx) such that x -∆(Mx) is "small" for a certain norm . . This stability to the model has been formalized into the so-called Instance Optimality assumption on ∆. Decoder ∆ is said to be instance optimal if:

∀x ∈ R n , x -∆(Mx) ≤ Cd(x, Σ k ), (1)
for a certain choice of norm . and distance d. For this property to be meaningful, the constant C must not scale with n and typically "good" instance optimal decoders are decoders which involve a constant which is the same for all n (note that this implicitly relies on the fact that a sparse set Σ k ⊂ R n can be defined for any n). When the norm is 2 or 1 and the distance is 1 , such good instance optimal decoders exist and can be implemented as the minimization of a convex objective [START_REF] Donoho | Compressed sensing[END_REF][START_REF] Candès | Near-optimal signal recovery from random projections: Universal encoding strategies[END_REF][START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF] under assumptions on M such as the Restricted Isometry Property (RIP). Note that instance optimality is a uniform upper bound on the reconstruction error, and that other types of bounds on decoders can be studied, particularly from a probabilistic point of view [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF]. Other early work include upper bounds on the reconstruction error from noisy measurements with a regularizing function when the signal belongs exactly to the model [START_REF] Engl | Regularization of Inverse Problems[END_REF].

In [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF], the authors considered the following question: Given the encoder M, is there a simple characterization of the existence of an instance optimal decoder? Their goal was not to find implementable decoders that would have this property, but rather to identify conditions on M and Σ k under which the reconstruction problem is ill-posed if one aims at finding an instance optimal decoder with small constant. The existence of a decoder ∆ which satisfies (1) will be called the Instance Optimality Property (IOP). The authors proved that this IOP is closely related to a property of the kernel of M with respect to Σ 2k , called the Null Space Property (NSP). This relation allowed them to study the existence of stable decoders under several choices of norm . and distance d(., .). A related question addressed in [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF] is that of the fundamental limits of dimension reduction: Given the target dimension m and desired constant C, is there an encoder M with an associated instance optimal decoder? They particularly showed that there is a fundamental trade-off between the size of the constant C in (1) (with 2 norm and 2 distance) and the dimension reduction ratio m/n.

Low-dimensional models beyond sparsity

Beyond the sparse model, many other low-dimensional models have been considered in the context of linear inverse problems and CS [START_REF] Baraniuk | Low-dimensional models for dimensionality reduction and signal recovery: A geometric perspective[END_REF]. In these generalized models, the signals of interest typically live in or close to a subset Σ of the space, which typically contains far fewer vectors than the whole space. Such models encompass sets of elements as various as block-sparse signals [START_REF] Eldar | Block-sparse signals: uncertainty relations and efficient recovery[END_REF], unions of subspaces, whether finite [START_REF] Blumensath | Sampling theorems for signals from the union of finitedimensional linear subspaces[END_REF] or possibly infinite [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF], signals sparse in a redundant dictionary [START_REF] Rauhut | Compressed sensing and redundant dictionaries[END_REF], cosparse signals [START_REF] Nam | The Cosparse Analysis Model and Algorithms[END_REF], approximately low-rank matrices [START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF][START_REF] Candès | Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[END_REF], low-rank and sparse matrices [START_REF] Zhou | Stable principal component pursuit[END_REF][START_REF] Candès | Robust principal component analysis?[END_REF], symmetric matrices with sparse inverse [START_REF] Yuan | Model selection and estimation in the Gaussian graphical model[END_REF][START_REF] Yuan | High dimensional inverse covariance matrix estimation via linear programming[END_REF] or manifolds [START_REF] Baraniuk | Random projections of smooth manifolds[END_REF][START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF]. An old result which can also be interpreted as generalized CS is the low-dimensional embedding of a point cloud [START_REF] Johnson | Extensions of Lipschitz mappings into a Hilbert space[END_REF][START_REF] Achlioptas | Database-friendly random projections[END_REF]. Some of these models are pictured in Figure 1.

Since these models generalize the sparse model, the following question arises: can they be considered under a general framework, sharing common reconstruction properties? In this work, we are particularly interested in the extension of the results of [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF] to these general models, allowing to further investigate the well-posedness of such problems.

In [START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF], the theoretical results of [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF] are generalized in the case where one aims at stably decoding a vector living near a finite union of subspaces (UoS). They also show in this case the impossibility of getting a good 2 / 2 instance optimal decoder with substantial dimensionality reduction. Their extension also covers the case where the quantity one wants to decode is not the signal itself but a linear measure of the signal.

In this work, we further extend the study of the IOP to general models of signals: we consider signals of interest living in or near a subset Σ of a vector space E, without further restriction, and show that instance optimality can be generalized for such models. In fact, we consider the following generalizations of instance optimality as considered in [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF]:

• Robustness to noise: noise-robust instance optimality is characterized, showing somewhat surprisingly the equivalence between the existence of two flavors of noise-robust decoders (noise-aware and noise-blind);

• Infinite dimension: signal spaces E that may be infinite dimensional are considered. For example E may be a Banach space such as an L p space or a space a signed measures. This is motivated by recent work on infinite dimensional compressed sensing [START_REF] Adcock | Breaking the coherence barrier: A new theory for compressed sensing[END_REF] or compressive density estimation [START_REF] Bourrier | Compressive Gaussian Mixture Estimation[END_REF];

• Task-oriented decoders: the decoder is not constrained to approximate the signal x itself but rather a linear feature derived from the signal, Ax, as in [START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF]; in the usual inverse problem framework, A is the identity. Examples of problems where A = I include:

-Medical imaging of a particular region of the body: as in Magnetic Resonance Imaging, one may acquire Fourier coefficients of a function defined on the body, but only want to reconstruct properly a particular region. In this case, A would be the orthogonal projection on this region.

-Partial source separation: given an audio signal mixed from several sources whose positions are known, as well as the microphone filters, the task of isolating one of the sources from the mixed signal is a reconstruction task where E is the space of concatenated sources, and A orthogonally projects such a signal in a single source signal space.

• Pseudo-norms: Instead of considering instance optimality involving norms, we use pseudonorms with fewer constraints, allowing us to characterize a wider range of instance optimality properties. As we will see in Section 2.3, this flexibility on the pseudo-norms has a relationship with the previous point: it essentially allows one to suppose A = I in every case, up to a change in the pseudo-norm considered for the approximation error.

Contributions of this work

We summarize below our main contributions.

Instance optimality for inverse problems with general models

In the noiseless case, we express a concept of instance optimality which does not necessarily involve homogeneous norms and distances but some pseudo-norms instead. Such a generalized instance optimality can be expressed as follows:

∀x ∈ E, Ax -∆(Mx) G ≤ Cd E (x, Σ), (2)
where . G is a pseudo-norm and d E is a distance the properties of which will be specified in due time, and A is a linear operator representing the feature one wants to estimate from Mx. Our first contribution is to prove that the existence of a decoder ∆ satisfying [START_REF] Adcock | Generalized sampling and infinite-dimensional compressed sensing[END_REF], which is a generalized IOP, can be linked with a generalized NSP, similarly to the sparse case. This generalized NSP can be stated as:

∀h ∈ ker(M), Ah G ≤ Dd E (h, Σ -Σ), (3)
where the set Σ -Σ is comprised of all differences of elements in Σ, that is Σ -Σ = {z 1 -z 2 : z 1 , z 2 ∈ Σ}. The constants C and D are related by a factor no more than 2, as will be stated in Theorems 1 and 2 characterizing the relationships between these two properties. In particular, all previously mentioned low-dimensional models can fit in this generalized framework.

Noise-robust instance optimality

Our second contribution (Theorems 3 and 4) is to link a noise-robust extension of instance optimality to a property called the Robust NSP. Section 2 regroups these noiseless and noise-robust results after a review of the initial IOP/NSP results of [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF]. We show somewhat surprisingly that the existence of noise-aware instance optimal decoders for all noise levels implies the existence of a noise-blind decoder (Theorem 5).

If a Robust NSP is satisfied, an instance optimal decoder can be defined as:

∆(y) = argmin u∈E D 1 d E (u, Σ) + D 2 d F (Mu, y), (4)
where the constants D 1 , D 2 and distances d E , d F are those which appear in the Robust NSP. The objective function is the sum of two terms: a distance to the model and a distance to the measurements. Also note that by fixing D 2 to infinity, one defines an instance optimal noise-free decoder provided the corresponding NSP is satisfied.

Limits of dimensionality reduction with generalized models

The reformulation of IOP as an NSP allows us to consider the 2 / 2 instance optimality for general models in Section 3. In this case, the NSP can be interpreted in terms of scalar product and we precise the necessity of the NSP for the existence of an instance optimal decoder. This leads to the proof of Theorem 6 stating that, just as in the sparse case, one cannot expect to build an 2 / 2 instance optimal decoder if M reduces substantially the dimension and the model is "too large" in a precise sense. In particular, we will see that the model is "too large" when the set Σ -Σ contains an orthonormal basis. This encompasses a wide range of standard models where a consequence of our results is that 2 / 2 IOP with dimensionality reduction is impossible:

• k-sparse vectors. In the case where Σ = Σ k is the set of k-sparse vectors, Σ contains the null vector and the canonical basis, so that Σ -Σ contains the canonical basis. Note that the impossibility of good 2 / 2 IOP has been proved in [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF].

• Block-sparse vectors [START_REF] Eldar | Block-sparse signals: uncertainty relations and efficient recovery[END_REF]. The same argument as above applies in this case as well, implying that imposing a block structure on sparsity does not improve 2 / 2 feasibility.

• Low-rank matrices [START_REF] Recht | Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[END_REF][START_REF] Candès | Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[END_REF]. In the case where E = M n (R) and Σ is the set of matrices of rank ≤ k, Σ also contains the null matrix and the canonical basis.

• Low-rank + sparse matrices [START_REF] Zhou | Stable principal component pursuit[END_REF][START_REF] Candès | Robust principal component analysis?[END_REF]. The same argument applies to the case where the model contains all matrices that are jointly low-rank and sparse, which appear in phase retrieval [START_REF] Oymak | Simultaneously structured models with application to sparse and low-rank matrices[END_REF][START_REF] Ohlsson | Compressive phase retrieval from squared output measurements via semidefinite programming[END_REF][START_REF] Candès | Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming[END_REF].

• Low-rank matrices with non-sparsity constraints. In order to reduce the ambivalence of the low-rank + sparse decomposition of a matrix, [START_REF] Candès | Robust principal component analysis?[END_REF] introduced non-sparsity constraints on the low-rank matrix in order to enforce its entries to have approximately the same magnitude. However, as shown in Lemma 3, an orthonormal Fourier basis of the matrix space can be written as differences of matrices which belong to this model.

• Reduced union of subspace models [START_REF] Baraniuk | Low-dimensional models for dimensionality reduction and signal recovery: A geometric perspective[END_REF] obtained by pruning out the combinatorial collection of k-dimensional subspaces associated to k-sparse vectors. This covers block-sparse vectors [START_REF] Eldar | Block-sparse signals: uncertainty relations and efficient recovery[END_REF], tree-structured sparse vectors, and more. Despite the fact that these unions of subspaces may contain much fewer k-dimensional subspaces than the combinatorial number of subspaces of the standard k-sparse model, the same argument as in the k-sparse model applies to these signal models, provided they contain the basis collection of 1-sparse signals. This contradicts the naive intuition that2 / 2 IOP could be achievable at the price of substantially reducing the richness of the model through a drastic pruning of its subspaces.

• k-sparse expansions in a dictionary model [START_REF] Rauhut | Compressed sensing and redundant dictionaries[END_REF]. More generally, if the model is the set of vectors which a linear combination of at most k elements of a dictionary D which contains an orthogonal family or a tight frame, then Theorem 6 applies.

• Cosparse vectors with respect to the finite difference operator [START_REF] Nam | The Cosparse Analysis Model and Algorithms[END_REF][START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF]. As shown in [START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF], the canonical basis is highly cosparse with respect to the finite difference operator, hence it is contained in the corresponding union of subspaces.

• As shown in Lemma 2, this is also the case for symmetric definite positive square matrices with k-sparse inverse. The covariance matrix of high-dimensional Gaussian graphical models is of this type: the numerous pairwise conditional independences that characterize the structure of such models, and make them tractable, translate into zeros entries of the inverse covariance matrix (the concentration matrix). Combining sparsity prior on the concentration matrix with maximum likelihood estimation of covariance from data, permits to learn jointly the structure and the parameters of Gaussian graphical models (so called "covariance selection" problem) [START_REF] Yuan | Model selection and estimation in the Gaussian graphical model[END_REF][START_REF] Yuan | High dimensional inverse covariance matrix estimation via linear programming[END_REF]. In very high-dimensional cases, compressive solutions to this problem would be appealing.

• Johnson-Lindenstrauss embedding of point clouds [START_REF] Achlioptas | Database-friendly random projections[END_REF]. Given a set X of L vectors in R n and > 0, there exists a linear mapping f : R n → R m , with m = O(ln(L)/ 2 ) and

(1 -) x -y 2 ≤ f (x) -f (y) 2 ≤ (1 + ) x -y 2 (5)
holds for all x, y ∈ X . The fact that the point cloud contains a tight frame is satisfied if it "spreads" in a number of directions which span the space. In this case, one cannot guarantee precise out-of-sample reconstruction of the points in R n in the 2 -sense, except for a very limited neighborhood of the point cloud. This is further discussed in Section 5.

Generalized Restricted Isometry Property

Our last contribution, in Section 4, is to study the relations between the NSP and a generalized version of the Restricted Isometry Property (RIP). This generalized RIP bounds Mx F from below and/or above on a certain set V , and can be decomposed in:

Lower -RIP : ∀x ∈ V, α x G ≤ Mx F (6) Upper -RIP : ∀x ∈ V, Mx F ≤ β x G , (7)
where . G and . F are pseudo-norms defined respectively on the signal space and on the measure space, and 0 < α ≤ β < +∞. We prove particularly in Theorem 7 that a generalized lower-RIP on Σ -Σ implies the existence of instance optimal decoders in the noiseless and the noisy cases for a certain norm • E we call the "M -norm" 2 .

Furthermore, we prove that under an upper-RIP assumption on Σ, this M -norm can be upper bounded by an atomic norm [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF] defined using Σ and denoted . Σ . This norm is easier to interpret than the M -norm: it can in particular be upper bounded by usual norms for the k-sparse vectors and low-rank matrices models. We have the following general result relating generalized RIP and IOP (Theorem 9): if M satisfies a lower-RIP (6) for V = Σ -Σ and an upper-RIP [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF] for V = Σ, then for all δ > 0, there exists a decoder ∆ δ satisfying ∀x ∈ E, ∀e ∈ F ,

x -∆ δ (Mx + e) G ≤ 2 1 + β α d Σ (x, Σ) + 2 α e E + δ, (8)
which is a particular case of Robust instance optimality, as described in Section 2.

In particular, this generalized RIP encompasses classical or recent RIP formulations, such as

• The standard RIP [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF] with V as the set of k-sparse vectors, • G and • F being 2 norms.

• The Union of Subspaces RIP [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF] with V as a union of subspaces, • G and • F being 2 norms.

• The RIP for low-rank matrices [START_REF] Candès | Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[END_REF] with V as the set of matrices of rank ≤ r, • G as the Frobenius norm and • F as the 2 norm;

• The D-RIP [START_REF] Candès | Compressed sensing with coherent and redundant dictionaries[END_REF] for the dictionary model with V as the set of vectors spanned by k columns of a dictionary matrix, • G and • F being 2 norms;

• The Ω-RIP [START_REF] Giryes | Greedy-Like Algorithms for the Cosparse Analysis Model. partially funded by the ERC, PLEASE project[END_REF] for the cosparse model with V as the set of vectors x such that Ωx is k-sparse, where Ω is the cosparse operator, • G and • F being 2 norms;

• Similarly, the task-RIP can be defined given a linear operator A such that one aims at reconstructing the quantity Ax (instead of x) to perform a particular task. As we will see in Section 2.3, in terms of IOP, this is essentially equivalent to reconstructing x in terms of the norm A • G . In this case, the corresponding lower task-RIP reads:

α Ax G ≤ Mx F . (9)

Infinite-dimensional inverse problems

The generalization of the relationship between the IOP, the NSP and the RIP to arbitrary vector spaces allows us to consider recovery results for infinite dimensional inverse problems. Such problems have mainly been considered in separable Hilbert spaces [START_REF] Adcock | A generalized sampling theorem for stable reconstructions in arbitrary bases[END_REF][START_REF] Adcock | Breaking the coherence barrier: A new theory for compressed sensing[END_REF], where the signals of interest are sparse with respect to a Hilbert basis and the measurement operators subsample along another Hilbert basis. In the theory of generalized sampling [START_REF] Adcock | A generalized sampling theorem for stable reconstructions in arbitrary bases[END_REF], even when the signal model Σ is simply a finite dimensional subspace, it can be necessary to oversample by some factor in order to guarantee stable recovery. In fact Theorem 4.1 of [START_REF] Adcock | Generalized sampling and infinite-dimensional compressed sensing[END_REF] can be read as a statement of 2 / 2 instance optimality for a specific (linear) decoder given in terms of the NSP constant of the measurement operator.

The results presented here therefore provide an extension of generalized sampling for linear models beyond 2 . However, as mentioned in Section 4.3.1, one cannot hope to get uniform instance optimality in this setting for a standard sparsity model. This is mentioned in [START_REF] Adcock | Breaking the coherence barrier: A new theory for compressed sensing[END_REF] when the authors state that no RIP can be satisfied in this case. In section 4.3.2, we nevertheless discuss the possibility of uniform instance optimality results in infinite dimensions with a proper choice of model Σ and pseudo-norms. In particular, a non-constructive topological result ensures that a generalized RIP is satisfied for a model of finite box-counting dimension [START_REF] James C Robinson | Dimensions, Embeddings, and Attractors. Cambridge Tracts in Mathematics[END_REF]. This generalized RIP leads to an IOP, according to Theorem 7.

Hopefully, our results will therefore help characterizing conditions under which infinite-dimensional uniform IOP is possible.

Structure of the paper

We will now describe the layout of the paper. Section 2 first contains a quick review of the relationship between IOP and NSP in the usual sparse case, then exposes the more general setting considered in this paper, for which these properties and their relationship are extended, both in noiseless and noisy settings. Section 3 then focuses on the particular case of 2 / 2 IOP, proving the impossibility for a certain class of models to achieve such IOP with decent precision in dimension reducing scenarii. In particular, we show that this encompasses a wide range of usual models. Finally, in Section 4, we get back to the problem of IO with general norms and prove that a generalized version of the lower-RIP implies the existence of an instance optimal decoder for a certain norm we call the "M -norm". Using a topological result, we illustrate that this implication may be exploited for certain models and norms, even in infinite dimensions. We propose an upperbound on this norm under a generalized upper-RIP assumption to get an IOP with simpler norms, illustrating the result in standard cases.

Generalized IOP and NSP equivalences

In this section, we review the initial IOP/NSP relationship before extending it in several ways.

The initial result

In [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF], the authors consider two norms . G and . E defined on the signal space R n . The distance derived from . E will be denoted d E . Given a vector x ∈ R n and a subset A ⊂ R n , the distance from x to A is defined as d E (x, A) = inf y∈A xy E . These two norms allow the definition of instance optimality: a decoder ∆ : R m → R n is said to be instance optimal for k-sparse signals if

∀x ∈ R n , x -∆(Mx) G ≤ Cd E (x, Σ k ), (10)
for some constant C > 0. This property on ∆ upper bounds the reconstruction error of a vector, measured by . G , by the distance from the vector to the model, measured by d E . The authors prove that the existence of an instance optimal decoder, called IOP, is closely related to the NSP of M with respect to the set Σ 2k of 2k-sparse vectors. Noting N = ker(M), this NSP states

∀h ∈ N , h G ≤ Dd E (h, Σ 2k ) (11)
for some constant D.

The relationship between the IOP and the NSP is the following: if there exists an instance optimal decoder ∆ satisfying [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF], then [START_REF] Candès | Compressed sensing with coherent and redundant dictionaries[END_REF] holds with D = C. Conversely, if [START_REF] Candès | Compressed sensing with coherent and redundant dictionaries[END_REF] holds, then there exists a decoder ∆ such that [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF] holds with C = 2D. Such a decoder can be defined as follows, supposing M is onto:

∆(Mx) = argmin z∈(x+N ) d E (z, Σ k ), (12)
x + N denoting the set {x + h, h ∈ N }. The well-posedness of this definition is discussed in Appendix A, in the more general setting where the model is a finite union of subspaces in finite dimension. Note that for generalized models, such a decoder may not necessarily exist since the infimum of d E (z, Σ) may not be achieved, as we will discuss in the next section. This result can be seen as an "equivalence" between the IOP and the NSP, with similar constants.

Proposed extensions

The framework we consider is more general. The signal space is a vector space E, possibly infinitedimensional. In particular, E may be a Banach space such as an L p space or a space of signed measures. On this space is defined a linear operator M : E → F , where F is the measurement space, which will most likely be finite-dimensional in practice. We assume that M is onto. We further define a signal model Σ ⊂ E comprising the signals which we want to be able to "reconstruct" from their images by M. In the framework we consider, this "reconstruction" is not necessarily an inverse problem where we want to recover x from Mx. More precisely, as in [START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF], we consider a case where we want to recover from Mx a quantity Ax, where A is a linear operator mapping E into a space G. When G = E and A = I, we are brought back to the usual case where we want to reconstruct x. This generalized framework is illustrated in Figure 2.

In this generalized framework, we are now interested in the concepts of IOP and NSP, as well as their relationship. A decoder ∆ : F → G will aim at approximating Ax from Mx.

The approximation error will be measured by a function . G : G → R + . This function needs not be a norm in order to state the following results. It still must satisfy the following properties:

Symmetry : x G = -x G (13) Triangle inequality : x + y G ≤ x G + y G . ( 14
)
The differences with a regular norm is that neither definiteness nor homogeneity is required: x G = 0 needs not imply x = 0 and λx G needs not equal |λ| x G . We provide two examples of such pseudo-norms in the case where G = R n :

• . G can be defined as a "non-normalized" p -quasinorm for 0

≤ p ≤ 1, that is x G = n i=1 |x i | p . In this case, λx G = |λ| p x G . • More generally, if f : R + → R + is a concave function such that f (x) = 0 ⇔ x = 0, then . G can be defined as the f -(pseudo-)norm x f = n i=1 f (|x i |)
, see [START_REF] Gribonval | Highly sparse representations from dictionaries are unique and independent of the sparseness measure[END_REF]. In order to measure the distance from a vector to the model, we also endow E with a pseudo-norm . E : E → R + which satisfies the same properties as . G with the additional requirement that 0 E = 0. The pseudo-distance d E is defined on E 2 by d(x, y) = xy E . Yet again, . E can be defined as a non-normalized p -norm or an f -norm.

We will also consider a noisy framework where the measure Mx is perturbed by an additive noise term e. To consider IOP and NSP in this context, we measure the amount of noise with supplied with a pseudo-norm . E used to measure the distance from a vector to the model Σ containing the signals of interest. E is mapped in the measure space F by the operator M and the measure is perturbed by an additive noise e. The space F is supplied with a pseudo-norm . F . The feature space G, supplied with a norm . G , is composed of vectors obtained by applying a linear operator A to the signals in E. These feature vectors are the vectors one wants to reconstruct from the measures in M by applying a decoder ∆. The reconstruction error for the vector x and noise e is therefore Ax -∆(Mx + e) G . Note that in the case where E = G and A = I, the decoder is aimed at reconstructing exactly the signals.

Signal space E Pseudo-norm • E (pseudo-distance d E ) Measure space F Pseudo-norm • F Σ x d E (x, Σ) Mx Mx + e MΣ Ax ∆(Mx + e) Ax -∆(Mx + e) G AΣ M ∆ A Feature space G Pseudo-norm • G

Triangle Inequality Symmetry

0 = 0 Definiteness Homogeneity . E X X X - - . F X X X - - . G X X - - -
Table 1: Summary of the hypotheses on the pseudo-norms . E , . F and . G . A cross means the property is required, a horizontal bar means it is not.

a pseudo-norm in the measurement space F , which we will denote by . F . The assumptions we make on . F are the same as the assumptions on . E . To sum up, here are the extensions we propose compared to the framework of [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF][START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF] :

• The measure Mx can be perturbed by an additive noise e.

• The model set Σ can be any subset of E.

• E is not necessarily R n but can be any vector space, possibly infinite-dimensional.

• The reconstruction of Ax is targeted rather than that of x.

• The functions . E , . F and . G need not be norms but can be pseudo-norms with relaxed hypotheses. In particular, Table 1 summarizes the requirements on these functions.

Once we have derived the generalized IOP and NSP equivalences, we see that one can essentially be brought back to the case where A = I with a proper choice of • G . This will be discussed in Section 2.3.

Let's note that even though [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF] does not consider the noisy case, some other works have studied noisy instance optimality for the standard sparse model and with p -norms ( [START_REF] Wojtaszczyk | Stability and instance optimality for gaussian measurements in compressed sensing[END_REF], Chapter 11 of [START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF]). They mainly study conditions under which standard 1 decoders are instance optimal. Here, we adopt a more conceptual approach by considering conditions for the existence of an instance optimal decoder, without restriction on its practical tractability. This has the advantage of providing fairly simple equivalences and also to identify fundamental performance limits in a certain framework.

In these works, the underlined relationships between 1 instance optimality and NSP are somewhat different than ours since they usually take advantage of the particular geometry of the sparse problem with 1 decoder. An interesting open question is to what extent we can bridge the gap between this particular setup and a more general setup.

The noiseless case

We first consider the same framework as [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF][START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF], where one measures Mx with infinite precision. In our generalized framework, instance optimality for a decoder ∆ reads:

∀x ∈ E, Ax -∆(Mx) G ≤ Cd E (x, Σ).
We will prove that if IOP holds, i.e., if the above holds for a certain decoder ∆, then a generalized NSP is satisfied, that is:

∀h ∈ N , Ah G ≤ Dd E (h, Σ -Σ), with D = C. Note that the set Σ 2k has been replaced by Σ -Σ = {x -y, x ∈ Σ, y ∈ Σ}. When Σ = Σ k , we have indeed Σ -Σ = Σ 2k . N Σ x + N • x • x 1 d(x 1 , Σ) • x 2 d(x 2 , Σ) • x 3 d(x 3 , Σ)
Figure 3: Necessity of the additive term δ in a simple case. For each x in the blue half-plane, the distance d E (x + N , Σ) is never reached at a particular point of x + N : the distance strictly decreases as one goes right along the affine plane x + N (d(x 1 , Σ) < d(x 2 , Σ) < d(x 3 , Σ)), so that the minimal distance is reached "at infinity".

The construction of an instance optimal decoder from the NSP is more complicated and the form of the instance optimality we get depends on additional assumptions on Σ and M. Let's first suppose that for all x ∈ E, there exists z ∈ (x + N ) such that d E (z, Σ) = d E (x + N , Σ). Then the NSP (3) implies the existence of an instance optimal decoder satisfying (2) with C = 2D. If this assumption is not true anymore, then the NSP implies a slightly modified IOP, which states, for any δ > 0, the existence of a decoder ∆ δ such that:

∀x ∈ E, Ax -∆ δ (Mx) G ≤ Cd E (x, Σ) + δ, (15)
reflecting the fact that one cannot necessarily consider the exact quantity

argmin z∈(x+N ) d E (z, Σ) but rather a certain vector z ∈ (x + N ) satisfying d E (z, Σ) ≤ d E (x + N , Σ) + δ.
A similar positive "projection error" appears in [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF].

Remark 1. To understand the necessity of such an additive error term when Σ is a general set, we can consider the following toy example depicted in Figure 3 where

E = R 2 , N = R × {0}, Σ = {(x 1 , x 2 ) ∈ (R + ) 2 : x 2 = 1 x1
} and . G / . E are the 2 norm. In this case, the minimal distance between x + N and Σ is not reached at any point, making it necessary to add the δ term for the decoder to be well-defined.

In this setting, the NSP (3) implies the existence of instance optimal decoders in the sense of (15) for all δ > 0. Moreover, this weak IOP formulation still implies the regular NSP with D = C. This is summarized in Theorems 1 and 2.

Theorem 1. Suppose ∀δ > 0, there exists a decoder ∆ δ satisfying (15):

∀x ∈ E, Ax -∆ δ (Mx) G ≤ Cd E (x, Σ) + δ.
Then M satisfies the NSP (3):

∀h ∈ N , Ah G ≤ Dd E (h, Σ -Σ), with constant D = C. Theorem 2. Suppose that M satisfies the NSP (3): ∀h ∈ N , Ah G ≤ Dd E (h, Σ -Σ).
Then ∀δ > 0, there exists a decoder ∆ δ satisfying (15):

∀x ∈ E, Ax -∆ δ (Mx) G ≤ Cd E (x, Σ) + δ, with C = 2D.
If we further assume that

∀x ∈ E, ∃z ∈ (x + N ), d E (z, Σ) = d E (x + N , Σ), ( 16
)
then there exists a decoder ∆ satisfying (2):

∀x ∈ E, Ax -∆(Mx) G ≤ Cd E (x, Σ) (17)
with C = 2D.

Note that this result is similar to the result proven in [START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF], which was stated in the case where Σ is a finite union of subspaces in finite dimension. In this framework, condition ( 16) is always satisfied as soon as . E is a norm, by the same argument as in usual CS (see Appendix A).

Let's also note the following property: if . E is definite, that is x E = 0 ⇒ x = 0, then d E is a distance. In the following proposition, we prove that if we further suppose that the set Σ + N is a closed set with respect to d E , then the NSP (3) implies for any δ > 0 the existence of a decoder ∆ δ satisfying (2) with C = (2 + δ)D. This assumption therefore allows us to suppress the additive constant in [START_REF] Candès | Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming[END_REF] and replace it by an arbitrarily small increase in the multiplicative constant of (2). Proposition 1. Suppose that M satisfies the NSP (3), that d E is a distance and that Σ + N is a closed set with respect to d E . Then ∀δ > 0, there exists a decoder ∆ δ satisfying:

∀x ∈ E, Ax -∆ δ (Mx) G ≤ (2 + δ)Dd E (x, Σ). ( 18
)

The noisy case

In practice, it is not likely that one can measure with infinite precision the quantity Mx. This measure is likely to be contaminated with some noise, which will be considered in the following as an additive term e ∈ F , so that the measure one gets is y = Mx + e. In this case, a good decoder should be robust to noise, so that moderate values of e should not have a severe impact on the approximation error. We are interested in the existence of similar results as before in this noisy setting.

We first need to define a noise-robust version of instance optimality. The robustness to noise of practical decoders is in fact a problem that has been considered by many authors. A first type of result considers noise-aware decoders, where given the noise level ≥ 0 a decoder ∆ fulfills the following property

∀x ∈ E, ∀e ∈ F, e F ≤ ⇒ Ax -∆(Mx + e) G ≤ C 1 d E (x, Σ) + C 2 . ( 19
)
Here, the upper bound on the approximation error gets a new term measuring the amplitude of the noise. For example, this noise-robust instance optimality holds for a noise-aware 1 decoder in the sparse case with bounded noise [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF] for . G = . 2 and . E = . 1 / √ k, provided M satisfies the RIP on Σ 2k .

In practical settings, it is hard to assume that one knows precisely the noise level. To exploit the above guarantee with a noise-aware decoder, one typically needs to overestimate the noise level. This loosens the effective performance guarantee and potentially degrades the actual performance of the decoder. An apparently stronger property for a decoder is to be robust even without knowledge of the noise level:

∀x ∈ E, ∀e ∈ F, Ax -∆(Mx + e) G ≤ C 1 d E (x, Σ) + C 2 e F . ( 20
)
Further on, such decoders will be referred to as noise-blind. Guarantees of this type have been obtained under a RIP assumption for practical decoders such as iterative hard thresholding, CoSAMP, or hard thresholding pursuit, see e.g. [25, Corollary 3.9]. Of course, the existence of a noise-blind noise-robust decoder in the sense of [START_REF] Devore | Some remarks on greedy algorithms[END_REF] implies the existence of a noise-aware noise-robust decoder in the sense of ( 19) for any noise level . We will see that, somewhat surprisingly, the converse is true in a sense, for both are equivalent to a noise-robust NSP.

Just as in the noiseless case, dealing with an arbitrary model Σ and possibly infinite dimensional E requires some caution. For δ > 0, the noise-robust (and noise-blind) instance optimality of a decoder ∆ δ is defined as:

∀x ∈ E, ∀e ∈ F, Ax -∆ δ (Mx + e) G ≤ C 1 d E (x, Σ) + C 2 e F + δ. (21)
One can see that ∆ δ necessarily also satisfies the noiseless instance optimality [START_REF] Candès | Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming[END_REF] by setting e = 0. As we show below, if for every δ > 0 there exists a noise-robust instance optimal decoder ∆ δ satisfying [START_REF] Donoho | Compressed sensing[END_REF], then a generalized NSP for M relatively to Σ -Σ, referred to as Robust NSP, must hold:

∀h ∈ E, Ah G ≤ D 1 d E (h, Σ -Σ) + D 2 Mh F , (22)
with

D 1 = C 1 and D 2 = C 2 .
This property appears e.g. in [START_REF] Foucart | A mathematical introduction to compressive sensing[END_REF] (Chap. 4) with . G = . E = . 1 and . F any norm. Note that this Robust NSP concerns every vector of E and not just the vectors of the null space N = ker(M) 3 . In the case where h ∈ N , one retrieves the regular NSP. For other vectors h, another additive term, measuring the "size" of Mh, appears in the upper bound.

Conversely, the Robust NSP implies the existence of noise-robust instance optimal decoders ∆ δ satisfying [START_REF] Donoho | Compressed sensing[END_REF] with C 1 = 2D 1 and C 2 = 2D 2 for all δ > 0. These results are summarized in Theorems 3 and 4.

Theorem 3. Suppose ∀δ > 0, there exists a decoder ∆ δ satisfying (21):

∀x ∈ E, ∀e ∈ F, Ax -∆ δ (Mx + e) G ≤ C 1 d E (x, Σ) + C 2 e F + δ.
Then M satisfies the Robust NSP [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF]:

∀h ∈ E, Ah G ≤ D 1 d E (h, Σ -Σ) + D 2 Mh F , with constants D 1 = C 1 and D 2 = C 2 .
Theorem 4. Suppose that M satisfies the Robust NSP [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF]:

∀h ∈ E, Ah G ≤ D 1 d E (h, Σ -Σ) + D 2 Mh F .
Then ∀δ > 0, there exists a decoder ∆ δ satisfying (21):

∀x ∈ E, ∀e ∈ F, Ax -∆ δ (Mx + e) G ≤ C 1 d E (x, Σ) + C 2 e F + δ, with constants C 1 = 2D 1 and C 2 = 2D 2 .
We conclude this section by discussing the relation between noise-aware and noise-blind decoders. A noise-aware version of noise-robust instance optimality can be defined where for ≥ 0, δ > 0 we require

∀x ∈ E, ∀e ∈ F, e F ≤ ⇒ Ax -∆ δ, (Mx + e) G ≤ C 1 d E (x, Σ) + C 2 + δ. (23)
Of course, the existence of a noise-blind instance optimal decoder implies that of noise-aware decoders for every ≥ 0. The converse is indeed essentially true, up to the value of the constants C i :

Theorem 5. Suppose ∀ , δ > 0, there exists a noise-aware decoder ∆ δ, satisfying (23):

∀x ∈ E, ∀e ∈ F, e F ≤ ⇒ Ax -∆ δ, (Mx + e) G ≤ C 1 d E (x, Σ) + C 2 + δ.
Then M satisfies the Robust NSP [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF] with constants D 1 = C 1 and D 2 = 2C 2 . Therefore, by Theorem 4, there exists an instance optimal noise-blind decoder satisfying:

∀x ∈ E, ∀e ∈ F, Ax -∆ δ (Mx + e) G ≤ 2C 1 d E (x, Σ) + 4C 2 e F + δ.

Task-oriented instance optimality

In this section, we show that the generalized instance optimality as stated in ( 15) is essentially equivalent to the same property with A = I and a different choice for the pseudo-norm . G . Indeed, let's consider that one aims at reconstructing a certain feature Ax from the measurements Mx. If for any δ > 0 there exists an instance optimal decoder ∆ δ such that (15) is satisfied, then Theorem 1 ensures that NSP (3) is satisfied. Let's define the following pseudo-norm for any signal x ∈ E:

x = Ax G . ( 24
)
The following NSP is satisfied:

∀h ∈ ker(M), h ≤ Cd E (h, Σ -Σ). ( 25
)
Therefore, Theorem 2 ensures that there exists decoders ∆ δ : F → G instance optimal in the following sense:

x -∆ δ (Mx) ≤ 2Cd E (x, Σ) + δ. (26)
This means that if a family of decoders ∆ δ aimed at decoding a feature Ax is instance optimal for the pseudo-norm . G , then there exists a family of decoders ∆ δ aimed at decoding the signal x which is instance optimal for the pseudo-norm . with a similar constant (up to a factor 2). Conversely, if there exists a family of decoders ∆ δ aimed at decoding x which is instance optimal for the pseudo-norm . , then a simple rewriting of the IOP gives that the decoders ∆ δ = A∆ δ are instance optimal for the pseudo-norm . G .

Therefore, IOP with a task-oriented decoder is essentially equivalent to IOP with a standard decoder provided a suitable change in the pseudo-norm is performed. The same reasoning can be applied to deduce this equivalence for Robust IOP. As a consequence, we will only consider the case A = I in the remainder of the paper. 2 / 2 Instance Optimality

In this section, we suppose that E is a Hilbert space equipped with the norm . 2 and scalar product ., . , that F = R m and we consider a finite-dimensional subspace V of dimension n, on which we define the measure operator M. We are interested in the following question in the noiseless framework: Is it possible to have a "good" noiseless instance optimal decoder with . G = . E = . 2 in a dimensionality reducing context where m n? A result of [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF] states that in the usual sparse setting, one cannot expect to get a good instance optimal decoder if M performs a substantial dimensionality reduction, the best corresponding constant being n m . In [START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF], the authors prove that this lower bound on the constant holds in the case where Σ is a finite union of subspaces in finite dimension. Here, we are interested in a version of this result for the general case where Σ can be a more general subset of E. More precisely, we will give a sufficient condition on Σ under which the optimal 2 / 2 instance optimalityconstant is of the order of n m , thus preventing the existence of a 2 / 2 instance optimal decoder with small constant if m n.

Homogeneity of the NSP

In the case where . G , . E and . F are homogeneous with the same degree, the general NSP can be rewritten as an NSP holding on the cone R(Σ -Σ) generated by Σ -Σ, i.e., the set {λz|λ ∈ R, z ∈ Σ -Σ}.

Lemma 1. If . G and . E are homogeneous with the same degree, we have an equivalence between the NSP on Σ -Σ:

∀h ∈ N , h G ≤ Dd E (h, Σ -Σ), (27)
and the NSP on R(Σ -Σ):

∀h ∈ N , h G ≤ Dd E (h, R(Σ -Σ)). (28)
Similarly, if . G , . E and . F are homogeneous with the same degree, we have an equivalence between the robust NSP on Σ -Σ:

∀h ∈ E, h G ≤ D 1 d E (h, Σ -Σ) + D 2 Mh F , (29)
and the robust NSP on R(Σ -Σ):

∀h ∈ E, h G ≤ D 1 d E (h, R(Σ -Σ)) + D 2 Mh F . (30)
This lemma, which is valid even in the case where A is not the identity, shows that the NSP imposes a constraint on the whole linear cone spanned by the elements of Σ -Σ and not only on the elements themselves. Note that this equivalence is trivial in the case where Σ is a union of subspaces since Σ -Σ is already a cone in this case.

3.2

The optimal 2 / 2 NSP constant Remark 2. In the subsequent sections of the paper, we will assume that A = I (this implies G = E), so that one aims at reconstructing the actual signal.

In the 2 / 2 case, one can give a simple definition of the optimal NSP constant D * , that is the minimal real positive number D such that the 2 / 2 NSP is satisfied with constant D:

D * = inf {D ∈ R + |∀h ∈ N , h 2 ≤ Dd 2 (h, Σ -Σ)}. ( 31
)
This definition assumes that there exists some constant so that the NSP is satisfied. Using the NSP definition and Lemma 1, we get that

D * = sup h∈N sup z∈R(Σ-Σ) h 2 h -z 2 = sup h∈N \{0} sup z∈R(Σ-Σ) 1 h h 2 -z h 2 2 . ( 32
)
Denoting B 2 the unit ball for the 2 norm, we can rewrite this last expression as:

D * = sup h∈N ∩B2 sup z∈R(Σ-Σ) 1 h -z 2 = sup h∈N ∩B2 sup z∈R(Σ-Σ)∩B2 sup λ∈R 1 h -λz 2 . (33)
A simple study gives that if h 2 = z 2 = 1, then sup

λ∈R 1 h-λz 2 = 1 √ 1-h,z 2
, so that:

D * = sup h∈N ∩B2 sup z∈R(Σ-Σ)∩B2 1 1 -h, z 2 . ( 34
)
The contraposition of Theorem 1 gives the following result : if the NSP (3) is not satisfied for a certain constant D, then no decoder ∆ δ can satisfy instance optimality [START_REF] Candès | Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming[END_REF] with constant D. In the 2 / 2 case, considering

D < D * , h ∈ N ∩ B 2 and z ∈ R(Σ -Σ) ∩ B 2 such that h, z 2 ≥ 1 -1 D 2
, we can construct two vectors such that for any decoder, instance optimality with constant < √ D 2 -1 can only be satisfied for at most one of them. This will shed light on the link between NSP and IOP. We have z = z1-z2 z1-z2 2 for some z 1 , z 2 ∈ Σ. Let ∆ be a decoder. If ∆(Mz 1 ) = z 1 , then this vector prevents ∆ from being instance optimal. The same goes for z 2 if ∆(Mz 2 ) = z 2 . Now, let's suppose that z 1 and z 2 are correctly decoded. In this case, (z 1 + z 2 )/2 is decoded with a constant worse than √ D 2 -1, as depicted in Figure 4. Indeed, noting p = (z 1 + z 2 )/2 and defining the vectors p 1 and p 2 respectively as the orthogonal projections of z 1 and z 2 on the affine plane p + N , we must have ∆(Mp 1 ) = ∆(Mp 2 ). Denoting as p N ⊥ the orthogonal projection on N ⊥ , we have Here, z 1 and z 2 are two vectors in Σ such that z 1 -z 2 is well correlated with N , implying that at least one of the two vectors p 1 and p 2 , which are close to Σ but far from one another, will not be well decoded.

d 2 (p 1 , Σ) ≤ d 2 (p 1 , z 1 ) = p N ⊥ (z 2 -z 1 ) 2 /2. Similarly, N p 1 z 1 z 2 p 2 • p p + N
d 2 (p 2 , Σ) ≤ p N ⊥ (z 2 -z 1 ) 2 /2. The fact that ∆(Mp 1 ) = ∆(Mp 2 ) implies that there exists i ∈ {1, 2} such that p i -∆(Mp i ) 2 ≥ p 1 -p 2 2 /2 = p N (z 1 -z 2 ) 2 /2. Therefore, p i -∆(Mp i ) 2 d 2 (p i , Σ) ≥ p N (z 2 -z 1 ) 2 p N ⊥ (z 2 -z 1 ) 2 ≥ D 1 - 1 D 2 = D 2 -1. (35)
This illustrates the closeness between NSP and IOP: a vector of R(Σ -Σ) which is correlated with N can be used to define a couple of vectors such that for any decoder, one of the vectors will not be well decoded.

3.3

2 / 2 IO with dimensionality reduction

Main theorem

Let's now exploit the expression of D * to state the main result of this section: if R(Σ -Σ) contains an orthonormal basis of the finite-dimensional subspace V ⊂ E (or even a family of vectors that is sufficiently correlated with every vector of V ), then one cannot expect to get a 2 / 2 instance optimal decoder with a small constant while M substantially reduces the dimension of V . The fact that R(Σ -Σ) contains such a tight frame implies that the dimension of N cannot be too big without N being strongly correlated with Σ -Σ, thus yielding the impossibility of a good instance optimal decoder.

Before showing examples where this theorem applies, let's first state it and prove it.

Theorem 6. Suppose V is of dimension n and Σ -Σ contains a family z 1 , . . . , z n of unit-norm vectors of E satisfying ∀x ∈ V , n i=1 z i , x 2 ≥ K x 2 2 .
Then to satisfy the NSP on V , M must map V into a space of dimension at least 1

-1 K 1 -1 D 2 * n.
If the number of measurements m is fixed, then an 2 / 2 IO decoder must have a constant at least

1 1-K(1-m n ) .
In particular, if Σ -Σ contains an orthonormal basis of V , then K = 1 and the minimal number of measures to achieve NSP with constant D * is n/D 2 * . Similarly, if m is fixed so that m n, then a 2 / 2 instance optimal decoder has constant at least n m .

Examples

As discussed in the introduction, there is a wide range of standard models where Σ -Σ contains an orthonormal basis, and so where 2 / 2 IOP with dimensionality reduction is impossible. We provide here less trivial examples, where E = V is finite-dimensional.

Symmetric definite positive matrices with sparse inverse. Lemma 2. Consider E is the space of symmetric n-dimensional matrices, and Σ ⊂ E the subset of symmetric positive-definite matrices with sparse inverse and with sparsity constant k ≥ n + 2 (note that k ≥ n is necessary for the matrix to be invertible). The set Σ -Σ contains an orthonormal basis of E.

Proof. This orthonormal basis we consider is made of the n(n + 1)/2 matrices: E i,i and 1 √ 2 (E i,j + E j,i ) i =j , where E i,j is the matrix where the only nonzero entry is the (i, j) entry which has value 1.

First, consider

B i = I + E i,i
, where I is the identity matrix. Since B -1

i = I -1 2 E i,i is n-sparse, we have B i ∈ Σ. Since, I ∈ Σ, we have E i,i = B i -I ∈ Σ -Σ.
Now, consider the matrix C i,j = 2I + E i,j + E j,i . This matrix is symmetric and for

x = (x 1 , . . . , x n ) ∈ R n , we have x T C i,j x = 2( x 2
2 -x i x j ) ≥ 0, so that C i,j is semi-definite positive. We can remark that C i,j is invertible and that its inverse is 1 2

I + 1 6 (E i,i + E j,j ) -1 3 (E i,j + E j,i
), which is n + 2-sparse. The fact that C i,j is invertible implies that it is definite, so that C i,j ∈ Σ. Therefore, we can write E i,i + E j,j = C i,j -2I ∈ Σ -Σ. Since Σ is a positive cone, multiplying this equality by 1 √ 2 yields the desired result.

Low-rank and nonsparse matrices. In [START_REF] Candès | Robust principal component analysis?[END_REF], the authors consider a matrix decomposition of the form L + S, where L is low-rank and S is sparse. In order to give meaning to this decomposition, one must avoid L to be sparse. To this end, a "nonsparsity model" for low-rank matrices was introduced.

Let E be the space of complex matrices of size n 1 × n 2 . Given µ ≥ 1 and r ≤ min(n 1 , n 2 ), let Σ µ,r be the set of matrices of E of rank ≤ r satisfying the two following conditions (denoting the SVD of such a matrix by r k=1 σ k u k v * k , where σ k > 0 and the u k and v k are unit-norm vectors) :

1. ∀k, u k ∞ ≤ µr n1 and v k ∞ ≤ µr n2 .
2. Denoting U and V the matrices obtained by concatenating the vectors u k and v k , UV * ∞ ≤ µr n1n2 .

These two conditions aim at "homogenizing" the entries of U and V. Note that we necessarily have µ ≥ 1.

Lemma 3. Let E = M n1,n2 (C) and Σ µ,r be the subset of E containing the matrices satisfying the two above conditions (with µ ≥ 1 and r ≥ 1). Then Σ µ,r -Σ µ,r contains an orthonormal basis.

Proof. Since Σ µ,r contains the null matrix, it is sufficient to prove that Σ µ,r contains an orthonormal basis. Let {e k } n1 k=1 and {f } n2 =1 be the discrete Fourier bases of C n1 and C n2 , that is

e k = 1 √ n 1 [1, exp(2iπk/n 1 ), . . . , exp(2iπ(n 1 -1)k/n 1 )] T and f = 1 √ n 2 [1, exp(2iπ /n 2 ), . . . , exp(2iπ(n 2 -1) /n 2 )] T .
Then the n 1 n 2 rank-1 matrices of the form e k f * are elements of Σ µ,r since they obviously satisfy the two above conditions. But they also form an orthonormal basis of E, since each entry of e k f * is of module 1 √ n1n2 and that, denoting ., . the Hermitian scalar product on E,

e k f * , e k f * = n1-1 u=0 exp 2iπu k -k n 1 n2-1 v=0 exp 2iπv - n 2 = δ k k δ , (36)
proving that these matrices form an orthonormal basis of E.

4

The NSP and its relationship with the RIP

As we have seen in the previous section, one cannot expect to get 2 / 2 instance optimality in a dimensionality reduction context. This raises the following question: given pseudo-norms . G and . F defined respectively on E and F , is there a pseudo-norm . E such that IOP holds? We will see that this property is closely related to the RIP on M.

Generalized RIP and its necessity for robustness

The Restricted Isometry Property is a widely-used property on the operator M which yields nice stability and robustness results on the recovery of vectors from their compressive measurements. In the usual CS framework, the RIP provides a relation of the form (1 -δ) x G ≤ Mx F ≤ (1 + δ) x G for any vector x in Σ 2k . The norms . G and . F are usually both taken as the 2norm. A form of RIP can easily be stated in a generalized framework: we will say that M satisfies the RIP on Σ -Σ if there exists positive constants α, β such that

∀z ∈ Σ -Σ, α z G ≤ Mz F ≤ β z G . ( 37
)
Similarly to the sparse case, it is possible to make a distinction between lower-RIP (left inequality) and upper-RIP (right inequality). Let's remark that this definition has been stated for vectors of Σ -Σ: this choice is justified by the links between this formulation and the NSP, which will be discussed later in this section. Let's also note that this form of RIP encompasses several generalized RIP previously proposed, as mentioned in Section 1.3.4. Let's now suppose the existence of decoders robust to noise, that is for all δ > 0, ( 21) is satisfied for a certain ∆ δ . This property implies the Robust NSP [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF] with the same constants according to Theorem 3. By considering h ∈ Σ -Σ, the Robust NSP reads:

∀h ∈ Σ -Σ, h G ≤ D 2 Mh F . (38)
This is the lower-RIP on Σ -Σ, with constant 1/D 2 . The stability to noise therefore implies the lower-RIP on the set of differences of vectors of Σ, which is therefore necessary if one seeks the existence of a decoder robust to noise.

Infinite-dimensional examples

As mentioned in the introduction, we do not constrain the signal space to be finite-dimensional, so that we can apply our results in an infinite-dimensional framework.

4.3.1

Negative example: Sparse model in a separable Hilbert space

If E = L 2 ([0, 1]
) and {ϕ n } n∈N is an orthonormal basis of E, a typical measurement process of a signal x is to subsample along another orthonormal basis {Ψ n } n∈N . Typically, {ϕ n } is a wavelet basis and {Ψ n } a Fourier basis. In [START_REF] Adcock | Breaking the coherence barrier: A new theory for compressed sensing[END_REF], the authors argue that standard sparsity does not represent well natural signals, which are rather asymptotically sparse, that is more sparse at fine levels than at coarse levels. They propose an asymptotic sparsity model with different levels of sparsity on different scales. Indeed, as the authors mention in their paper, a standard sparsity model Σ with respect to basis {ϕ n } cannot yield uniform recovery for the L 2 norm: this is an obvious consequence of Theorem 6 if d E is the L 2 distance and it is actually true for any other distance. Indeed, the NSP can never be satisfied since one has ϕ n + ϕ n+1 2 = √ 2 for all n (since the family {ϕ n } is orthonormal) while the right hand side term of the NSP for

h n = ϕ n + ϕ n+1 is equal to d(h n , Σ -Σ) + Mh n 2 = Mh n 2 , (45)
which goes to 0 when n → ∞ (since M is continuous).

Positive example: Topological RIP result for Σ of finite box-counting dimension

Even though the IOP cannot be satisfied for the standard sparse model in a Hilbert space, it does not mean IOP is impossible for all models in an infinite-dimensional space. Let's mention the following topological result, which is Theorem 8.1 in [START_REF] James C Robinson | Dimensions, Embeddings, and Attractors. Cambridge Tracts in Mathematics[END_REF] and ensures that a RIP is satisfied in some settings:

Theorem 8. Let Σ be a compact subset of a Banach space B supplied with norm . B . Suppose Σ has finite (upper) box-counting dimension d. Then for any m > 2d, any norm . on R m , and any θ satisfying

0 < θ < m -2d m(1 + d) ,
there exists a prevalent set5 of continuous linear operators M : B → R m such that for any x, y ∈ Σ,

C M x -y B ≤ Mx -My θ . (46)
This theorem essentially says that if Σ has finite upper box-counting dimension 6 , then a lower-RIP is satisfied for a prevalent set of operators M with the pseudo-norms . B and . θ -this last one being a pseudo-norm since θ ≤ 1. According to the previous section, this implies an IOP with the corresponding M -norm, that is the existence of a family of decoders ∆ δ such that for all x ∈ E, e ∈ F and z ∈ Σ:

x -∆(Mx) B ≤ 2d M (x, Σ) + 2 C M e θ + δ. (47)
We necessarily have θ ≤ 1 d , meaning the exponent drops to 0 as d grows, and therefore the corresponding IOP becomes much less powerful with a high-dimensional set Σ (in the sense of the upper box-counting dimension). However, this essentially proves that uniform instance optimality is possible even in infinite dimensions with appropriate Σ and pseudo-norms. Furthermore, weakening the existence of a prevalent set of operators M to the existence of an operator M or a certain class of such operators satisfying a Robust IOP has the potential to yield IOP with better pseudo-norms.

As an example of an infinite-dimensional model with finite upper box-counting dimension, let's consider the problem experimented in [START_REF] Bourrier | Compressive Gaussian Mixture Estimation[END_REF]: we consider E = L 1 (R n ) ∩ L 2 (R n ) and aim at decoding a probability density p ∈ E from a linear measurement Mp. The a priori on p is that it can be expressed as a linear combination of a few densities taken in a set P. In [START_REF] Bourrier | Compressive Gaussian Mixture Estimation[END_REF], the authors considered P as a set of isotropic Gaussians, that is

P = p µ : x → exp -x -µ 2 2 |µ ∈ R n . (48)
Denoting Σ k (P) the compact set of convex linear combinations of k elements in P with µ 2 ≤ C, the upper-box counting dimension of Σ k (P) is upper bounded by k(n + 1), so that a prevalent set of linear operators satisfies the IOP (47) as soon as the number of measurements satisfies m > 2k(n + 1).

This example shows that one can obtain uniform IOP for an infinite-dimensional model which "spans in an infinite number of directions", such as the aforementioned model Σ k (P). We hope that more precise characterizations on this kind of IOP can be obtained in this general framework.

Upper-bound on the M -norm by an atomic norm

As we have seen, provided a lower-RIP on Σ -Σ, an NSP can be derived with the M -norm as . E . However, this may look like a tautology since the M -norm explicitly depends on M. Hence, one may wonder if this NSP is of any use. We will prove in the following that provided an upper-RIP on a certain cone Σ (which can be taken as RΣ), a more natural upper bound can be derived by bounding the M -norm with an atomic norm [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF]. In particular, this type of inequality applied to the usual k-sparse vectors and low-rank matrices models give, under standard RIP conditions, instance optimality upper bounds with typical norms.

We will suppose in this section that . G is a norm.

The atomic norm . Σ

Let Σ be a subset of E and let E be the closure of span(Σ ) with respect to the norm . G . For

x ∈ E , one can define the "norm" x Σ by:

x Σ := inf +∞ k=0 x k G : ∀k, x k ∈ RΣ and x - K k=0 x k G → K→+∞ 0 . (49)
Remark that there may be some vectors x for which x Σ = +∞, if +∞ k=0 x k G = +∞ for any decomposition of x as an infinite sum of elements of RΣ . However, the set V = {x ∈ E| x Σ < +∞} is a normed subspace of E which contains Σ [START_REF] Devore | Some remarks on greedy algorithms[END_REF]. In the following, we assume that V = E. Note that this norm can be linked to atomic norms defined in [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF] by considering A as the set of normalized elements of Σ with respect to . G . Now suppose M satisfies an upper-RIP on Σ , so that

∀x ∈ Σ , Mx F ≤ β x G . (50)
For x ∈ E admitting a decomposition +∞ k=0 x k on RΣ , we can therefore upper bound Mx F by

+∞ k=0 Mx k F ≤ β +∞ k=0 x k G .
This inequality is valid for any decomposition of x as a sum of elements of RΣ , so that Mx F ≤ β x Σ . Therefore, under these hypotheses,

∀x ∈ E, x M ≤ x G + β α x Σ ≤ 1 + β α x Σ . (51)
In particular, we have the following result:

Theorem 9. Suppose M satisfies the lower-RIP on Σ -Σ with constant α and the upper-RIP on

Σ with constant β, that is ∀x ∈ Σ -Σ, α x G ≤ Mx F ( 52
)
and ∀x ∈ Σ, Mx F ≤ β x G . ( 53
)
Then for all δ > 0, there exists a decoder ∆ δ satisfying

∀x ∈ E, ∀e ∈ F, x -∆ δ (Mx + e) G ≤ 2 1 + β α d Σ (x, Σ) + 2 α e E + δ, (54)
where d Σ is the distance associated to the norm . Σ .

Remark 3. Note that these results can be extended with relative ease to the case where . G is not necessarily homogeneous but p-homogeneous, that is λx G = |λ| p x G .

Study of . Σ in two usual cases

We now provide a more thorough analysis of the norm . Σ for usual models which are sparse vectors and low-rank matrices. In particular, we give a simple equivalent of this norm involving usual norms in the case where . G = . 2 (for matrices, this is the Frobenius norm). The norm . Σ relies on the decomposition of a vector as a sum of elements of RΣ. When Σ is the set of k-sparse vectors or the set or matrices of rank k, there are particular decompositions of this type:

• In the case where Σ is the set of k-sparse vectors, a vector x can be decomposed as ∞ j=1 x j , where all x j are k-sparse vectors with disjoint supports, which are eventually zero, and such that any entry of x j does not exceed any entry of x j-1 (in magnitude). This is a decomposition of x into disjoint supports of size k with a nonincreasing constraint on the coefficients.

• Similarly, in the case where Σ is the set of matrices of rank k and N is a matrix, the SVD of N gives a decomposition of the form N = ∞ j=1 N j , where the N j are rank k, eventually zero matrices such that any singular value of N j does not exceed any singular value of N j-1 .

For j ≥ 2, we can upper bound the quantity x j 2 using the assumption on the particular decomposition:

x j 2 ≤ √ k x j ∞ ≤ √ k xj-1 1 k = xj-1 1 √ k . Similarly, N j 2 ≤ Nj-1 * √ k
, where

. * is the trace norm, defined as the sum of singular values. We can therefore, in both cases, upper bound the norm . Σ . In the case of k-sparse vectors, this gives:

x Σ ≤ x 1 2 + j≥1 x j 1 √ k ≤ x 2 + x 1 √ k . (55)
In the case of matrices of rank k, this gives:

N Σ ≤ N 1 2 + j≥1 N j 1 √ k ≤ N F + N * √ k . ( 56
)
We can also upper bound the right hand side of these equations by O( . Σ ) with a small constant, which will prove that the norms defined in these equations are of the same order. Indeed, a simple application of the triangle inequality gives us first that x 2 ≤ x Σ and N F ≤ N Σ . Then, considering a decomposition of x as a sum of k-sparse vectors j≥1 x j , we get

x 1 √ k ≤ j≥1 x j 1 √ k ≤ j≥1 x j 2 (57)
(indeed, each x j can be viewed as a k-dimensional vector and we have for such a vector

x j 1 ≤ √ k x j 2 ). Similarly, N * √ k ≤ j≥1 N j F . (58)
Since these upper bounds are satisfied for any decomposition, they can be replaced respectively by x Σ and N Σ . Finally, we have

x 2 + x 1 √ k ≤ 2 x Σ and N F + N * √ k ≤ 2 N Σ . (59)
We have thus shown:

Lemma 4. When Σ is the set of k-sparse vectors, the norm . Σ satisfies

• Σ ≤ • 2 + • 1 √ k ≤ 2 • Σ . ( 60
)
When Σ is the set of rank-k matrices, it satisfies

• Σ ≤ • F + • * √ k ≤ 2 • Σ . (61)
We can thus remark that for these two standard models, the norm . Σ can easily be upper bounded by usual norms under RIP conditions, yielding an IOP with a usual upper bound. We can also note that stronger RIP conditions can yield a stronger result: in [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF], the author proves that under upper and lower-RIP on Σ -Σ with Σ being the set of k-sparse vectors, an instance optimal decoder can be defined as the minimization of a convex objective: the 1 norm, which appears as strongly connected to the norm • Σ . One may then wonder if a generalization of such a result is possible: when can an instance optimal decoder be obtained by solving a convex minimization problem with a norm related to • Σ ?

Discussion and outlooks on Instance Optimality

Let's now summarize the results and give some insights on interesting future work. As has been detailed throughout the paper, Instance Optimality is a property presenting several benefits:

• It can be defined in a very general framework, for any signal space, signal model and pseudonorms, as well as for both noiseless and noisy settings.

• It is a nice uniform formulation of the "good behavior" of a decoder and thus of the wellposedness of an inverse problem.

• It can be linked to Null Space Property and Restricted Isometry Property, which provide necessary and/or sufficient conditions for the existence of an Instance Optimal decoder.

We now present some immediate outlooks and interesting open questions related to instance optimality and to the results presented in this paper.

Condition for the well-posedness of the "optimal" decoder. We have seen that for general models Σ, an additionnal term δ appears in the right hand side term of the instance optimality inequality (( 15),( 21)), reflecting the fact that the minimal distance of the "optimal" decoder (69) may not be reached at a specific point. However, as mentioned in Property 1, this additive constant can be dropped in the noiseless case provided Σ + N is a closed set. One can then wonder if there exists a similar condition (e.g., a sort of local compactness property) in the noisy case for which one can drop the constant δ and get a more usual instance optimality result.

Compressed graphical models. As has been mentioned in Section 1.3.3, the case where Σ is the set of symmetric definite positive square matrices with sparse inverse is related to high-dimensional Gaussian graphical models. In Lemma 2, we showed this type of models fits in our theory since we could apply Theorem 6 in this case, proving the impossibility of 2 / 2 IOP in a dimension-reduction case. Yet, as for other signal models, can Gaussian graphical models satisfy some IOP/NSP with different norms in a compressive framework?

Guarantees for signal-space reconstructions and more. When D is a redundant dictionary of size d × n and the signals of interest are vectors of the form z = Dx, where x is a sparse vector, traditional reconstruction guarantees from y = Mz assume the RIP on the matrix MD. This is often too restrictive: for example when D has strongly correlated columns, failure to identify x from y does not necessarily prevent one from correctly estimating z. Recent work on signal-space algorithms [START_REF] Davenport | Signal space cosamp for sparse recovery with redundant dictionaries[END_REF] has shown that the D-RIP assumption on M is in fact sufficient.

The framework presented in this paper offers two ways to approach this setting:

• Considering Σ = Σ k as the set of k-sparse vectors of dimension n and A = D, the upper bound on the reconstruction error is of the form d E (x, Σ k ). Signal-space guarantees can be envisioned by choosing a metric • E = D • .

• Considering Σ = DΣ k as the set of d-dimensional vectors that have a k-sparse representation in the dictionary D and A = I, the upper bound is of the form d (z, DΣ k ).

In [START_REF] Needell | Stable image reconstruction using total variation minimization[END_REF], the authors propose a result similar to instance optimality by upper bounding, for a Total Variation decoder, the reconstruction error of an image X from compressive measurement by a quantity involving d 1 (∇X, Σ k ), where ∇ is the gradient operator, Σ k the k-sparse union of subspaces (in the gradient space) and d 1 is the 1 distance. This quantity is therefore the distance between the gradient of the image and the k-sparse vectors model. Can such a bound be interpreted in our framework, and possibly be generalized to other types of signals?

Task-oriented decoders versus general purpose decoders. We already mentioned two very different application set-ups, in medical imaging and audio source separation, where only parts of the original signals need to be recovered. One can think of other, more dramatic, cases where only task-oriented linear features should be reconstructed. One such situation is met in current image classification work-flows. Indeed, most recent state-of-art image classification methods rely on very high-dimensional image representation (e.g., so called Fisher vectors, of dimension ranging from 10,000 to 200,000) and conduct supervised learning on such labeled signals by means of linear SVMs [START_REF] Sanchez | Image classification with the fisher vector: Theory and practice[END_REF]. Not only this approach yields top-ranking performance in terms of classification accuracy on challenging image classification benchmarks, but it also permits very large scale learning thanks to the low complexity of linear SVM training and its efficient implementations, e.g., with stochastic gradient descent. For each visual category to recognize, a linear classifier w is learned, which associates to an input image with representation x the score w T x. The single or multiple labels that are finally assigned to x by the system depend on the scores provided by all trained classifiers (typically from 10 to 100), hence on a vector of the form Ax, where each row of A is one one-vs-all linear SVM. In this set-up, the operator A implies a dramatic dimension reduction. For very large scale problems of this type, storing and manipulating original image signatures in the database can become intractable. The theoretical framework proposed in this paper might help designing new solutions to this problem in the future. In particular, it will provide tools to answer the following questions:

• A being given (learned on a labeled subset of the database): can one design a compressive measurement operator M such that the "classifiers" scores can be recovered directly from the compressed image signature Mx, hence avoiding the prior reconstruction of the highdimensional signal x?

• M being given ("legacy" compressed storing of image signatures): what are the linear classifier collections that can be precisely emulated in the compressed domain thanks to a good decoder ∆?

Note that this classification-oriented set-up might call for a specific norm . G on the output of a linear score bank. Another important domain of application that might benefit from both aspects (general purpose and task-oriented) of our work is data analysis under privacy constraints. Two scenarii can be envisioned, where our framework could help decide whether or not such constraints are compatible with the analysis of interest:

• General purpose scenario: given a linear measurement operator M of interest for further analysis, can one guarantee that there is no decoder permitting good enough recovery of original signals?

• Task-oriented scenario: the operator M serving as a means to obfuscate original signals such that critical information can't be recovered, let's consider a specific analysis task on original Worst case versus average case instance optimality. The raw concept of Instance Optimality has a major drawback: the uniformity of the bound may impose, in some settings, a large global instance optimality constant whereas the inverse problem is well posed for the vast majority of signals. Let's consider the example depicted in Figure 5, where the signal space E is of dimension 2, the signal model Σ is a point cloud mostly concentrated along the line D and the measurement operator M is the orthogonal projection on D. The figure depicts the ratio (approximation error)/(distance to model) for each x ∈ R 2 . The optimal constant, which is the supremum of these ratios, is infinite: the ratio actually goes to infinity in the vicinity of the point p. However, for the vast majority of vectors, the ratio is rather low (the blue section covers most of the space).

An interesting outlook to circumvent this pessimistic "worst-case" phenomenon is to consider a probabilistic formulation of instance optimality, as in [START_REF] Cohen | Compressed sensing and best k-term approximation[END_REF]: given Ω a probability space with probability measure P , and considering M as a random variable on Ω, is there a decoder ∆(.|M) (which computes an estimate given the observation and the particular draw of the measurement operator M) such that for any x ∈ E, the instance optimality inequality

x -∆(Mx|M) G ≤ Cd E (x, Σ) (62)
holds with high probability on the drawing of M? A particular challenge would be to understand in which dimension reduction scenarii there exists both a probability measure and a decoder with the above property. Another possible formulation of probabilistic instance optimality is to define a probability distribution on the signal space and to upper bound the average reconstruction error of the vectors, as in [START_REF] Yu | Statistical compressed sensing of gaussian mixture models[END_REF].

Proof. Let Φ be defined on V + W by Φ(u) = ux . Since Φ(u) ≥ ux , we have lim u →+∞ Φ(u) = +∞, so that ∃M > 0 such that u > M ⇒ Φ(u) ≥ x . The set B = {u ∈ V + W, u ≤ M } is a closed ball of V + W and is thus a compact. Since Φ is continuous, Φ has a minimizer v on B. 0 ∈ B, so that Φ(0) = x ≥ Φ(v). For all u such that u > M , we have Φ(u) ≥ x ≥ Φ(v), so that v is a global minimizer of Φ. We therefore have ∀(u, w) ∈ V × W, xv ≤ x -(u + w) . The vector v can be written f + g with f ∈ V and g ∈ W , so that the vector y = xf , which belongs to x + V , satisfies d(x -f , W ) = (x -f ) -g = d(x, V + W ) = d(x + V, W ), which proves the result.

Let Σ = ∪ i∈J1,pK V i , where V i are subspaces of R n . Lemma 5 applied to V = N and W = V i ensures the existence of x i ∈ (x + N ) such that d E (x i , V i ) = d E (x + N , V i ). Therefore, ∆(Mx) can be defined as argmin {xi,i∈J1,pK} d E (x i , V i ) and satisfies d E (∆(Mx), Σ) = d E (x + N , Σ), so that the decoder ∆(Mx) = argmin z∈(x+N ) d(z, Σ) is properly defined. In particular, this applies to the decoder [START_REF] Candès | Robust principal component analysis?[END_REF].

B Proof of Theorem 1

Let δ > 0 and ∆ δ and C be such that (15) holds ∀x ∈ E. Let h ∈ N . Then ∃h 0 ∈ Σ -Σ such that d E (h, h 0 ) ≤ d E (h, Σ -Σ) + δ. Let h 0 = h 1 -h 2 with h 1 , h 2 ∈ Σ, and h 3 = hh 0 . Since h ∈ N , we have:

M(h 1 + h 3 ) = Mh 2 . (63)
Applying ( 15) to x = h 2 ∈ Σ and using the fact that 0 E = 0, we get:

Ah 2 -∆ δ (Mh 2 ) G ≤ δ. (64)
Let's now find an upper bound for Ah G :

Ah G = A(h 1 -h 2 + h 3 ) G = A(h 1 + h 3 ) -∆ δ (M(h 1 + h 3 )) -Ah 2 + ∆ δ (M(h 1 + h 3 )) G ≤ A(h 1 + h 3 ) -∆ δ (M(h 1 + h 3 )) G + Ah 2 -∆ δ (M(h 1 + h 3 )) G , (65)
where we have used ( 13) and ( 14) for the last inequality. Combining (63) and (64), we get that:

Ah 2 -∆ δ (M(h 1 + h 3 )) G ≤ δ. (66)
Applying ( 15) to x = h 1 + h 3 , we get:

A(h 1 + h 3 ) -∆ δ (M(h 1 + h 3 )) G ≤ Cd E (h 1 + h 3 , Σ) + δ ≤ C h 3 E + δ = Cd E (h, h 0 ) + δ ≤ Cd E (h, Σ -Σ) + (C + 1)δ. ( 67
)
Combining (65), (66) and (67) gives:

Ah G ≤ Cd E (h, Σ -Σ) + (C + 2)δ. ( 68
)
(68) is valid for all δ > 0, so it is valid for δ = 0. This gives us the property (3) with D = C.

C Proof of Theorem 2

Let's first assume that ( 16) holds and define the following decoder on F :

∆ (Mx) = argmin z∈(x+N ) d E (z, Σ). ( 69
)
Note that the decoder is well defined, since Mx 1 = Mx 2 ⇒ x 1 + N = x 2 + N . For x ∈ E, we have x -∆ (Mx) ∈ N , so that (3) yields:

Ax -A∆ (Mx) G ≤ Dd E (x -∆ (Mx), Σ -Σ)
≤ Dd E (x, Σ) + Dd E (∆ (Mx), Σ)

≤ 2Dd E (x, Σ), ( 70
)
where we have used [START_REF] Candès | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF] for the second inequality. The last inequality comes from (69), which yields d E (∆ (Mx), Σ) ≤ d E (x, Σ). Therefore, by posing ∆ = A∆ , we get (2).

Let's return to the general case, and consider ν > 0. We define the following decoder on F :

∆ ν (Mx) ∈ {u ∈ (x + N )|d E (u, Σ) ≤ d E (x + N , Σ) + ν}. (71)
Note that this set may not contain a unique element and thus this definition relies on the axiom of choice.

For x ∈ E, we have again x -∆ ν (Mx) ∈ N , so that by (3):

Ax -A∆ ν (Mx) G ≤ Dd E (x -∆ ν (Mx), Σ -Σ)
≤ Dd E (x, Σ) + Dd E (∆ ν (Mx), Σ)

≤ 2Dd E (x, Σ) + Dν, (72)
where we have used [START_REF] Candès | Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[END_REF]

G Proof of Lemma 1

The two equivalences are very similar to prove, so that we will only prove the first. ( 28) ⇒ (27) is obvious. Let's now suppose [START_REF] Giryes | Greedy-Like Algorithms for the Cosparse Analysis Model. partially funded by the ERC, PLEASE project[END_REF], so that:

∀h ∈ N , ∀z ∈ Σ -Σ, h G ≤ D h -z E . (78)
By homogeneity, we also have:

∀λ ∈ R * , ∀h ∈ N , ∀z ∈ Σ -Σ, λh G ≤ D λh -z E , (79)
so that:

∀λ ∈ R * , ∀h ∈ N , ∀z ∈ Σ -Σ, h G ≤ D h -z/λ E . (80)
This last inequality yields [START_REF] Gribonval | Highly sparse representations from dictionaries are unique and independent of the sparseness measure[END_REF].

H Proof of Theorem 6

Let's note M = M |V and N = N ∩ V . Let m be the dimension of the range of M, so that N is of dimension n -m. Let h 1 , . . . , h n-m be an orthonormal basis of N . We have:

n -m = n-m j=1 h j 2 2 ≤ 1 K n-m j=1 n i=1 h j , z i 2 . (81)
Using [START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF], we get that, for all h ∈ N and unit-norm vector z ∈ Σ -Σ, h, z 2 ≤ 1 -1

D 2 * h 2
2 . If we denote by p N the orthogonal projection on N and apply this inequality with h = p N (z i ) = n-m j=1 h j , z i h j and z = z i , we get that p N (z i ) 4 2 ≤ 1 -

n -m ≤ n K 1 - 1 D 2 * , (82)
so that:

m ≥ n 1 - 1 K 1 - 1 D 2 * . ( 83
)
We get the lower bound on D 2 * by isolating it in the inequality.

I Proof of Theorem 7

Let h ∈ E and z ∈ Σ -Σ. We have the following inequalities:

h G ≤ h -z G + z G ≤ h -z G + 1 α Mz F , (84)
where we have used the lower-RIP for the second inequality.

Figure 1 :

 1 Figure 1: Illustration of several CS models. From left to right: k-sparse vectors, union of subspaces, smooth manifold and point cloud.

Figure 2 :

 2 Figure2: Illustration of the proposed generalized setting. The signals belong to the space E, supplied with a pseudo-norm . E used to measure the distance from a vector to the model Σ containing the signals of interest. E is mapped in the measure space F by the operator M and the measure is perturbed by an additive noise e. The space F is supplied with a pseudo-norm . F . The feature space G, supplied with a norm . G , is composed of vectors obtained by applying a linear operator A to the signals in E. These feature vectors are the vectors one wants to reconstruct from the measures in M by applying a decoder ∆. The reconstruction error for the vector x and noise e is therefore Ax -∆(Mx + e) G . Note that in the case where E = G and A = I, the decoder is aimed at reconstructing exactly the signals.

3

 3

Figure 4 :

 4 Figure 4: Illustration of the impact of the correlation between N and Σ -Σ on instance optimality.Here, z 1 and z 2 are two vectors in Σ such that z 1 -z 2 is well correlated with N , implying that at least one of the two vectors p 1 and p 2 , which are close to Σ but far from one another, will not be well decoded.

Figure 5 :

 5 Figure 5: Drawback of uniform instance optimality in a simple case: the model Σ (Left) is the set of black points including those on D and the point p and the operator M is the 1-dimensional orthogonal projection on the horizontal axis. If we choose ∆ as the pseudo-inverse of M, the depicted IO ratio (Right) is low on most of the space, but the uniform constant is infinite.

  again for the second inequality. The last inequality comes from (71), which yields d E (∆ ν (Mx), Σ) ≤ d E (x, Σ) + ν. Therefore, by posing ∆ δ = A∆ δ/D , we get[START_REF] Candès | Phaselift: Exact and stable signal recovery from magnitude measurements via convex programming[END_REF].D Proof of Proposition 1Let x ∈ E and ν > 0. If 0 = d E (x + N , Σ) = d E (x, Σ + N ), then since Σ + N is a closed set,x ∈ Σ + N , and therefore (x + N ) ∩ Σ = ∅. In this case, we define ∆ ν (Mx) as any element of (x + N ) ∩ Σ.Ifd E (x + N , Σ) > 0, then we define ∆ ν (Mx) ∈ {u ∈ (x + N )|d E (u, Σ) ≤ (1 + ν)d E (x + N , Σ)}. This provides a consistent definition of ∆ ν . Let's remark that for all x ∈ E, d E (∆ ν (Mx), Σ) ≤ (1 + ν)d E (x + N , Σ) ≤ (1 + ν)d E (x, Σ). For x ∈ E, x -∆ ν (Mx) ∈ N , so that (3) gives: Ax -A∆ ν (Mx) G ≤ Dd E (x -∆ ν (Mx), Σ -Σ) ≤ Dd E (x, Σ) + Dd E (∆ ν (Mx), Σ) ≤ (2 + ν)Dd E (x, Σ). (73)Defining ∆ δ = A∆ ν , we get the desired result.

By contrast, linear inverse problems usually refer to a setup where one aims at reconstructing a signal from its measurements by a given operator (e.g. imposed by the underlying physics), which may be dimensionality-reducing.

The prefix "M-" should be thought as "Measurement-related norm" since in other works the measurement matrix may be denoted by other letters.

In fact, unlike the NSP (3),[START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF] is not purely a property of the null space N even though it implies the NSP. The name Robust NSP is thus somewhat improper, but has become a standard for this type of property.

to highlight its dependency on the Measurement operator

A prevalent set being a set which complementary is negligible in a certain sense. Definition is given in[START_REF] James C Robinson | Dimensions, Embeddings, and Attractors. Cambridge Tracts in Mathematics[END_REF].

This is a notion of dimension defined by asymptotic behavior of -covers.

Acknoledgements

This work was supported in part by the European Research Council, PLEASE project (ERC-StG-2011-277906). The authors also wants to thank the anonymous reviewers for their remarks about instance optimality in infinite dimensions and for providing the example given in Section 4.3.1.

M -norm instance optimality with the RIP

The lower-RIP is necessary for the existence of a Robust instance optimal decoder, but what can we say this time if we suppose that M satisfies the lower-RIP on Σ -Σ with constant α, that is ∀z ∈ Σ -Σ, α z G ≤ Mz F ? We will prove that in both the noiseless and the noisy cases, this implies the IOP with norms . G and . M , the latter being called "M -norm" 4 and involving . G and . F .

Let's define the M -norm on E as the following quantity, extending its definition for 2 norms in [START_REF] Peleg | Compressed sensing and best approximation from union of subspaces: Beyond dictionaries[END_REF] and its implicit appearance in the proof of early results of the field [START_REF] Candès | The restricted isometry property and its implications for compressed sensing[END_REF]:

Note that the term M -norm should be understood as M -pseudo-norm in the general case: if . F and . G satisfy the properties listed in Table 1, then . M satisfies the same properties as . G . However, when . G and . F are norms, . M is also a norm. We will note d M (., .) its associated (pseudo-)distance. The following theorem states that this . M allows one to derive an NSP from the lower-RIP on Σ -Σ.

Theorem 7. Let's suppose that M satisfies the lower-RIP on Σ -Σ with constant α (left inequality of (37)). Then the following Robust NSP is satisfied:

In particular, the following regular NSP is satisfied:

Therefore, if M satisfies the lower-RIP on Σ -Σ with constant α, then for all δ > 0, there exists a noise-robust instance optimal decoder ∆ δ satisfying the following property (Theorem 4):

Note that in [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF], the author explored the implication of a lower-RIP on Σ -Σ for the case where Σ is an arbitrary UoS and . G / . F are the 2 norm. He proved that this generalized lower-RIP implies the following IOP: for all δ > 0, there exists a decoder ∆ δ such that

In this set-up, the instance optimality in equation ( 42) can be reformulated as

Comparing these two instance optimality results, we can remark that the one in [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF] is slightly tighter. This is merely a consequence of the difference in our method of proof, as we add the NSP as an intermediate result to prove instance optimality. The upper bound in [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF] can also be derived in our case with the same proof layout if we suppose the lower-RIP. Compared to [START_REF] Blumensath | Sampling and reconstructing signals from a union of linear subspaces[END_REF], our theory deals with general (pseudo-)norms and sets Σ beyond Union of Subspaces.

A Well-posedness of the finite UoS decoder

In this section, we will prove that if Σ is a finite union of subspaces in R n and . a norm on R n , then the quantity arg min z∈(x+N ) d(z, Σ), where d is the distance relative to . , is defined for all x ∈ R n .

Let's first prove the following lemma:

E Proof of Theorem 3 and Theorem 5

Let's first remark that applying (21) (resp. ( 23)) with x = z ∈ Σ and e = 0 yields Az -∆ δ (Mz) G ≤ δ and Az -∆ δ, (Mz) G ≤ C 2 + δ for any z ∈ Σ, ≥ 0, where we have used the fact that 0 F = 0. Let h ∈ E and z ∈ Σ. We apply (21) (resp. ( 23)) with x = zh, e = Mh, and = Mh F , which yields:

Let's remark that ( 13) and ( 14) imply

This last inequality is valid for all z ∈ Σ, therefore [START_REF] Donoho | Compressed sensing[END_REF] implies:

where we have used [START_REF] Candès | Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[END_REF] for the last inequality. Similarly, [START_REF] Eldar | Block-sparse signals: uncertainty relations and efficient recovery[END_REF] implies

We conclude by using the fact that (74) and (75) hold for all δ > 0.

F Proof of Theorem 4

Let's suppose [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF] and define for δ > 0 the decoder ∆ δ : F → E such that ∀y ∈ F :

Let's prove that this decoder meets property [START_REF] Donoho | Compressed sensing[END_REF]. Let x ∈ E and e ∈ F . Applying [START_REF] Eftekhari | New analysis of manifold embeddings and signal recovery from compressive measurements[END_REF] with h = x -∆ δ (Mx + e), we get:

where we have used ( 13) and ( 14) for the second inequality and the last inequality is a consequence of (76).

Posing ∆ δ = A∆ δ proves [START_REF] Donoho | Compressed sensing[END_REF] with C 1 = 2D 1 and C 2 = 2D 2 .

A similar consideration on Mz yields:

Substituting (85) into (84), we get:

Taking the infimum of the right hand-side quantity over all z ∈ Σ -Σ, one gets the desired Robust NSP: