Claire Boyer

Antonin Chambolle

Yohann De Castro

Vincent Duval

Frédéric De Gournay

Pierre Weiss

On Representer Theorems and Convex Regularization

Keywords: Inverse problems, Convex regularization, Representer theorem, Vector space, Total variation

We establish a general principle which states that regularizing an inverse problem with a convex function yields solutions which are convex combinations of a small number of atoms. These atoms are identified with the extreme points and elements of the extreme rays of the regularizer level sets. An extension to a broader class of quasiconvex regularizers is also discussed. As a side result, we characterize the minimizers of the total gradient variation, which was still an unresolved problem.

Introduction

Let E denote a real vector space. Let Φ : E → R m be a linear mapping called sensing operator and u ∈ E denote a signal. The main results in this paper describe the structural properties of certain solutions of the following problem:

inf u∈E f (Φu) + R(u), (1)
where R : E → R∪{+∞} is a convex function called regularizer and f is an arbitrary convex or non-convex function called data fitting term. In many applications, one looks for "sparse solutions" that are linear sums of a few atoms. This article investigates the theoretical legitimacy of this usage.

Representer theorems and Tikhonov regularization

The name representer theorem comes from the field of machine learning [START_REF] Scholkopf | Learning with kernels[END_REF]. To provide a first concrete example 1 , assume that Φ ∈ R m×n is a finite dimensional measurement operator and L ∈ R p×n is a linear transform. Solving an inverse problem using Tikhonov regularization amounts to finding the minimizers of

min u∈R m 1 2 Φu -y 2 2 + 1 2 Lu 2 2 . (2)
Provided that kerΦ ∩ kerL = {0}, it is possible to show that, whatever the data y is, solutions are always of the form

u = m i=1 α i ψ i + u K , (3)
where u K ∈ ker(L) and ψ i = (Φ T Φ + L T L) -1 (φ i ), where φ T i ∈ R n is the i-th row of Φ. This result characterizes structural properties of the minimizers without actually needing to solve the problem. In addition, when E is an infinite dimensional Hilbert space, Equation (3) sometimes allows to compute exact solutions, by simply solving a finite dimensional linear system. This is a critical observation that explains the practical success of kernel methods and radial basis functions [START_REF] Wendland | Scattered data approximation[END_REF].

Representer theorems and convex regularization

The Tikhonov regularization (2) is a powerful tool when the number m of observations is large and the operator Φ is not too ill-conditioned. However, recent results in the fields of compressed sensing [START_REF] Donoho | Compressed sensing[END_REF], matrix completion [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] or super-resolution [START_REF] Tang | Compressed sensing off the grid[END_REF][START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF] -to name a few -suggest that much better results may be obtained in general, by using convex regularizers, with level sets containing singularities. Popular examples of regularizers in the finite dimensional setting include the indicator of the nonnegative orthant [START_REF] Donoho | Sparse nonnegative solution of underdetermined linear equations by linear programming[END_REF], the 1 -norm [START_REF] Donoho | Compressed sensing[END_REF] or its composition with a linear operator [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF] and the nuclear norm [START_REF] Candès | Exact matrix completion via convex optimization[END_REF]. Those results were nicely unified in [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF] and one of the critical arguments behind all these techniques is a representer theorem of type [START_REF] Aliprantis | Infinite Dimensional Analysis: A Hitchhiker's Guide[END_REF]. In most situations however, this argument is only implicit. The main objective of this paper is to state a generalization of (3) to arbitrary convex functions R. It covers all the aforementioned problems, but also new ones for problems formulated over the space of measures.

To the best of our knowledge, the name "representer theorem" is new in the field of convex regularization and its first mention is due to Unser, Fageot and Ward in [START_REF] Unser | Splines are universal solutions of linear inverse problems with generalized tv regularization[END_REF]. Describing the solutions of ( 1) is however an old problem which has been studied since at least the 1940's in the case of Radon measure recovery.

Total variation regularization of Radon measures

where Ω ⊆ R N , M(Ω) denotes the space of Radon measures, |µ|(Ω) is the total variation of the measure µ (see Section 4) and Φµ is a vector of generalized moments, i.e. Φµ = Ω ϕ i (x)dµ(x) 1≤i≤m where {ϕ i } 1≤i≤m is a family of continuous functions (which "vanish at infinity" if Ω is not compact). Problems of the form (4) have received considerable attention since the pioneering works of Beurling [START_REF] Beurling | Sur les intégrales de Fourier absolument convergentes et leur application à une transformation fonctionnelle[END_REF] and Krein [START_REF] Kre Ǐn | The L-problem in an abstract normed linear space[END_REF], sometimes under the name L-moment problem (see the monograph [START_REF] Krein | The Markov moment problem and extremal problems: ideas and problems of P. L. Cebysev and A. A. Markov and their further development[END_REF]). To the best of our knowledge, the first "representer theorem" for problems of the form (1) is given for (4) by Zuhovicki ȋ [START_REF] Zuhovicki | Remarks on problems in approximation theory[END_REF] (see [START_REF] Zuhovicki | On approximation of real functions in the sense of P.L. Čebyšev[END_REF]Th. 3]

for an English version). It essentially states that

There exists a solution to (4) of the form r i=1 a i δ x i , with r ≤ m.

(

A more precise result was given by Fisher and Jerome in [START_REF] Fisher | Spline solutions to L1 extremal problems in one and several variables[END_REF]. When considering the problem (4), and for a bounded domain Ω, the result reads as follows:

The extreme points of the solution set to (4) are of the form r i=1 a i δ x i , with r ≤ m.

Incidentally, the Fisher-Jerome theorem considers more general problems of the form:

min u∈E |Lu|(Ω) s.t. Lu ∈ M(Ω) and Φu = y, (7)
where E ⊆ D (Ω) is a suitably defined Banach space of distributions, L : D (Ω) → D (Ω) maps E onto M(Ω) and Φ : E → R m is a continuous linear operator. We refer to Section 4 for precise assumptions. Let us mention that the initial results by Fisher-Jerome were extended to a significantly more general setting in [START_REF] Unser | Splines are universal solutions of linear inverse problems with generalized tv regularization[END_REF].

It is important to note that the Fisher-Jerome theorem [START_REF] Fisher | Spline solutions to L1 extremal problems in one and several variables[END_REF] provides a much finer description of the solution set than Zuhovicki ȋ's result [START_REF] Zuhovicki | Remarks on problems in approximation theory[END_REF]. Indeed, the well-known Krein-Milman theorem states that, if E is endowed with the topology of a locally convex Hausdorff vector space and C ⊂ E is compact convex, then C is the closed convex hull of its extreme points,

cl conv (ext(C)) = C. (8)
In other words, the solutions described by the Fisher-Jerome theorem are sufficient to recover the whole set of solutions. Let us mention that the Krein-Milman theorem was extended by Klee [START_REF] Klee | Extremal structure of convex sets[END_REF] to unbounded sets: if C is locally compact, closed, convex, and contains no line, then

cl conv (ext(C) ∪ rext(C)) = C, (9)
where rext(C) denotes the union of the extreme rays of C (see Section 2 below).

"Representer theorems" for convex sets

As the Dirac masses are the extreme points of the total variation unit ball, each of the above-mentioned "representer theorems" for inverse problems actually reflect some phenomenon in the geometry of convex sets. In that regard, the celebrated Minkowski-Carathéodory theorem [28, Th. III.2.3.4] is fundamental: any point of a compact convex set in an m-dimensional space is a convex combination of (at most) m + 1 of its extreme points. In [START_REF] Klee | On a theorem of Dubins[END_REF]Th. (3)], Klee removed the boundedness assumption and obtained the following extension: any point of a closed convex set in an m-dimensional space is a convex combination of (at most) m + 1 extreme points, or m points, each an extreme point or a point in an extreme ray.

One purpose of the present paper is to point out the connection between the Fisher-Jerome theorem and a lesser known theorem by Dubins [START_REF] Dubins | On extreme points of convex sets[END_REF] (see also [START_REF] Bourbaki | Espaces vectoriels topologiques: Chapitres 1à 5[END_REF]Exercise II.7.3.f]):

The extreme points of the intersection of C with an affine space of codimension m are convex combination of (at most) 2 m + 1 extreme points of C, provided C is linearly bounded and linearly closed (see Section 2). That theorem was extended by Klee [START_REF] Klee | On a theorem of Dubins[END_REF] to deal with the unbounded case.

Although the connection with the Fisher-Jerome is striking, Dubins' theorem actually provides one extreme point too many. In the case of (4), it would yield two Dirac masses for one linear measurement. We provide in this paper a refined analysis of the case of variational problems, which ensures at most m extreme points.

Contributions

The main results of this paper yield a description of some solutions to (1) of the following form:

u = r i=1 α i ψ i + u K ,
where r ≤ m, the atoms ψ i are identified with some extreme points (or points in extreme rays) of the regularizer level sets, and u K is an element of the so-called constancy space of R, i.e. the set of directions along which R is invariant. The results take the form (5), when f is an arbitrary function and the form (6) when it is convex. We provide tight bounds on the number of atoms r that depend on the geometry of the level sets and on the link between the constancy space of R and the measurement operator Φ.

Our general theorems then allow us to revisit many results of the literature (linear programming, semi-definite programming, nonnegative constraints, nuclear norm, analysis priors), yielding simple and accurate descriptions of the minimizers. Our analysis also allows us to characterize the solutions of a resisting problem: we provide a representation theorem for the minimizers of the total gradient variation [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF] as sums of indicators of simple sets. This provides a simple explanation to the staircaising effect when only a few measurements are used.

Let us mention that, shortly after this work was posted on arXiv, similar results appeared, with somewhat different proofs, in a paper by Bredies and Carioni [START_REF] Bredies | Sparsity of solutions for variational inverse problems with finite-dimensional data[END_REF].

Notation and Preliminaries

Throughout the paper, unless otherwise specified, E denotes a finite or infinite dimensional real vector space and C ⊆ E is a convex set. Given two distinct points x and y in E, we let ]x, y[= {tx + (1 -t)y : 0 < t < 1} and [x, y] = {tx+(1-t)y : 0 ≤ t ≤ 1} denote the open and closed segments joining x to y. We recall the following definitions, and we refer to [START_REF] Dubins | On extreme points of convex sets[END_REF][START_REF] Klee | Extremal structure of convex sets[END_REF] for more details.

Lines, rays, and linearly closed sets A line is an affine subspace of E with dimension 1. An open half-line, i.e. a set of the form ρ = {p + tv : t > 0}, where p, v ∈ E, v = 0, is called a ray (through p). We say that the set C is linearly closed (resp. linearly bounded) if the intersection of C and a line of E is closed (resp. bounded) for the natural topology of the line. If E is a topological vector space and C is closed for the corresponding topology, then C is linearly closed.

If C is linearly closed and contains some ray ρ = p+R * + v, it also contains the endpoint p as well as the rays q + R + v for all q ∈ C. Therefore, if C contains a ray (resp. line), it recesses in the corresponding direction.

Recession cone and lineality space

The set of all v ∈ E such that C + R * + v ⊆ C is a convex cone called the recession cone of C, which we denote by rec(C). If C is linearly closed then so is rec(C), and rec(C) is the union of 0 and all the vectors v which direct the rays of C. In particular, C contains a line if and only the vector space Following [START_REF] Dubins | On extreme points of convex sets[END_REF][START_REF] Klee | On a theorem of Dubins[END_REF], if p ∈ C, the smallest face of C which contains p is the union of {p} and all the open segments in C which have p as an inner point. We denote it by F C (p). The (co)dimension of F C (p) is defined as the (co)dimension of its affine hull. The collection of all elementary faces, {F C (p)} p∈C , is a partition of C. Extreme points correspond to the zerodimensional faces of C, while extreme rays are (generally a strict subcollection of the) one-dimensional faces.

lin(C) def. = rec(C) ∩ (-rec(C)) (10

Quotient by lines

As noted above, if C is linearly closed, it contains a line if and only if the vector space lin(C) defined in [START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF] where y ∈ R m , Φ : E → R m is a linear operator, and m ≤ dimE, m < +∞.

In the following, let t denote the optimal value of (P), S denote its solution set, and C denote the corresponding level set of R,

C

def.

= {u ∈ E : R(u) ≤ t } .

Theorem 1. Let R : E → R ∪ {+∞} be a convex function. Assume that inf E R < t < +∞, that S is nonempty and that the convex set C is linearly closed and contains no line. Let p ∈ S and let j be the dimension of the face F S (p). Then p belongs to a face of C with dimension at most m + j -1.

In particular, p can be written as a convex combination of:

• m + j extreme points of C ,

• or m + j -1 points of C , each an extreme point of C or in an extreme ray of C .

Moreover, rec(S ) = rec(C ) ∩ ker(Φ) and therefore lin(S ) = lin(C ) ∩ ker(Φ). The proof of theorem 1 is given in Section 6.1. Before extending this theorem to a wider setting, let us formulate some remarks.

Remark 1 (Extreme points and extreme rays of S ). In particular (j = 0), each extreme point of S is a convex combination of m extreme points of C , or a convex combination of m -1 points of C , each an extreme point of C or in an extreme ray. Similarly (j = 1), each point on an extreme ray of S is a convex combination of m + 1 extreme points of C , or a convex combination of m points of C , each an extreme point of C or in an extreme ray. Hence, provided the assumptions of Klee's theorem (see [START_REF] Bredies | Sparsity of solutions for variational inverse problems with finite-dimensional data[END_REF]) hold, Theorem 1 completely charaterizes the solution set. An illustration is provided in fig. 1.

Remark 2 (The hypothesis inf E R < t ). We have focused on the case t > inf E R in the theorem since the case t = min R is easier. In that case, M = Φ -1 ({y}) can be in arbitrary position (i.e. not necessarily tangent) w.r.t. C = argmin R, and one can only use the general Dubins-Klee theorem [START_REF] Dubins | On extreme points of convex sets[END_REF][START_REF] Klee | On a theorem of Dubins[END_REF] to describe their intersection. As a result the conclusions of theorem 1 are slightly weakened, p belongs to a face of C with dimension m + j, and one must add one more point in the convex combination (e.g., for j = 0, each extreme point of S is a convex combination of m + 1 extreme points of C , or m points. . . ).

Remark 3 (Gauge functions or semi-norms).

A common practice in inverse problems is to consider positively homogeneous regularizers R, such as (semi)norms or gauge functions of convex sets. In that case the extreme points of C correspond, up to a rescaling, to the extreme points of {u ∈ E : R(u) ≤ 1}. In several cases of interest, the extreme points of such convex sets are well understood, see Section 4 for examples in Banach spaces or, for instance, the paper [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF]Sec. 2.2] for examples in finite dimensional spaces.

Remark 4 (Extension to semi-strictly quasi convex functions). Theorem 1 can be extended to the case where R is a semi-strictly quasi-convex function. A function R is said to be semi-strictly quasi-convex [START_REF] Daniilidis | Some remarks on the class of continuous (semi-) strictly quasiconvex functions[END_REF]

if it is quasi-convex and if R(x) < R(y) =⇒ R(λx + (1 -λ)y) < R(y) ∀λ ∈]0, 1[.
In words, semi-strictly quasi-convex functions are functions that, when restricted to a line are successively decreasing, constant and increasing on their domain.

In comparison, strictly quasi-convex functions are successively decreasing and increasing while quasi-convex functions successively non-increasing and nondecreasing.

The set of semi-strictly quasi-convex functions is a subset of quasi-convex functions and it contains all convex and strictly quasi-convex functions. In the proof of theorem 1, only the semi-strictly quasi-convex property is required to ensure that (28) holds.

Remark 5 (Topological properties).

The assumption that C is linearly closed is fulfilled in most practical cases, since E is usually endowed with the topology of a Banach (or locally convex) vector space and R is assumed to be lower semicontinuous (so as to guarantee the existence of a solution to (P)). Note also that if R is lower semi-continuous on any line (for the natural topology of the line), the set C is linearly closed.

The case of level sets containing lines

The reader might be intrigued by the assumption of theorem 1 that C contains no line, since in several applications the regularizer R is invariant by the addition of, e.g., constant functions or low-degree polynomials (see Section 4). In that case, one is generally interested in the non-constant or non-polynomial part, and it is natural to consider a quotient problem for which the theorem applies. We describe below (see corollary 1) how our result extends to the case where C contains lines.

If C is linearly closed and contains some line, it is translation-invariant in the corresponding direction. The collection of all such directions is the lineality space of C (see Section 2), we denote it by K def.

= lin(C ) (typically, if R is the composition of a linear operator and a norm, K is the kernel of that linear operator). Let π K : E → E/K be the canonical projection map. We recall that there exists a linear isomorphism ψ K : E → (E/K) × K such that the first component of ψ K (p) is π K (p) for all p ∈ E. We may now describe the equivalence classes (modulo K) of the solutions.

E/K C Φ -1 ({y}) S C q 1 q 2 K = lin(C )
Corollary 1. Let R : E → [-∞,
+∞] be a convex function. Assume that inf E R < t < +∞, that S is nonempty and that the convex set C is linearly closed. Let K def.

= lin(C ) be the lineality space of C and d def.

= dimΦ(K). Let p ∈ S , let π K (p) denote its equivalence class, and let j be the dimension of the face

F π K (S ) (π K (p)).
Then, π K (p) belongs to a face of π K (C ) with dimension at most m+j -d-1. In particular,

• π K (p) is a convex combination of m + j -d extreme points of π K (C ), • or π K (p) is a convex combination of m + j -d -1 points of π K (C ), each an extreme point of π K (C ) or in an extreme ray of π K (C ).
As a result, letting q1 , . . . , qr denote those extreme points (or points in extreme rays),

p = r i=1 θ i ψ -1 K (q i , 0) + u K , where θ i ≥ 0, r i=1 θ i = 1, and u K ∈ K. ( 13
)
The proof of corollary 1 is given in Section 6.2. One can have an explicit representation with elements of E of a solution p ∈ S . Indeed, let W be some linear complement to K = lin(C ). One may decompose C = C + K, where C = C ∩ W , and observe that π K (C ) and C are isomorphic. In this case, corollary 1 implies that p can be written as the sum of one point in lin(C ) and of a convex combination of:

• m + j -d extreme points of C ,
• or m + j -1 -d points of C , each an extreme point of C or in an extreme ray of C .

Extensions to data fitting functions

In this section, we discuss the extension of the above results to more general problems of the form

inf u∈E f (Φu) + R(u), (P f )
where f : R m → R ∪ {+∞} is an arbitrary fidelity term.

Convex data fitting term

When f is a convex data fitting function f , we get the following result.

Corollary 2. Assume that f is convex and that the solution set

S f of (P f ) is nonempty. Let p ∈ S f such that C def. = {u ∈ E, R(u) ≤ R(p)} is linearly closed, K def.
= linC and let j be the dimension of the face

F π K (S f ) (π K (p)). If inf E R < R(p), then the conclusions of corollary 1 (or theorem 1 if K = {0}) hold.
If inf E R = R(p), they hold with 1 more dimension (see remark 2).

Let us recall that, in view of remark 5, if E is a topological vector space and R is lower semi-continuous, C is closed regardless of the choice p.

Proof. Let y = Φp and consider the following problem:

min u∈E R(u) s.t. Φu = y. (P {y} ) Let S {y} denote its solution set. It is a convex subset of S f , with p ∈ S {y} . Additionally, if j is the dimension of F π K (S f ) (p) (resp. F S f (p) if C contains no line), then the face F π K (S {y} ) (p) (resp. F S {y} (p)
) has dimension at most j, since S {y} ⊆ S f . It suffices to apply corollary 1 (resp. theorem 1) to obtain the result.

Remark 6 (The case of a strictly-convex function). In the case when f is strictly convex, it is known that ΦS f is a singleton, which means that S {y} = S f .

Remark 7 (The case of quasi-convex functions). The result actually holds whenever the solution set S f is convex. In particular, this property holds when f is quasi-convex and R is convex.

Non-convex function

In the general case, i.e. when f : R m → R ∪ {+∞} is an arbitrary function, it is difficult to describe the structure of the solution set. However, one may choose a solution p 0 (as before, provided it exists) and observe that it is also a solution to (P) for y def.

= Φp 0 . Then, one may apply corollary 1, but the difficult part is that the dimensions j to consider are with respect to the solution set S of the convex problem (P). Nevertheless, if one is able to assert that the solution set S has at least an extreme point p, then corollary 1 ensures that p can be written in the form [START_REF] Chandrasekaran | The convex geometry of linear inverse problems[END_REF], where r ≤ m and the qi 's are extreme points (or points in extreme rays) of C . Since p must also be a solution to (P f ), one obtains that there exists a solution to (P f ) of the form (13).

Ensuring the existence of extreme points

It is important to note that, in theorem 1, the existence a face of S with dimension j is not guaranteed (nor, for j = 0, the existence of extreme points). The convex set S might not even have any finite-dimensional face! For instance, let E be the space of Lebesgue-integrable functions on

[0, 1]. If R(u) = 1 0 |u(x)|dx, Φ : E → R is defined by u → 1 0 u(x)dx, and y = 1, then S = u ∈ E : 1 0 |u(x)|dx ≤ 1 and 1 0 u(x)dx = 1 . ( 14
)
It is possible to prove that such a set S does not have any extreme point. As a consequence S does not have any finite-dimensional face (otherwise an extreme point of the closure of a face would be an extreme point of S ). However, theorem 1 (in fact the Dubins-Klee theorem [START_REF] Dubins | On extreme points of convex sets[END_REF][START_REF] Klee | On a theorem of Dubins[END_REF]) asserts that, if there is a finite-dimensional face in S , then C has indeed extreme points (and possibly extreme rays), and the convex combinations of such points generate the above-mentioned face.

As a result, it is crucial to be able to assert a priori the existence of some finite-dimensional face for S , and this is where topological arguments come into play. If E is endowed with the topology of a locally convex (Hausdorff) vector space, the theorems [30, 3.3 and 3.4] which generalize the celebrated Krein-Milman theorem, state that S has an extreme point provided

• S is nonempty, convex,
• S contains no line,

• and S is closed, locally compact.

The last two conditions hold in particular if S is compact. Moreover, as in corollary 1, the second condition can be ensured by considering a suitable quotient map, provided it preserves the other topological properties (e.g. if lin(C) has a topological complement). Remark 8. Whereas local compactness is a very strong property for topological vector spaces (implying their finite-dimensionality, see [8, Th. 3,Ch. 1]), it is not so difficult to ensure the local compactness of S in practice. Indeed, very often, even the existence of solutions is usually ensured using compactness arguments for a suitable weak or weak-* topology. The unbounded cases require more specific arguments, but let mention that there are examples of cones which are locally compact without being contained in any finite-dimensional vector space. In Section 4.2.2 below, we discuss the example of the cone M + (Ω) of non-negative measures over a compact set for the weak-* topology. Another example of locally compact convex cone is

C = x ∈ R N such that x n ≥ 0 and n∈N x n ω n ≤ n∈N x n < +∞ ⊆ 1 (N) ,
for some non-decreasing positive sequence (ω n ) n converging to +∞ (note that ω 0 < 1 for the cone to be non-empty). The cone C is locally compact for the strong topology. Indeed, consider the intersection K of the cone C and the strong unit ball, namely

K = {x = (x n ) n : x n ≥ 0, n ω n x n ≤ n x n ≤ 1} and consider a sequence of elements of K denoted (x k ) k ⊂ K. Using a diagonal argument, each (x k n ) k converges
(w n -1)x n ≤ lim inf k n : wn≥1 (w n -1)x k n ≤ lim inf k n : wn<1 (1 -w n )x k n = n : wn<1 (1 -w n )x n
and we deduce that x = (x n ) n ∈ K. Furthermore, one has

||x k -x|| 1 = M n=0 |x k n -xn | + n>M |x k n -xn |
and M will be chosen later. Finally,

n>M |x k n -xn | ≤ n>M (x k n + xn ) ≤ (1/ω M ) n>M ω n (x k n + xn ) ≤ 2/ω M since ω n /ω M ≥ 1 for n > M . Therefore choosing M large enough ensures that the second term n>M |x k n -xn | is less than some ε > 0. Choosing k large enough leads to ||x k -x|| 1 ≤ 2ε.

Application to some popular regularizers

We now show that the extreme points and extreme rays of numerous convex regularizers can be described analytically, allowing to describe important analytical properties of the solutions of some popular problems. The list given below is far from being exhaustive, but it gives a taste of the diversity of applications targeted by our main results.

Finite-dimensional examples

We first consider examples where one has dimE < +∞. In that case, Φ is continuous, and since the considered regularizations R are lower semicontinuous, we deduce that

• the level set C is closed,
• the solution set S = C ∩ Φ -1 ({y}) is closed, and locally compact (even compact in most cases), hence it admits extreme points provided it contains no line.

Nonnegativity constraints

In a large number of applications, the signals to recover are known to be nonnegative. In that case, one may be interested in solving nonnegatively constrained problems of the form:

inf u∈R n + f (Φu -y). (15)
An important instance of this class of problems is the nonnegative least squares [START_REF] Lawson | Solving least squares problems[END_REF], which finds it motivation in a large number of applications.

Applying the results of Section 3 to Problem (15) yields the following result.

Proposition 1. If the solution set of (15) is nonempty, then it contains a solution which is m-sparse. In addition if f is convex and the solution set is compact, then its extreme points are m-sparse.

Choosing R as the characteristic function of R n + , the result simply stems from the fact that the extreme rays of the positive orthant are the half lines {αe i , α ≥ 0}, where (e i ) 1≤i≤n denote the elements of the canonical basis. We have to consider m atoms and not m -

1 since t = inf R = 0, see remark 2.
It may come as a surprise to some readers, since the usual way to promote sparsity consists in using 1 -norms. This type of result is one of the main ingredients of [START_REF] Donoho | Sparse nonnegative solution of underdetermined linear equations by linear programming[END_REF] which shows that the 1 -norm can sometimes be replaced by the indicator of the positive orthant when sparse positive signals are looked after.

Linear programming

Let ψ ∈ R n be a vector and Φ ∈ R m×n be a matrix and consider the following linear program in standard (or equational) form:

inf u∈R n + Φu=y ψ, u (16)
Applying Theorem (1) to the problem ( 16), we get the following wellknown result (see e.g. [START_REF] Matousek | Understanding and using linear programming[END_REF]Thm. 4

.2.3]):

Proposition 2. Assume that the solution set of (16) is nonempty and compact. Then, its extreme points are m-sparse, i.e. of the form:

u = m i=1 α i e i , α i ≥ 0, (17)
where e i denotes the i-th element of the canonical basis.

In the linear programming literature, solutions of this kind are called basic solutions. To prove the result, we can reformulate [START_REF] Castro | Exact solutions to super resolution on semi-algebraic domains in higher dimensions[END_REF] as follows:

inf (u,t)∈R n + ×R Φu=y ψ,u =t t (18) Letting R(u, t) = t + ι R n + (u), we get inf R = -∞.
Hence, if a solution exists, we only need to analyze the extreme points and extreme rays of

C = {(x, t) ∈ R n × R, R(x, t) ≤ t } = R n + ×] -∞, t ],
where t denotes the optimal value. The extreme rays of this set (a shifted nonnegative orthant) are of the form {αe i , α > 0} × {t } or {0}×] -∞, t [. In addition C possesses only one extreme point (0, t ). Applying theorem 1, we get the desired result.

1 analysis priors

An important class of regularizers in the finite dimensional setting E = R n contains the functions of the form R(u) = Lu 1 , where L is a linear operator from R n to R p . They are sometimes called analysis priors, since the signal u is "analyzed" through the operator L. Remarkable practical and theoretical results have been obtained using this prior in the fields of inverse problems and compressed sensing, even though many of its properties are -to the belief of the authors-still quite obscure.

Since R is one-homogeneous, it suffices to describe the extremality properties of the unit ball C = {u ∈ R n , Lu 1 ≤ 1} to use our theorems. The lineality space is simply equal to lin(C) = ker(L). Let K = ker(L), K ⊥ denote the orthogonal complement of K in R n and L + : R n → K ⊥ denote the pseudo-inverse of L. We can decompose C as C = K + C K ⊥ with C K ⊥ = C ∩ K ⊥ . Our ability to characterize the extreme points of C K ⊥ depends on whether L is surjective or not. Indeed, we have

ext(C K ⊥ ) = L + (ext (ran(L) ∩ B p 1 )) , (19)
where B p 1 is the unit 1 -ball defined as

B p 1 = {z ∈ R p , z 1 ≤ 1}.
Property [START_REF] Drusvyatskiy | Extreme point inequalities and geometry of the rank sparsity ball[END_REF] simply stems from the fact that C K ⊥ and D = ran(L) ∩ B p 1 are in bijection through the operators L and L + .

The case of a surjective operator L When L is surjective (hence p ≤ n), the problem becomes quite elementary.

Proposition 3. If L is surjective, the extreme points u of C K ⊥ are ext(C K ⊥ ) = (±L + e i ) 1≤i≤p
, where e i denotes the i-th element of the canonical basis. Consider Problem (P f ) and assume that at least one solution exists. Then Problem (P f ) has solutions of the form

u = i∈I α i L + e i + u K , ( 20
)
where u K ∈ ker(L) and I ⊂ {1, . . . , p} is a set of cardinality |I| ≤ mdim(Φker(L)).

The proof of Proposition 3 follows from Corollary 1 and Section 3.3.2, with j = 0 and observing that π K is the orthogonal projection on K ⊥ .

The case of an arbitrary operator L When L is not surjective the description of the extreme points ext (D) becomes untractable in general. A rough upper-bound on the number of extreme points can be obtained as follows. We assume that L has full rank n and that ran(L) is in general position. The extreme points of ran(L) ∩ B p 1 correspond to the intersections of some faces of the 1 -ball with a subspace of dimension n. In order for some k-face to intersect the subspace ran(L) on a singleton, k should satisfy n + k -p = 0, i.e. k = p -n. The k-faces of the 1 -ball contain (k + 1)-sparse elements. The number of (k + 1)-sparse supports in dimension p is p k+1 . For a fixed support, the number of sign patterns is upperbounded by 2 k+1 . Hence, the maximal number of extreme points satisfies | ext (ran(L) ∩ B p 1 ) | ≤ 2 k+1 p k+1 . This upper-bound is pessimistic since the subspace may not cross all extreme points, but it provides an idea of the combinatorial explosions that may happen in general.

Notice that enumerating the number of faces of a polytopes is usually a hard problem. For instance, the Motzkin conjecture [START_REF] Motzkin | Comonotone curves and polyhedra[END_REF] which upper bounds the number of k faces of a d polytope with z vertices was formulated in 1957 and solved by Mc Mullen [START_REF] Mcmullen | The maximum numbers of faces of a convex polytope[END_REF] in 1970 only.

Matrix examples

In several applications, one deals with optimization problems in matrix spaces. The following regularizations/convex sets are commonly used.

Semi-definite matrix constraint

Similarly to Section 4.1.1, one may consider in R n×n the following constrained problem

inf M 0 f (ΦM -y), (21)
where M 0 means that M must be symmetric positive semi-definite (p.s.d.). The extreme rays of the positive semi-definite cone C are the p.s.d. matrices of rank 1 (see for instance [15, Sec. 2.9.2.7]). Hence, arguing as in Section 4.1.1, we may deduce that if there exists a solution to [START_REF] Duval | Exact support recovery for sparse spikes deconvolution[END_REF], there is also a solution which has rank (at most) m.

However, that conclusion is not optimal, as in that case a theorem by Barvinok [5,Th. 2.2] ensures that there exists a solution M with rank(M ) ≤ 1 2

√ 8m + 1 -1 . ( 22
)
To understand the gap with Barvinok's result, let us note that the p.s.d. cone has a very special structure which makes the Minkowski-Carathéodory theorem (or its extension by Klee) too pessimistic. By [15, Sec. 2.9.2.3], given M 0, the smallest face of the p.s.d. cone which contains M (i.e. the set of p.s.d matrices which have the same kernel) has dimension

d = 1 2 rank(M )(rank(M ) + 1). (23)
Equivalently, if the smallest face which contains M has dimension d,

then rank(M ) = 1 2 √ 8d + 1 -1 , hence M is a convex combination of 1 2
√ 8d + 1 -1 points in extreme rays, a value which is less than the value d predicted by Klee's extension of Carathéodory's theorem.

As a result, we recover Barvinok's result by noting that, as ensured by the first claim3 of theorem 1, any extreme point M of the solution set belongs to a face of dimension m. Then, taking into account [START_REF] Fisher | Spline solutions to L1 extremal problems in one and several variables[END_REF] improves upon the second claim of theorem 1, and we immediately obtain [START_REF] Fernandez-Granda | Super-resolution of point sources via convex programming[END_REF].

Semi-definite programming Semi-definite programs are problems of the form:

inf

M 0 Φ(M )=y A, M , (24)
where A ∈ R n×n is a matrix and A, M def.

= Tr(AM ). Arguing as in proposition 2, if the solution set of ( 24) is nonempty, our main result allows to state that its extreme points are matrices of rank m. In view of the above discussion, it is possible to refine this statement and show that [START_REF] Fernandez-Granda | Super-resolution of point sources via convex programming[END_REF] holds.

The nuclear norm

The nuclear norm of a matrix M ∈ R p×n is often denoted M * and defined as the sum of the singular values of M . It gained a considerable attention lately as a regularizer thanks to its applications in matrix completion [START_REF] Candès | Exact matrix completion via convex optimization[END_REF] or blind inverse problems [START_REF] Ahmed | Blind deconvolution using convex programming[END_REF]. The geometry of the unit ball {M ∈ R p×n , M * ≤ 1} is well studied due to its central role in the field of semi-definite programming [START_REF] Pataki | The geometry of semidefinite programming[END_REF]. Its extreme points are the rank one matrices M = uv T , with

u 2 = v 2 = 1.
Combining theorem 1 with this result explains why regularizing problems over the space of matrices with the nuclear norm allows recovering rank-m solutions.

The rank-sparsity ball The rank-sparsity ball is the set {M ∈ R m×n , M * + M 1 ≤ 1}, where M 1 is the 1 -norm of the entries of M . The corresponding regularization is sometimes used in order to favor sparse and low-rank matrices. The authors of [START_REF] Drusvyatskiy | Extreme point inequalities and geometry of the rank sparsity ball[END_REF] have described the extreme points of this unit ball. They have proved that the extreme points M of the rank sparsity ball satisfy r(r+1)

2

-|I| ≤ 1, where |I| denotes the number of non-zero entries in M and r denotes its rank. This result partly explains why using the rank-sparsity gauge promotes sparse and low rank solution. Let us outline that this effect might be better obtained using different strategies [START_REF] Richard | Intersecting singularities for multistructured estimation[END_REF][START_REF] Richard | Tight convex relaxations for sparse matrix factorization[END_REF].

Bi-stochastic matrices A doubly stochastic matrix is a matrix with nonnegative rows and columns summing to one. The set of such matrices is called the Birkhoff polytope. The Birkhoff-von Neumann theorem states that its extreme points are the permutation matrices. We refer the interested reader to [START_REF] Fogel | Convex relaxations for permutation problems[END_REF] for an use of such matrices in DNA sequencing.

Examples in infinite dimension

In this section, we provide results in infinite dimensional spaces, which echoe the ones described in finite dimension.

Problems formulated in Hilbert or Banach sequence spaces

The case of Hilbert spaces (or countable sequences) can be treated within our formalism and all the examples presented previously have their natural counterpart in this setting. In the same vein, one can also treat Banach sequence spaces p for 1 ≤ p ≤ ∞. We do not reproduce the results here for space limitations. Let us however mention that two works treat this specific case with 1 regularizers [47, 1].

Linear programming and the moment problem

Let Ω be a compact metric space, M(Ω) be the set of Radon measures on Ω and let M + (Ω) ⊆ M(Ω) be the cone of nonnegative measures on Ω. Let ψ and (φ i ) 1≤i≤m denote a collection of continuous functions on Ω. Now, let Φ : M(Ω) → R m be defined by (Φµ) i = φ i , µ , where φ i , µ def.

= Ω φ i dµ, and consider the following linear program in standard form:

inf µ∈M + (Ω) Φµ=y ψ, u . (25)
Applying Theorem (1) to the problem (25), we get proposition 4 below. We do not provide a proof here, since it mimics very closely the one given for linear programming in finite dimension. The extreme rays of M + (Ω) can be described, arguing as in [START_REF] Aliprantis | Infinite Dimensional Analysis: A Hitchhiker's Guide[END_REF]Th. 15.9], as the rays directed by the Dirac masses. Proposition 4. Assume that the solution set (25) is nonempty. Then, its extreme points are m-sparse, i.e. of the form:

u = m i=1 α i δ x i , x i ∈ Ω, α i ≥ 0. (26)
To make sure that the above proposition is non-trivial, one may wish to ensure that the solution set S has indeed extreme points, using arguments from Section 3.4. It is straightforward that S is convex and does not contain any line. Now, let us endow M(Ω) with the weak-* topology (i.e. the coarsest topology for which µ → Ω ηdµ is continuous for every η ∈ C (Ω)). By lower semi-continuity, S is closed. Moreover, S is locally compact since the closed convex cone M + is itself locally compact (take any

µ ∈ M + (Ω), its neighborhood {ν ∈ M + (Ω) : ν(Ω) ≤ µ(Ω) + 1} is compact in the weak-* topology).
Proposition 4 is well known, see e.g. [START_REF] Shapiro | On duality theory of conic linear problems[END_REF]. Note that if we optimize the linear form ψ, u over the set of probability measures instead of the set of nonnegative measures, we get the so-called moment problem [START_REF] Shohat | The problem of moments[END_REF] for which we can obtain a similar result.

The total variation ball

Let Ω denote an open subset of R d and M(Ω) denote the set of Radon measures on Ω. The total variation ball B M = {u ∈ M(Ω), u M(Ω) ≤ 1} plays a critical role for problems such as super-resolution [START_REF] Candès | Towards a mathematical theory of super-resolution[END_REF][START_REF] Tang | Compressed sensing off the grid[END_REF][START_REF] Duval | Exact support recovery for sparse spikes deconvolution[END_REF]. It is compact for the weak-* topology and its extreme points are the Dirac masses: ext(B M ) = {±δ x , x ∈ Ω}. Hence total variation regularized problems of the form:

inf u∈M f (Φu) + u M ,
yield m-sparse solutions (under an existence assumption). A few variations around this central result were provided in [START_REF] Fernandez-Granda | Super-resolution of point sources via convex programming[END_REF].

Demixing of Sines and Spikes

In [22, Page 262], the author presents a regularization of the type

µ M + η v 1
where η > 0 is a tuning parameter, µ a complex measure and v ∈ C n a sparse vector. Define E as the set of (µ, v) where µ is a complex Radon measure on a domain Ω and v ∈ C n . Consider the unit ball

B def. = {(µ, v) ∈ E : µ M + η v 1 ≤ 1}.
Its extreme points are the points

• (aδ t , 0) for all t ∈ Ω (and δ t denotes the Dirac mass at point t) and all a ∈ C such that |a| = 1,

• (0, ae k ) for all k = 1, . . . , n and all a ∈ C such that |a| = 1/η and e k denotes the vector with 1 at entry k and 0 otherwise.

Group Total Variation: Point sources with a common support In [22, Page 266], the author presents a regularization of the type

µ M n := sup F :Ω→C n , F (t) 2 ≤1, t∈Ω Ω F (t), ν(t) d|µ|(t)
were F is continuous and vanishing at infinity, and µ is a vectorial Radon measure on Ω such that |µ|-a.e. µ = ν • |µ| with ν a measurable function from Ω onto S n-1 the n-sphere and |µ| a positive finite measure on Ω. Consider the unit ball B def.

= {µ, µ M n ≤ 1}.

Its extreme points are aδ t for all t ∈ Ω (and δ t denotes the Dirac mass at point t) and all a ∈ C n such that a 2 = 1.

Analysis priors in Banach spaces

The analysis of extreme points of analysis priors in an infinite dimensional setting is more technical. Fisher and Jerome [START_REF] Fisher | Spline solutions to L1 extremal problems in one and several variables[END_REF] proposed an interesting result, which can be seen as an extension of (20). This result was recently revisited in [START_REF] Unser | Splines are universal solutions of linear inverse problems with generalized tv regularization[END_REF] and [START_REF] Flinth | Exact solutions of infinite dimensional totalvariation regularized problems[END_REF]. Below, we follow the presentation in [START_REF] Flinth | Exact solutions of infinite dimensional totalvariation regularized problems[END_REF].

Let Ω denote an open set in R d . Let D (Ω) denote the set of distributions on Ω and let L : D (Ω) → D (Ω) denote a linear operator with kernel K = ker(L). We let E = {u ∈ D (Ω), Lu ∈ M(Ω)} and let • K denote a seminorm on E, which restricted to K is a norm. We define a function space B(Ω) as follows:

B(Ω) = {u ∈ E, Lu M(Ω) + u K < +∞}
and equip it with the norm u B(Ω) = Lu M(Ω) + u K . We assume that L is surjective, i.e. M(Ω) = L(B(Ω)), and that K has a topological complement (with respect to B(Ω)), which we denote by K ⊥ . This setting encompasses all surjective Fredholm operators for instance. Under the stated assumptions, we can define a pseudo-inverse L + of L relative to K ⊥ [START_REF] Beutler | The operator theory of the pseudo-inverse i. bounded operators[END_REF].

The representer theorems in [START_REF] Fisher | Spline solutions to L1 extremal problems in one and several variables[END_REF][START_REF] Unser | Splines are universal solutions of linear inverse problems with generalized tv regularization[END_REF][START_REF] Flinth | Exact solutions of infinite dimensional totalvariation regularized problems[END_REF] can be obtained using theorem 1 as exemplified below. Assume that S is nonempty and does not contain 0. Then the extreme points (if they exist) of π K (S ) are of the form u = m i=1 α i L + δ x i . Proof. The proof mimics the finite dimensional case [START_REF] Dubins | On extreme points of convex sets[END_REF]. First notice that B = L -1 (B M ), where L -1 ({µ}) is the pre-image of µ by L and B M is the unit total variation ball. We have L -1 (B M ) = L + (B M ) + K and we can identify C K ⊥ with L + (B M ). Since L + is bijective from M(Ω) to K ⊥ , the extreme points of C K ⊥ are the image by L + of the Dirac masses.

The end of the proposition follows from Corollary 2 and from the fact that the lineality space of {u ∈ B(Ω), Lu M(Ω) ≤ 1} is equal to K.

Let us mention that, although the description of the extreme points follows directly from the results of Section 3, proving the existence of minimizers and the existence of extreme points is a considerably more difficult problem which needs a careful choice of topologies. The paper [START_REF] Unser | Splines are universal solutions of linear inverse problems with generalized tv regularization[END_REF] provides a systematic way to construct Banach spaces and pseudo-inverse L + for "spline admissible operators" L such as the fractional Laplacian. In addition, they prove existence of solutions by adding weak-* continuity assumptions on the sensing operator Φ.

The total gradient variation

Since its introduction in the field of image processing [START_REF] Rudin | Nonlinear total variation based noise removal algorithms[END_REF], the total gradient variation proved to be an extremely valuable regularizer in diverse fields of data science and engineering. It is defined, for any locally integrable function u as

T V (u) def. = sup udiv(φ) dx, φ ∈ C 1 c (R d ) d , sup x∈R d φ(x) 2 ≤ 1 .
If the above quantity is finite, we say that u has bounded variation and its gradient Du is a Radon measure, with

T V (u) = R d |Du| = Du (M(R d )) d .
Working in E = L d/(d-1) (R d ), one is led to consider the convex set C = {u ∈ E, T V (u) ≤ 1}, referred to as the TV unit ball.

The generalized gradient operator is not a surjective operator. Hence, the analysis of Section 4.2.4 cannot help finding the extreme points of the TV ball. Still, those have been described in the fifties by Fleming in [START_REF] Fleming | Functions with generalized gradient and generalized surfaces[END_REF] and refined analyses have been proposed more recently by Ambrosio, Caselles, Masnou and Morel in [START_REF] Ambrosio | Connected components of sets of finite perimeter and applications to image processing[END_REF].

Theorem 2 (Extreme points of the TV ball [START_REF] Fleming | Functions with generalized gradient and generalized surfaces[END_REF][START_REF] Ambrosio | Connected components of sets of finite perimeter and applications to image processing[END_REF]). The extreme points of the unit TV unit ball are the indicators of simple sets normalized by their perimeter, i.e. functions of the form u = ± 1 F T V (1 F ) , where F is an indecomposable and saturated subset of R d .

Informally, the simple sets of R d are the simply connected sets with no hole. We refer the reader to [START_REF] Ambrosio | Connected components of sets of finite perimeter and applications to image processing[END_REF] for more details. Using theorem 2 in conjunction with our results tell us that functions minimizing the total variation subject to a finite number of linear constraints can be expressed as a sum of a small number of indicators of simple sets, see for instance fig. 3, which is yet another theoretical result explaining the common observation that total variation tends to produce stair-casing [START_REF] Nikolova | Local strong homogeneity of a regularized estimator[END_REF].

Conclusion

In this paper we have developed representer theorems for convex regularized inverse problems (1), based on fundamental properties of the geometry of convex sets: the solution set can be entirely described using convex combinations of a small number of extreme points and extreme rays of the regularizer level set.

Obviously, the conclusion of Theorem 1 is only nontrivial when C has a "sufficiently flat boundary", in the sense that two or more faces of C have dimension larger than m. For instance, if C is strictly convex (i.e. has only 0-dimensional faces, except its interior4 ), then the solution set S is always reduced to a single extreme point of C ! Nevertheless, several regularizers which are commonly used in the literature (notably sparsitypromoting ones) have that flatness property, and Theorem 1 then provides interesting information on the structure of the solution set, as illustrated in Section 4.

To conclude, the structure theorem presented in this paper highlights the importance of describing the extreme points and extreme rays of the regularizer: this yields a fine description of the set of solutions of variational problems of the form (1). Our theorem also suggests a principled way to design a regularizer. If a particular family of solutions is expected, then one may construct a suitable regularizer by taking the convex hull of this family. Finally, representer theorems have had a lot of success in the fields of approximation theory and machine learning [START_REF] Sch Ölkopf | A generalized representer theorem[END_REF], in the frame of reproducible kernel Hilbert spaces. A reason of this success is that they allow to design efficient numerical procedures that yield infinite dimensional solutions by solving finite dimensional linear systems. Such numerical procedures have recently been extended to the case of Banach spaces for some simple instances of the problems described in this paper [START_REF] Fernandez-Granda | Super-resolution of point sources via convex programming[END_REF][START_REF] Castro | Exact solutions to super resolution on semi-algebraic domains in higher dimensions[END_REF][START_REF] Flinth | Exact solutions of infinite dimensional totalvariation regularized problems[END_REF]. The price to pay when going from a Hilbert space to a Banach space is that semi-infinite convex programs have to be solved instead of simpler linear systems. We foresee that the results in this paper may help designing new efficient numerical procedures, since they allow to parameterize the solutions using extreme points and extreme rays only.

Proofs of Section 3 6.1 Proof of Theorem 1

The set of solutions S is precisely C ∩ Φ -1 ({y}), and the statement of the theorem amounts to describing its elementary faces. Since Φ -1 ({y}) is an affine space with codimension at most m, the main theorem of [START_REF] Klee | On a theorem of Dubins[END_REF] almost provides the desired conclusion, but, for our particular case, it yields one extreme point/ray too many. Here is how to obtain the correct number.

Let p be a point of S such that F S (p) has dimension j. Up to a translation, it is not restrictive to assume that p = 0, so that S = C ∩ kerΦ.

Let T be the union of {0} and all the lines such that C ∩ contains an open interval which contains 0. Note that T is a linear space, the linear hull of F C (0).

We claim that codim T (T ∩ kerΦ) ≤ m-1. By contradiction assume that there is a complement Z to T ∩ kerΦ in T with dimension m. Then Φ| Z has rank m and is a bijection, hence we may define

z def. = - θ (1 -θ) (Φ| Z ) -1 (Φu 0 ) ∈ Z ⊂ T,
where θ ∈]0, 1[ and u 0 ∈ C is such that inf R ≤ R(u 0 ) < t . For θ small enough, z ∈ C , hence R(z) ≤ t . Moreover, Φ ((1 -θ)z + θu 0 ) = (1 -θ)Φz + θΦu 0 = 0.

so that (1 -θ)z + θu 0 lies in C ∩ kerΦ. Since R(u 0 ) < R(z), and R is convex

R ((1 -θ)z + θu 0 ) < R (z) ≤ t , (28)
we obtain a contradiction with the fact that t is the minimal value of (P). As a result, codim T (T ∩ kerΦ) ≤ m -1. Observing that T ∩ kerΦ is the linear hull of F S (0), hence j = dim (T ∩ kerΦ), we deduce that dimF C (0)

def.

= dimT = codim T (T ∩ kerΦ)+dim (T ∩ kerΦ) ≤ m-1+j, [START_REF] Klee | On a theorem of Dubins[END_REF] and the first claim of the theorem is proved. Now, applying the Carathéodory-Klee theorem (3) in [START_REF] Klee | On a theorem of Dubins[END_REF], p is convex combination of at most m+j (resp. m+j -1) extreme points (resp. extreme points or in an extreme ray) of F C (0). The conclusion stems from the fact that the extreme points (resp. rays) of F C (0) are extreme points (resp. rays) of C , see the proof of the main theorem in [START_REF] Klee | On a theorem of Dubins[END_REF].

Proof of Corollary 1

Now, assume that the vector space K def.

= rec(C ) ∩ (-rec(C )) is non trivial (otherwise the conclusion follows from Theorem 1). We note that for any u ∈ C , the convex function v → R(u + v) is upper bounded by t on K, hence is constant. As a result, possibly replacing R with R + χ C , it is not restrictive to assume that R is invariant by translation along K. Now, let π K , π Φ(K) be the canonical quotient maps and define R and Φ by the commutative diagrams

E [-∞, ∞] E/K R π K R E R m E/K R m /Φ(K) Φ π K π Φ(K)

Φ

Note that R is a convex function and that Φ is a linear map with rank m-d, where d def.

= dim (Φ(K)). It is then natural to consider the problem = π Φ(K) (y). In other words, one still wishes to minimize R(u), but one is satisfied if the constraint Φu = y merely holds up to an additional term Φv, where v ∈ K. We observe that (P) and ( P) have the same value t , and the level set

C def.
= ũ ∈ E/K : R(ũ

) ≤ t = π K (C ) (30)
is convex linearly closed and contains no line. Let S be the solution set to ( P). Theorem 1 now describes the elements of the j-dimensional faces of S as convex combinations of m -d + j (resp. m -d + j -1) extreme points (resp. extreme points or points in an extreme ray) of C that we denote by q1 ,q 2 ,. . . , qr .

To conclude, we have obtained π K (p) = i θ i qi , for some θ ∈ R r + with i θ i = 1. Equivalently, since ψ -1 K (•, 0) provides one element in the corresponding class, this means that p ∈ ψ -1 K ( i θ i qi , 0)+K. We get the claimed result by linearity of ψ -1 K .

Remark 9. Incidentally, we note that for Y = {y}, the face F S {y} (p) is isomorphic (through ψ K ) to F π K (S {y} ) (π K (p)) × (K ∩ kerΦ).

  A typical example of inverse problem in the space of measures is min µ∈M(Ω) |µ|(Ω) s.t. Φµ = y

3 Abstract representer theorems 3 . 1

 31 Main resultOur main result describes the facial structure of the solution set to min u∈E R(u) s.t. Φu = y, (P)

Figure 1 :

 1 Figure 1: An illustration of theorem 1 for m = 2. The solution set S = C ∩Φ -1 ({y}) is made of an extreme point and an extreme ray. The extreme point is a convex combination of {e 0 , e 1 }. Depending on their position, the points in the ray are a convex combination of {e 0 , e 1 , e 2 } or a pair of points, one in ρ 1 and the other in ρ 2 .

Figure 2 :

 2 Figure 2: Taking the quotient by K = lin(C ) yields a level set C with no line. In this figure, to simplify the notation, we have omitted the isomorphism ψ K (i.e. in this figure C shoud be replaced with ψ K (C ), and similarly for S and Φ -1 ({y})).

Proposition 5 .

 5 Let B = {u ∈ B(Ω), Lu M(Ω) ≤ 1}. Then the extreme points of the set C K ⊥ = B ∩ K ⊥ are of the form ±L + δ x , for x ∈ Ω. Let f : R m → R ∪ {+∞} denote a convex function and define S = argmin u∈B(Ω) f (Φu) + Lu M(Ω) .

Figure 3 :

 3 Figure 3: Illustration for the total gradient variation problem min {T V (u) : Φ(u) = y}. Here, Φ is a linear mapping giving access to 3 measurements, y ∈ R 3 , by performing the mean of an image u of size 200 × 200 on 3 different disks represented in (a). The TV problem is solved using a primal-dual algorithm, also known as the Chambolle-Pock algorithm [12]. The recovered image is displayed in (b): it can be represented as the sum of 3 indicator functions of simple sets.

Extreme points, extremal rays, faces An extreme point of C is a point

  p ∈ C such that C \ {p} is convex. An extremal ray of C is a ray ρ ∈ C such that if x, y ∈ C and ]x, y[ intersects ρ, then ]x, y[⊂ ρ. If C contains the endpoint p of ρ (e.g. if C is linearly closed),this is equivalent to p being an extreme point of C and C \ ρ being convex.

	)
	is non trivial. The vector space lin(C) is called the lineality space of C. It
	corresponds to the largest vector space of invariant directions for C.
	If E is finite dimensional and C is closed, the recession cone coincides
	with the asymptotic cone.

  C (p) is the smallest face of p in C. One may check that C contains no line, as its recession cone rec( C), the projection of rec(C) onto W parallel to lin(C), is a salient convex cone.

				is nontrivial. In
	that case, letting W denote some linear supplement to lin(C) , we may
	write	C = C + lin(C), with	C def. = C ∩ W	(11)
	and the corresponding decomposition is unique (i.e. any element of C can be decomposed in a unique way as the sum of an element of C and lin(C)). The convex set C (isomorphic to the projection of C onto the quo-
	tient space E/lin(C)) is then linearly closed, and the decomposition of C
	in elementary faces is exactly given by the partition {F C (p) + lin(C)} p∈ C ,
	where F

  to some xn ≥ 0. Furthermore, using that {n : w n < 1} is finite and Fatou's lemma, it holds that

	n	xn ≤ lim inf k	n	x k n ≤ 1 and

n : wn≥1

Here, we follow the presentation of[START_REF] Gupta | Continuous-domain solutions of linear inverse problems with tikhonov vs. generalized tv regularization[END_REF].

In the rest of the paper, we omit the mention "at most", with the convention that some points may be chosen identical.

or, more precisely, by its variant when t = inf R, see remark 2.

In this example, to simplify the discussion, we assume that E has finite dimension.

Acknowledgments

This work was initially started by two different groups composed of A. Chambolle, F. de Gournay and P. Weiss on one side and C. Boyer, Y. De Castro and V. Duval on the other side. The authors realized that they were working on a similar topic when a few of them met at the Cambridge semester in mathematical imaging during the Isaac Newton Institute (Cambridge) semester "Variational methods and effective algorithms for imaging and vision", supported by EPSRC Grant N. EP/K032208/1. They therefore decided to write a joint paper and wish to thank the organizers for giving them this opportunity. This work initially started with the help of T. Pock through a few numerical experiments and with discussions with J. Fadili and C. Poon.

The work of A.C. was partially supported by a grant of the Simons Foundation.