A unifying representer theorem for inverse problems and machine learning

2019·Arxiv

Abstract

Abstract

Regularization addresses the ill-posedness of the training problem in machine learning or the reconstruction of a signal from a limited number of measurements. The method is applicable whenever the problem is formulated as an optimization task. The standard strategy consists in augmenting the original cost functional by an energy that penalizes solutions with undesirable behavior. The effect of regularization is very well understood when the penalty involves a Hilbertian norm. Another popular configuration is the use of an -norm (or some variant thereof) that favors sparse solutions. In this paper, we propose a higher-level formulation of regularization within the context of Banach spaces. We present a general representer theorem that characterizes the solutions of a remarkably broad class of optimization problems. We then use our theorem to retrieve a number of known results in the literature such as the celebrated representer theorem of machine leaning for RKHS, Tikhonov regularization, representer theorems for sparsity promoting functionals, the recovery of spikes, as well as a few new ones.

Mathematics Subject Classification (2010) 46N10 47A52 65J20 68T05

Keywords convex optimization regularization representer theorem inverse problem machine learning Banach space

Communicated by Tomaso Poggio

The research leading to these results has received funding from the Swiss National Science Foundation under Grant 200020-162343.

1 Introduction

A recurrent problem in science and engineering is the reconstruction of a multidimensional signal from a finite number of (possibly noisy) linear measurements , where the operator ) : ) symbolizes the linear measurement process. The machine-learning version of the problem is the determination of a function from a finite number of samples ) + where is a small perturbation term; it is a special case of the former with ). Since a function that takes values over the continuum is an infinite-dimensional entity, the reconstruction problem is inherently ill-posed.

The standard remedy is to impose an additional minimum-energy requirement which, in effect, regularizes the solution. A natural choice of regularization is a smoothness norm associated with some function space (typically, a Sobolev space), which results in the prototypical formulation of the problem as

An alternative version that is better suited for noisy data is

with an adequate choice of hyper-parameters and [1). We note that the unconstrained form (2) is a generalization of (1): the latter is recovered in the limit by taking 0.

The term “representer theorem” is typically used to designate a parametric formula—preferably, a linear expansion in terms of some basis functions— that spans the whole range of solutions, irrespective of the value of the data . Representer theorems are valued by practitioners because they indicate the way in which the initial problem can be recast as a finite-dimensional optimization, making it amenable to numerical computations. The other bene-fit is that the description of the manifold of possible solutions provides one with a better understanding of the effect of regularization. The best known example is the representer theorem for reproducing-kernel Hilbert spaces (RKHS), which states that the solution of (2) with ) and a Hilbertian regularization norm necessarily lives in a subspace of dimension M spanned by kernels centered on the data coordinates [7] [31] [36] [35] [43]. This theorem, in its extended version [42], is the foundation for the majority of kernel-based methods for machine learning, including regression, radial-basis functions, and support-vector machines [44] [23] [48]. There is also a whole line of generalizations of the concept that involves reproducing kernel Banach spaces (RKBS) [56] [57] [55]. More recently, motivated by the success of and total-variation regularization for compressed sensing [19] [14] [11], researchers have derived alternative representer theorems in order to explain the sparsifying effect of such penalties and their robustness to missing data [26] [52] [28] [8]. A representer theorem for measures has also been invoked to justify the use of the total-variation norm for the super-resolution localization of spikes [12] [17] [21] [37] (see, Section 4.1 for details).

In this paper, we present a unifying treatment of regularization by considering the problem from the abstract perspective of optimization in Banach spaces. Our motivation there is essentially two-fold: (1) to get a better “geometrical” understanding of the effect of regularization, and (2) to state a generic representer theorem that applies to a wide variety of objects describable as elements of some native Banach space. The supporting theory is developed in Section 2. Our formulation takes advantage of the notion of Banach conjugates which is explained in Section 2.1. We then immediately proceed with the presentation of our key result: a generalized representer theorem (Theorem 2) that is valid for arbitrary convex data terms and Banach spaces in general, including the non-reflexive ones. The proof that is developed Section 2.2 is rather soft (or “high-level”), as it relies exclusively on the powerful machinery of duality mappings and the Hahn-Banach theorem—in other words, there is no need for Gˆateaux derivatives nor subdifferentials, which are often invoked in such contexts. The resulting form of the solution in Theorem 2 is enlightening because it separates out the effect of the measurement operator from that of the regularization topology. Specifically, the measurement functionals in (1) or (2) specify a linear solution manifold that is then isometrically mapped into the primary space via the conjugate map J, which may or may not be linear, depending on wether the regularization norm is Hilbertian or not.

The theory is then complemented with concrete examples of usage of Theorem 2 to illustrate the power of the approach as well as its broad range of applicability. Section 3 is devoted to the scenario where the regularization norm is strictly convex, which ensures that the solution of the underlying minimization problem is unique. We make the link with the existing literature by deriving of a number of classical results: Sch¨olkopf’s generalized representer theorem for RKHS (Section 3.1), the closed-form solution of continuous-domain Tikhonov regularization with a Hilbertian norm (Section 3.2), and the connection with the theory of reproducing kernel Banach spaces (Section 3.3). In addition, we present a novel representer theorem for -norm regularization (Section 3.4). Then, in Section 4, we turn our attention to sparsity promoting regularization which is more challenging because the underlying Banach spaces are typically non-reflexive and non-convex. The enabling ingredient there is a recent result by Boyer et al. [8], which allows one to express the extreme points of the solution set in Theorem 2 as a linear combination of a few basic atoms that are selected adaptively (Theorem 3). This result, in its simplest incarnation with ), supports the well-documented sparsifying effect of -norm minimization, which is central to the theory of compressed sensing. By switching to a continuum, we obtain the representer theorem for )—the space of signed Radon measures on a compact domain —(Section 4.1), which is relevant to super-resolution localization. We then also derive a representer theorem for generalized total-variation (Section 4.2)—in the spirit of [53]—that justifies the use of sparse kernel expansions for machine learning, in line with the generalized LASSO [39].

2 Mathematical Formulation

2.1 Banach Spaces and Duality Mappings

The notion of Banach space—basically, a vector space equipped with a norm— is remarkably general. Indeed, the elements (or points) of a Banach space can be vectors (e.g., ), functions (e.g., )), sequences (e.g., )), continuous linear functionals (e.g., where is the dual of some primary Banach space), vector-valued functions (e.g., ) with )), matrices (), and, even, bounded linear operators from a Banach space U (domain) to another Banach space V (range) (e.g., X )) [32].

Definition 1 A normed vector space X is a linear space equipped with a norm, henceforth denoted by . It is called a Banach space if it is complete in the sense that every Cauchy sequence in () converges to an element of X. It is said to be strictly convex if, for all such that , one has that + (1 1 for any (0, 1). Finally, a Hilbert space is a Banach space whose norm is induced by an inner product.

We recall that (the continuous dual of X) is the space of linear functionals that are continuous on X. It is a Banach space equipped with the dual norm

A direct implication of this definition is the generic duality bound

for any . In fact, (4) can be interpreted as the Banach generalization of the Cauchy-Schwarz inequality for Hilbert spaces. By invoking the Hahn-Banach theorem, one can also prove that the duality bound is sharp for any dual pair () of Banach spaces [41]. This remarkable property inspired Beurling and Livingston to introduce the notion of duality mapping and to identify conditions of uniqueness [4]. We like to view the latter as the generalization of the classical Riesz map R : or, rather, its inverse J: , which describes the isometric isomorphism between a Hilbert space H and its continuous dual [38]. The caveat with Banach spaces is that the duality mapping is not necessarily bijective nor even single-valued.

Definition 2 (Duality mapping) Let () be a dual pair of Banach spaces. Then, the elements and form a conjugate pair if they satisfy:

For any given , the set of admissible conjugates defines the duality mapping

which is a nonempty subset of . Whenever the duality mapping is a singleton (for instance, when is strictly convex), one also defines the corresponding duality operator J, which is such that .

We now list the properties of the duality mapping that are relevant for our purpose (see [4], [15, Proposition 4.7 p. 27, Proposition 1.4, p. 43], [45, Theorem 2.53, p. 43]).

Theorem 1 (Properties of duality mappings) Let () be a dual pair of Banach spaces. Then, the following holds:

condition is also necessary if X is reflexive. 5. When X is reflexive, the duality map is bijective if and only if both X and

The most favorable scenario is covered by Item 5. In that case, the duality map is invertible with ; that is, J, in conformity with the property that .

We now prove that the duality map is linear if and only if X = H is a Hilbert space. In that case, the unitary operator Jis precisely the inverse of the Riesz map R : .

Proposition 1 Let () be a dual pair of Banach spaces such that is strictly convex. Then, the duality map Jis linear if and only if X is a Hilbert space.

Proof First, we recall that all Hilbert spaces are strictly convex. Consequently, the indirect part of the statement is Riesz’ celebrated representation theorem, which identifies the canonical linear isometry Jbetween a Hilbert space and its dual [41]. As for the converse implication, we show that the underlying inner product is

Its bilinearity follows from the bilinearity of the duality product and the linearity of J, while the symmetry in u and v is obvious. Finally, the definition of the conjugate yields

which confirms that the bilinear form is positive-semi-definite. Hence, it is the inner product that induces the -norm.

As an example, we provide the expression of the (unique) Banach conjugate ) of a function with 1 and

This formula is intimately connected to H¨older’s inequality. In particular, the conjugation map with p = q = 2 is an identity.

2.2 General representer theorem

We now make use of the powerful tool of conjugation to characterize the solution of a broad class of unconstrained optimization problems in Banach space. Let us note that the result also covers the equality constraint of Problem (1) if one selects the barrier functional

Theorem 2 (General Banach representer theorem) Let us consider the following setting:

lower-semi-continuous and convex in its second argument. – Some arbitrary strictly increasing and convex function .

Then, for any fixed , the solution set of the generic optimization problem

is nonempty, convex, and weak-compact. If E is strictly convex (or if it imposes the equality )), then any solution is a ()-conjugate of a common

with a suitable set of weights ; i.e., ). Moreover, if X is strictly convex and ) is strictly convex, then the solution is unique with (Banach conjugate of ). In particular, if X is a Hilbert space, then , where is the Riesz conjugate of .

The condition of unicity requires the strict convexity of both and . This applies to Banach spaces such as ) (up to some isometric isomorphism) with 1 and the canonical choice of regularization with being strictly convex. While the solution of (8) also exists for Banach spaces such as or , the uniqueness is usually lost in such non-reflexive scenarios (see Section 4).

Proof The proof uses standard arguments in convex analysis together with a dual reformulation of the problem inspired from the interpretation of best interpolation given by Carl de Boor in [6].

(i) Existence and Reformulation as a Generalized Interpolation Problem. First, we recall that the basic properties of (weak lower semi-) continuity and coercivityare preserved though functional composition. The functional is convex, (norm-)continuous and coercive on from the definition of a norm. Since is strictly increasing and convex, it is necessarily continuous and coercive. This ensures that ) is endowed with the same three basic properties. The linear measurement operator is continuous on by assumption (because of the canonical embedding of a Banach space in its bidual) and trivially convex. Since is lower semicontinuous on and convex, this implies by composition the lower-semicontinuity and convexity of . Consequently, the functional ) is (weakly) lower-semicontinuous, convex, and coercive on , which guarantees the existence of the solution (as well as the convexity and closedness of the solution set) by a standard argument in convex analysis [22]—see [28, Proposition 8] for the non-reflexive case. Moreover, unicity is ensured when ) is strictly convex which happens to be the case when both and ) are strictly convex.

For the general (not necessarily unique) scenario, we take advantage of the strict convexity of ) to show that all minimizers of F(f) share a common measurement vector . To that end, we pick any two distinct solutions 2 with corresponding measurements ) and regularization cost ). The convexity of S implies that, for any (0, 1), + (1 with + (1 and 2. Let us now assume that . Then, by invoking the strictly convexity of ) and the convexity of ), we get that

which is a contradiction. It follows that which, in turn, implies that the optimal regularization cost is the same for all . Although is usually not known before hand, this property provides us with a convenient parametric characterization of the solution set as

where z ranges over . In this reformulation, we also exploit the property that the minimization of is equivalent to that of ) because the mapping between the two quantities is monotone.

The linear independence of the functionals ensures that any has the unique expansion . Based on this representation, we define the linear functional

with fixed. By construction, is continuouswith , where . Moreover, the Hahn-Banach theorem ensures the existence of a continuous, norm-preserving extension of to the whole Banach space X; that is, an element such that

The connection between the above statement and the generalized interpolation problem (10) is that the complete set of continuous extensions of to is given by

with the property that

The next fundamental observation is that because both spaces are of finite dimension M and, hence, reflexive. Consequently, for any , we have that and , as well as for all because of (11). Since and , this yields

which implies that ) with the duality mapping from X to .

When is strictly convex, the situation is simpler because the duality mapping from X to is single-valued and the solution is unique. Moreover, the latter conjugate map is linear if and only if X is a Hilbert space, by Proposition 1.

Note that the existence of the conjugate of is essential to the argumentation. This is the reason why the problem is formulated with subject to the hypothesis that (weakcontinuity). These considerations are inconsequential in the simpler reflexive scenario where the role of the two spaces is interchangeable since . The hypothesis of linear independence of the in Theorem 2 is only made for convenience. When it does not hold, one can adapt the proof by picking a basis of of reduced dimension , which then leads to a corresponding reduction in the number of degrees of freedom of the solution.

In the sequel, as we shall apply Theorem 2 to concrete scenarios, we shall implicitly interpret in (8) as a function (or, eventually, a vector) rather than a continuous linear functional on X (the abstract definition of an element of the dual space). This is acceptable provided that the defining space is isometrically embedded in some classical function spaces such as ) because of the bijective mapping (isometric isomorphism) that relates the two types of entities; for instance, there is a unique element of ) with p the conjugate exponent of [1) such that the linear functional can be specified as and vice versa. This allows us to identify as ), while it also gives a precise meaning to identities such as .

3 Strictly-Convex Regularization

The solution of the optimization problem in Theorem 2 is unique whenever the Banach space X (or ) is reflexive and strictly convex. This is the setting that has been studied the most in the literature. We now illustrate the unifying character of Theorem 2 by using it to retrieve the key results in this area; that is, the classical kernel methods for machine learning in RKHS (Section 3.1), the resolution of linear inverse problems with Tikhonov regularization (Section 3.2), and the link with reproducing kernel Banach spaces (Section 3.3). In addition, we make use of the conjugate map to present a novel perspective on regularization for p > 1 in Section 3.4.

3.1 Kernel/RKHS Methods in Machine Learning

Here, the search space is a reproducing-kernel Hilbert space on denoted by H with , where is the underlying inner product. The predual space is which agrees with (reflexive scenario). The RKHS property [3] is equivalent to the existence of a (unique) positive-definite kernel (the reproducing kernel of H) such that

for all and any .

In the context of machine learning, the loss function E is usually chosen to be additive with [43] [29]. Given a series of data pointswith , the learning problem is then to estimate a function such that

where is an adjustable regularization parameter. In functional terms, the reproducing kernel represents the Schwartz kernel [27] [46] of the Riesz map R : so that ). The application of Theorem 2 with then immediately yields the parametric form of the solution

which is a linear kernel expansion. The optimality of such kernel expansions is precisely the result stated in Sch¨olkopf’s representer theorem for RKHS [42]. Moreover, by invoking the reproducing-kernel property (13) with f = , one readily finds that , where the Gram matrix is specified by [). By injecting the parametric form of the solution into the cost functional in (14), we then end up with the equivalent finite-dimensional minimization task

which yields the exact solution of the original infinite-dimensional optimization problem. In short, (16) is the optimal dicretization of the functional optimization problem (15), which is then readily transcribable into a numerical implementation using standard (finite-dimensional) techniques.

3.2 Tikhonov Regularization

Tikhonov regularization is a classical approach for dealing with ill-posed linear inverse problems [50] [30]. The goal there is to recover a function from a noisy or imprecise series of linear measurements , where is the disturbance term. By using the same functional framework as in Section 3.1 with , and , one formulates the recovery problem as

The application of Theorem 2 then yields a solution that takes the parametric form

with , where R is the Riesz map . The next fundamental observation is that the bilinear form (is actually the inner product for the dual space leading to . In fact, by using the property that and are Hilbert conjugates, we have that

which, somewhat remarkably, shows that the underlying system matrix is equal to the Gram matrix of the basis .

Therefore, by injecting (18) into the cost functional in (17), we are able to reformulate the initial optimization problem as the finite-dimensional minimization

where the system/Gram matrix with [is symmetric positive-definite. By differentiating the quadratic form in (20) with respect to a and setting the gradient to zero, we readily derive the very pleasing closed-form solution

under the implicit assumption that H is invertible. We note that the latter is equivalent to the linear independence of the (resp., the linear independence of the due to the Riesz pairing).

3.3 Reproducing Kernel Banach Spaces

The concept of reproducing kernel Banach space, which is the natural generalization of RKHS, was introduced and investigated by Zhang and Xu in [56] [55]. Similar to the Hilbertian case, one can identify the RKBS property as follows.

Definition 3 A strictly convex and reflexive Banach space B of functions on is called a reproducing kernel Banach space (RKBS) if for any . Then, the unique representer when indexed by x is called the reproducing kernel of the Banach space.

It is then of interest to consider the Banach variant of (14) that involves a slightly more general regularization term: Given the data points, m = 1, . . . , M, we want to find the unique solution of the optimization problem

where the loss function is convex in its second argument and the regularization strength modulated by the function , which is convex and strictly increasing. Since the space B is reflexive by assumption, the optimization problem falls into the framework of Theorem 2 with and and , where the latter inclusion is guaranteed by the RKBS property. We thereby obtain the parametric form of the solution as

with appropriate coefficients (, where the expression on the righthand side has been included in order to make the connection with the Banach reproducing kernel, as in [56] [57]. Due to the homogeneity and invertibility of the duality mapping (see Theorem 1), we have that J). This implies that (23) yields a linear expansion in terms of kernels if and only if is linear. We note that the latter condition together with Definition 3 is equivalent to B = H being a RKHS (by Proposition 1), which brings us back to the classical setting of Section 3.1. The same argumentation is also extendable to the vector-valued setting which has been considered by various authors both for RKHS and RKBS settings [1] [33] [58]. We also like to point our that our analysis is compatible with some recent results of Combettes et al. [16], where the corresponding conditions of optimality are stated using subdifferentials.

3.4 Towards Compressed Sensing: -Norm Regularization

A classical problem in signal processing is to recover an unknown discrete signal from a set of corrupted linear measurements , m = 1, . . . , M. The measurement vectors specify the system matrix . When M (the number of measurements) is less than N (the size of the unknown signal s), the reconstruction problem is a priori ill-posed, and strongly so when (compressedsensing scenario). However, if the original signal is known to be sparse (i.e., with ) and the system matrix H satisfies some “incoherence” properties, then the theory of compressed sensing provides general guarantees for a stable recovery [26] [14] [19]. The computational strategy then is to impose an regularization (with p small to favor sparsity) on the solution and to formulate the reconstruction problem as

with . The traditional choice for compressed sensing is p = 1, which is the smallest exponent that still results in a convex optimization problem.

We now show how we can use Theorem 2 to characterize the effect of such a regularization for (1). The corresponding Banach space is () whose predual is ) with + the underlying norms are strictly convex for p > 1, which guarantees that the solution is unique, irrespective of M and H. By introducing the dual signal and by using the known form of the corresponding Banach q-to-p duality map J, we then readily deduce that the solution can be represented as

for a suitable value of the (dual) parameter vector . While the exact value of a is data-dependent, (25) provides us with the description of the solution manifold of intrinsic dimension M. Another way to put it is that the fact that s minimizes (24) induces a nonlinear pairing between the data vector and the dual variable in (25). In particular, for p = 2, we have that , which confirms the well-known result that span. The latter also explains why classical quadratic/Tikhonov regularization performs poorly when M is much smaller than N.

4 Sparsity-Promoting Regularization

The limit caseof the previous scenario is p = 1 (CS) for which the norm is no longer strictly convex. To deal with such cases where the solution is potentially non-unique, we first recall the Krein-Milman theorem [41, p. 75], which allows us to describe the weak-compact solution set S in Theorem 2 as the convex hull of its extreme points. We then invoke a recent result by Boyer et al. that yields the following characterization of the extremal points of Problem (8).

Theorem 3 All extremal points of the solution set S of Problem (8) can be expressed as

for some 1 where the are some extremal points of the unit “regularization” ball : and (is a vector of appropriate weights.

The above is a direct corollary of [8, Theorem 1 with j = 0] applied to an extreme point of the equivalent generalized interpolation problem (10). We also note that the existence of a minimizer of the form (26) has been established independently by Bredies and Carioni [9] in a framework that is even more general than the one considered here. The latter property is also directly deducible from the reduced problem (10) and a classical result by Singer [47, Lemma 1.3, p. 169]. It remains that the existence of a global minimizer of the form (26) is not as strong a result as Theorem 3, which tells us the characterization applies for all extremal points of S. Moreover, it should be pointed out that the result in Theorem 3 is not particularly informative for strictly convex spaces such as ) or ) with (1) for which all unit vectors (with ball. Indeed, since the corresponding solution is unique (by Theorem 2), we trivially have that with .

By contrast, the characterization in Theorem 3 is highly relevant for the non-strictly convex space ) whose extreme vectors are intrinsically sparse; i.e, for some fixed offset . Here, ] denotes the Kronecker impulse which is such that Hence, the outcome is that the use of the penalty (e.g., (24) with p = 1) has a tendency to induce sparse solutions with , which is the flavor of the representer theorem(s) in [52]. Two other practically-relevant examples that fall in the non-strictly convex category are considered next.

4.1 Super-resolution Localization of Spikes

The space of continuous functions over a compact domain equipped with the supremum (or ) norm is a classical Banach space denoted by

Its continuous dual

is the Banach space of bounded (signed) Radon measures on (by the RieszMarkov representation theorem [40]). Moreover, it is well known that the extreme points of the unit ball in ) are point measures (a.k.a. Dirac impulses) of the form ) for some , with the property that

for any ). For a series of (independent) analysis functions ) (e.g., Fourier exponentials), we can invoke Theorems 2 and 3 with ) to deduce that the extreme points of the problem

are inherently sparse. This means that there necessarily exists at least one minimizer of the form

with , (, and . The fact that (30) admits a global solution whose representation is given by (31) is a result that can be traced back to the work of Fisher and Jerome in [25, Theorem 1]. This optimality result is the foundation for a recent variational method for super-resolution localization that was investigated by a number of authors [10,12, 24]. Besides the development of grid-free optimization schemes, researchers have worked out the conditions on and under which (30) can provide a perfect recovery of spike trains of the form given by (31) with a small [13, 17,37]. The remarkable finding is that there are many configurations for which super-resolution recovery is guaranteed, with an accuracy that only depends on the signal-to-noise ratio and the minimal spacing between neighbouring spikes.

4.2 Sparse Kernel Expansions

Schwartz’ space of smooth and rapidly decaying functions on is denoted by ). Its continuous dual is ): the space of tempered distributions. In this section, L : ) is an invertible operator with continuous inverse L: ). We also assume that the generalized impulse response of Lis a bivariate function of slow growth . In other words, the inverse operator Lhas the explicit integral representation

for any ). In conformity with the nomenclature of [53], the native Banach space foris

It is isometrically isomorphic to ) (the space of bounded Radon measures on ). This is to say that the operators Lhave restrictions L : ) and L: ) that are isometries. Consequently, we can apply Theorem 2 to deduce that the generic learning problem

admits a solution, albeit not necessarily a unique one since the underlying search space )—or, equivalently, the parent space )—is neither reflexive nor strictly convex.

In order to refine the above statement with the help of Theorem 3, we first observe that the extreme points of the unit ball in ) take the form ) with , which is consistent with the result in Section 4.1 for ). Since the map L: ) is isometric, this allows us to identify the extreme points of the unit ball in ) as

where is the kernel of the operator in (32). Consequently, we can invoke Theorem 3 to prove that the extreme points of Problem (34) are all expressible as

with parameters , and (. Moreover, since L) and larization cost is , which makes an interesting connection with -norm minimization and the generalized LASSO [49] [39]. To sum up, the solution (36) has a kernel expansion that is similar to (15), with the important twist that the kernel centers are adaptive, meaning that their location as well as their cardinality is data-dependent. In effect, it is the underlying -norm penalty that helps reducing the number of active kernels, thereby producing a sparse solution. We should also point out that the form of the solution is compatible with the empirical method of moving and learning the data centers in kernel expansions (see [35, Section IV]) with the important difference that the present proposal is purely variational.

When L : ) is linear shift-invariant (LSI) with frequency response ), then ) with

where the operator : ) is the generalized inverse Fourier transform.

The overarching message in the optimality result of the present section is that the choice of the regularization operator L in (34) predetermines the parametric form of the kernel in (36). Now, in light of (37), we can choose to specify first a kernel and then infer the frequency response of the corresponding regularization operator

Now, the necessary and sufficient condition for the continuity of L : ) is that the function be smooth and slowly growing [46]. A parametric class of kernels that meets this admissibility requirement is the super-exponential family

with (0, 2). The limit case with corresponding frequency response in (38) (inverse of a Gaussian) fails to be slowly increasing.

5 Conclusion

We have shown that the fundamental ingredient in the quest for a representer theorem is the identification and characterization of a dual pair of Banach spaces that is linked to the regularization functional. The main result of the paper is expressed by Theorem 2, which is valid for Banach spaces in general. This characterization of the solution of the general optimization problem (8) is directly exploitable in the reflexive and strictly convex scenario—in which case the solution is also known to be unique—whenever the duality mapping is known. While our formulation also offers interesting insights for certain non-strictly convex and sparsity-promoting norms such as and its continuous-domain counterpart—the total variation and generalization thereof—it raises intriguing questions about the unicity of such solutions and the necessity to develop some corresponding numerical optimization schemes.

We have made the link with the existing literature in machine learning (regression) and the resolution of ill-posed inverse problems by considering several concrete cases, including reproducing kernel Hilbert spaces (RKHS) and compressed sensing. The conciseness and self-containedness of the proposed derivations is a good indication of the power of the approach.

Since the concept of Banach spaces is remarkably general, one can easily conceive of other variations around the common theme of regularization and representer theorems. Potential topics for further research include the use of nonstandard norms, the deployment of hybrid regularization schemes, vector-valued functions or feature maps [1], and the consideration of directsum spaces and semi-norms, as in the theory of splines [7] [20] [54] [18] [34] [53]. In short, there is ample room for additional theoretical and practical investigations, in direct analogy with what has been accomplished during the past few decades in the simpler but more restrictive context of RKHS [2,1]. Interestingly, there also appears to be a link with deep neural/kernel networks, as has been demonstrated recently [5,51].

Acknowledgments

The research was partially supported by the Swiss National Science Foundation under Grant 200020-162343. The author is thankful to Julien Fageot, Shayan Aziznejad, Pakshal Bohra, Quentin Denoyelle and Philippe Th´evenaz for helpful comments on the manuscript.

References

1. Alvarez, M.A., Rosasco, L., Lawrence, N.D.: Kernels for vector-valued functions: A review. Foundations and Trends in Machine Learning 4(3), 195–266 (2012)

2. Argyriou, A., Micchelli, C.A., Pontil, M.: When is there a representer theorem? Vector versus matrix regularizers. Journal of Machine Learning Research 10(Nov), 2507–2529 (2009)

3. Aronszajn, N.: Theory of reproducing kernels. Transactions of the American Mathe- matical Society 68(3), 337–404 (1950)

4. Beurling, A., Livingston, A.E.: A theorem on duality mappings in Banach spaces. Arkiv f¨or Matematik 4(5), 405–411 (1962)

5. Bohn, B., Rieger, C., Griebel, M.: A representer theorem for deep kernel learning. Jour- nal of Machine Learning Research 20(64), 1–32 (2019)

6. de Boor, C.: On “best” interpolation. Journal of Approximation Theory 16(1), 28–42 (1976)

7. de Boor, C., Lynch, R.E.: On splines and their minimum properties. Journal of Math- ematics and Mechanics 15(6), 953–969 (1966)

8. Boyer, C., Chambolle, A., De Castro, Y., Duval, V., De Gournay, F., Weiss, P.: On representer theorems and convex regularization. SIAM Journal of Optimization 29(2), 1260–1281 (2019)

9. Bredies, K., Carioni, M.: Sparsity of solutions for variational inverse problems with finite-dimensional data. Calculus of Variations and Partial Differential Equations 59(14), 26 (2020)

10. Bredies, K., Pikkarainen, H.K.: Inverse problems in spaces of measures. ESAIM: Control, Optimisation and Calculus of Variations 19(1), 190–218 (2013)

11. Bruckstein, A.M., Donoho, D.L., Elad, M.: From sparse solutions of systems of equations to sparse modeling of signals and images. SIAM Review 51(1), 34–81 (2009)

12. Cand`es, E.J., Fernandez-Granda, C.: Super-resolution from noisy data. Journal of Fourier Analysis and Applications 19(6), 1229–1254 (2013)

13. Cand`es, E.J., Fernandez-Granda, C.: Towards a mathematical theory of super- resolution. Communications on Pure and Applied Mathematics 67(6), 906–956 (2014)

14. Cand`es, E.J., Romberg, J.: Sparsity and incoherence in compressive sampling. Inverse Problems 23(3), 969–985 (2007)

15. Cioranescu, I.: Geometry of Banach Spaces, Duality Mappings and Nonlinear Problems, vol. 62. Springer Science & Business Media (2012)

16. Combettes, P.L., Salzo, S., Villa, S.: Regularized learning schemes in feature banach spaces. Analysis and Applications 16(01), 1–54 (2018)

17. Denoyelle, Q., Duval, V., Peyr´e, G.: Support recovery for sparse super-resolution of positive measures. Journal of Fourier Analysis and Applications 23(5), 1153–1194 (2017)

18. Dodu, F., Rabut, C.: Irrotational or divergence-free interpolation. Numerische Mathe- matik 98, 477–498 (2004)

19. Donoho, D.L.: Compressed sensing. IEEE Transactions on Information Theory 52(4), 1289–1306 (2006)

20. Duchon, J.: Splines minimizing rotation-invariant semi-norms in Sobolev spaces. In: W. Schempp, K. Zeller (eds.) Constructive Theory of Functions of Several Variables, pp. 85–100. Springer-Verlag, Berlin (1977)

21. Duval, V., Peyr´e, G.: Exact support recovery for sparse spikes deconvolution. Founda- tions of Computational Mathematics 15(5), 1315–1355 (2015)

22. Ekeland, I., Temam, R.: Convex Analysis and Variational Problems, Classics in Applied Mathematics, vol. 28. SIAM (1999)

23. Evgeniou, T., Pontil, M., Poggio, T.: Regularization networks and support vector ma- chines. Advances in Computational Mathematics 13(1), 1–50 (2000)

24. Fernandez-Granda, C.: Super-resolution of point sources via convex programming. In- formation and Inference 5, 251–303 (2016)

25. Fisher, S.D., Jerome, J.W.: Spline solutions to extremal problems in one and several variables. Journal of Approximation Theory 13(1), 73–83 (1975)

26. Foucart, S., Rauhut, H.: A Mathematical Introduction to Compressive Sensing. Springer (2013)

27. Gelfand, I.M., Vilenkin, N.Y.: Generalized Functions. Vol. 4. Applications of Harmonic Analysis. Academic Press, New York, USA (1964)

28. Gupta, H., Fageot, J., Unser, M.: Continuous-domain solutions of linear inverse problems with Tikhonov versus generalized TV regularization. IEEE Transactions on Signal Processing 66(17), 4670–4684 (2018)

29. Hofmann, T., Sch¨olkopf, B., Smola, A.J.: Kernel methods in machine learning. Annals of Statistics 36(3), 1171–1220 (2008)

30. Karayiannis, N.B., Venetsanopoulos, A.N.: Regularization theory in image restoration— The stabilizing functional approach. IEEE Transactions on Acoustics, Speech and Signal Processing 38(7), 1155–1179 (1990)

31. Kimeldorf, G., Wahba, G.: Some results on Tchebycheffian spline functions. Journal of Mathematical Analysis and Applications 33(1), 82–95 (1971)

32. Megginson, R.E.: An Introduction to Banach Space Theory. Springer (1998)

33. Micchelli, C.A., Pontil, M.: On learning vector-valued functions. Neural Computation 17(1), 177–204 (2005)

34. Mosamam, A., Kent, J.: Semi-reproducing kernel Hilbert spaces, splines and increment kriging. Journal of Nonparametric Statistics 22(6), 711–722 (2010)

35. Poggio, T., Girosi, F.: Networks for approximation and learning. Proceedings of the IEEE 78(9), 1481–1497 (1990)

36. Poggio, T., Girosi, F.: Regularization algorithms for learning that are equivalent to multilayer networks. Science 247(4945), 978–982 (1990)

37. Poon, C., Peyr´e, G.: Multidimensional sparse super-resolution. SIAM Journal on Math- ematical Analysis 51(1), 1–44 (2019)

38. Riesz, M.: Sur les fonctions conjugu´ees. Mathematische Zeitschrift 27, 218–244 (1927)

39. Roth, V.: The generalized LASSO. IEEE Transactions on Neural Networks 15(1), 16–28 (2004)

40. Rudin, W.: Real and Complex Analysis, 3rd edn. McGraw-Hill, New York (1987)

41. Rudin, W.: Functional Analysis, 2nd edn. McGraw-Hill, New York (1991). McGraw-Hill Series in Higher Mathematics

42. Sch¨olkopf, B., Herbrich, R., Smola, A.J.: A generalized representer theorem. In: D. Helmbold, B. Williamson (eds.) Computational Learning Theory, pp. 416–426. Springer Berlin Heidelberg (2001)

43. Sch¨olkopf, B., Smola, A.J.: Learning with Kernels: Support Vector Machines, Regular- ization, Optimization, and Beyond. MIT press (2002)

44. Sch¨olkopf, B., Sung, K.K., Burges, C.J.C., Girosi, F., Niyogi, P., Poggio, T., Vapnik, V.: Comparing support vector machines with Gaussian kernels to radial basis function classifiers. IEEE Transactions on Signal Processing 45(11), 2758–2765 (1997)

45. Schuster, T., Kaltenbacher, B., Hofmann, B., Kazimierski, K.S.: Regularization Methods in Banach Spaces, vol. 10. Walter de Gruyter (2012)

46. Schwartz, L.: Th´eorie des Distributions. Hermann, Paris (1966)

47. Singer, I.: Best Approximation in Normed Linear Spaces by Elements of Linear Subspaces. Springer-Verlag, Berlin (1970)

48. Steinke, F., Sch¨olkopf, B.: Kernels, regularization and differential equations. Pattern Recognition 41(11), 3271–32286 (2008)

49. Tibshirani, R.: Regression shrinkage and selection via the Lasso. Journal of the Royal Statistical Society. Series B 58(1), 265–288 (1996)

50. Tikhonov, A.N.: Solution of incorrectly formulated problems and the regularization method. Soviet Mathematics 4, 1035–1038 (1963)

51. Unser, M.: A representer theorem for deep neural networks. Journal of Machine Learning Research 20(110), 1–30 (2019)

52. Unser, M., Fageot, J., Gupta, H.: Representer theorems for sparsity-promoting ularization. IEEE Transactions on Information Theory 62(9), 5167–5180 (2016)

53. Unser, M., Fageot, J., Ward, J.P.: Splines are universal solutions of linear inverse prob- lems with generalized-TV regularization. SIAM Review 59(4), 769–793 (2017)

54. Wahba, G.: Spline Models for Observational Data. Society for Industrial and Applied Mathematics, Philadelphia, PA (1990)

55. Xu, Y., Ye, Q.: Generalized Mercer kernels and reproducing kernel Banach spaces, vol.

258. Memoirs of the American Mathematical Society (2019)

56. Zhang, H., Xu, Y., Zhang, J.: Reproducing kernel Banach spaces for machine learning. Journal of Machine Learning Research 10, 2741–2775 (2009)

57. Zhang, H., Zhang, J.: Regularized learning in Banach spaces as an optimization problem: representer theorems. Journal of Global Optimization 54(2), 235–250 (2012)

58. Zhang, H., Zhang, J.: Vector-valued reproducing kernel Banach spaces with applications to multi-task learning. Journal of Complexity 29(2), 195–215 (2013)

designed for accessibility and to further open science