b

DiscoverSearch
About
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  ℓ1-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.

A recurrent problem in science and engineering is the reconstruction of a multidimensional signal  f : Rd → Rfrom a finite number of (possibly noisy) linear measurements  y = (ym) = ν(f) ∈ RM, where the operator  ν = (νm) :  f �→ν(f) = (⟨ν1, f⟩, . . . , ⟨νM, f⟩) symbolizes the linear measurement process. The machine-learning version of the problem is the determination of a function f : Rd → Rfrom a finite number of samples  ym = f(xm) +  ǫmwhere  ǫmis a small perturbation term; it is a special case of the former with  νm = δ(·−xm). 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  X ′(typically, a Sobolev space), which results in the prototypical formulation of the problem as

image

An alternative version that is better suited for noisy data is

image

with an adequate choice of hyper-parameters  λ ∈ R+and  p ∈[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 y ∈ RM. 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  ⟨νm, f⟩ = f(xm) and a Hilbertian regularization norm necessarily lives in a subspace of dimension M spanned by kernels centered on the data coordinates  xm[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  ℓ1and 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  ν1, . . . , νMin (1) or (2) specify a linear solution manifold that is then isometrically mapped into the primary space via the conjugate map JX : X → X ′, 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  ℓp-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 X ′ = ℓ1(Z), supports the well-documented sparsifying effect of  ℓ1-norm minimization, which is central to the theory of compressed sensing. By switching to a continuum, we obtain the representer theorem for  X ′ = M(Ω)—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.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.,  v ∈ RN), functions (e.g.,  f ∈ L2(Rd)), sequences (e.g., u[·] ∈ ℓ1(Z)), continuous linear functionals (e.g.,  f ∈ X ′where  X ′is the dual of some primary Banach space), vector-valued functions (e.g.,  f = (f1, . . . , fN) with  fn ∈ L2(Rd)), matrices (e.g., X ∈ RN×N), and, even, bounded linear operators from a Banach space U (domain) to another Banach space V (range) (e.g., X  ∈ L(U, V)) [32].

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

We recall that  X ′(the continuous dual of X) is the space of linear functionals  u : v �→ ⟨u, v⟩ △= u(v) ∈ Rthat are continuous on X. It is a Banach space equipped with the dual norm

image

A direct implication of this definition is the generic duality bound

image

for any  u ∈ X, v ∈ X ′. 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 (X, X ′) 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 :  H′ → Hor, rather, its inverse JH = R−1:  H → H′, which describes the isometric isomorphism between a Hilbert space H and its continuous dual  H′[38]. The caveat with Banach spaces is that the duality mapping is not necessarily bijective nor even single-valued.

Definition 2 (Duality mapping) Let (X, X ′) be a dual pair of Banach spaces. Then, the elements  v∗ ∈ X ′and  v ∈ Xform a conjugate pair if they satisfy:

image

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

image

which is a nonempty subset of  X ′. Whenever the duality mapping is a singleton (for instance, when  X ′is strictly convex), one also defines the corresponding duality operator JX : X → X ′, which is such that  JX (v) = {v∗ = JX {v}}.

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 (X, X ′) be a dual pair of Banach spaces. Then, the following holds:

image

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

image

The most favorable scenario is covered by Item 5. In that case, the duality map is invertible with  v = (v∗)∗ = JX ′JX {v}; that is, J−1X = JX ′, in conformity with the property that  X ′′ = X.

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 JH : H → H′is precisely the inverse of the Riesz map R :  H′ → H.

Proposition 1 Let (X, X ′) be a dual pair of Banach spaces such that  X ′is strictly convex. Then, the duality map JX : X → X ′, v �→ JX {v} = v∗is 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 JX = R−1between a Hilbert space and its dual [41]. As for the converse implication, we show that the underlying inner product is

image

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

image

which confirms that the bilinear form  ⟨·, ·⟩Xis positive-semi-definite. Hence, it is the inner product that induces the  ∥ · ∥X-norm.

As an example, we provide the expression of the (unique) Banach conjugate v∗ = JX {v} ∈ Lq(Rd) of a function  v ∈ Lp(Rd)\{0}with 1  < p < ∞and

image

This formula is intimately connected to H¨older’s inequality. In particular, the L2conjugation 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

image

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

image

lower-semi-continuous and convex in its second argument. Some arbitrary strictly increasing and convex function  ψ : R+ → R+.

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

image

is nonempty, convex, and weak∗-compact. If E is strictly convex (or if it imposes the equality  y = ν(f)), then any solution  f0 ∈ S ⊂ X ′is a (X ′, X)-conjugate of a common

image

with a suitable set of weights  a ∈ RM; i.e.,  S ⊆ JX (ν0). Moreover, if X is strictly convex and  f �→ ψ(∥f∥X ′) is strictly convex, then the solution is unique with  f0 = JX {ν0} ∈ X ′(Banach conjugate of  ν0). In particular, if X is a Hilbert space, then  f0 = �Mm=1 amν∗m, where  ν∗mis the Riesz conjugate of νm.

The condition of unicity requires the strict convexity of both  ψ : R+ → Rand  f �→ ∥f∥X ′. This applies to Banach spaces such as  X ′ =�Lq(Rd)�′ =Lp(Rd) (up to some isometric isomorphism) with 1  < p < ∞and the canonical choice of regularization  R(f) = λ∥f∥pLpwith  ψ(t) = λ|t|pbeing strictly convex. While the solution of (8) also exists for Banach spaces such as  M(Rd) =�C0(Rd)�′or  L∞(Rd) =�L1(Rd)�′, 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 coercivity1are preserved though functional composition. The functional f �→ ∥f∥X ′is convex, (norm-)continuous and coercive on  X ′from the definition of a norm. Since  ψ : R+ → R+is strictly increasing and convex, it is necessarily continuous and coercive. This ensures that  f �→ ψ (∥f∥X ′) is endowed with the same three basic properties. The linear measurement operator  ν : X ′ → RNis continuous on  X ′by assumption (i.e., νm ∈ X ⇒ νm ∈ X ′′because of the canonical embedding of a Banach space in its bidual) and trivially convex. Since  z �→ E�y, z�is lower semicontinuous on  Rdand convex, this implies by composition the lower-semicontinuity and convexity of  f �→ E�y, ν(f)�. Consequently, the functional  f �→ F(f) = E�y, ν(f)�+ ψ (∥f∥X ′) is (weakly) lower-semicontinuous, convex, and coercive on  X ′, 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  f �→ F(f) is strictly convex which happens to be the case when both  z �→ E�y, z�and f �→ ψ (∥f∥X ′) are strictly convex.

For the general (not necessarily unique) scenario, we take advantage of the strict convexity of  E(y, ·) to show that all minimizers of F(f) share a common measurement vector  z0 = ν(f0) ∈ RM. To that end, we pick any two distinct solutions  fi ∈ S, i = 1,2 with corresponding measurements  zi = ν(fi) and regularization cost  ri = λψ(∥fi∥X ′). The convexity of S implies that, for any α ∈(0, 1),  f = αf1+ (1  − α)f2 ∈ Swith  z = ν(f) = αz1+ (1  − α)z2and F(f) = F(fi), i = 1,2. Let us now assume that  z1 ̸= z2. Then, by invoking the strictly convexity of  z �→ E(y, z) and the convexity of  f �→ λψ(∥f∥X ′), we get that

image

which is a contradiction. It follows that  zi = ν(fi) = z0which, in turn, implies that the optimal regularization cost  ri = r0is the same for all  fi ∈ S. Although z0 = ν(f0) ∈ RMis usually not known before hand, this property provides us with a convenient parametric characterization of the solution set as

image

where z ranges over  RM. In this reformulation, we also exploit the property that the minimization of  ∥f∥X ′is equivalent to that of  ψ(∥f∥X ′) because the mapping between the two quantities is monotone.

image

The linear independence of the functionals  νmensures that any  ν ∈ Nνhas the unique expansion  ν = �Mm=1 amνm. Based on this representation, we define the linear functional

image

with  z = z0fixed. By construction,  ζis continuous�Nν, ∥ · ∥X� c.−−→ Rwith |ζ(ν)| ≤ ∥ζ∥ ∥ν∥X, where  ∥ζ∥ = supν∈Nν: ∥ν∥X =1 ζ(ν) < ∞. 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  f0 ∈ X ′such that

image

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

image

with the property that

image

The next fundamental observation is that  Nν =�N ′ν�′because both spaces are of finite dimension M and, hence, reflexive. Consequently, for any  ν0 ∈JX (ζ) ⊆�N ′ν�′ = Nν, we have that  ∥ν0∥X = ∥ζ∥and  ζ(ν0) = ∥ν0∥2X, as well as  ∥ν0∥X = ∥f0∥X ′for all  f0 ∈ Sz0because of (11). Since  f0 ∈ U ⊂ X ′and ν0 ∈ Nν ⊂ X, this yields

image

which implies that  f0 ∈ JX (ν0) with  JXthe duality mapping from X to  X ′.

image

When  X ′is strictly convex, the situation is simpler because the duality mapping from X to  X ′is single-valued and the solution  f0 ∈ X ′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  ν0 ∈ Nν ⊂ Xis essential to the argumentation. This is the reason why the problem is formulated with  f ∈X ′subject to the hypothesis that  ν1, . . . , νM ∈ X(weak∗continuity). These considerations are inconsequential in the simpler reflexive scenario where the role of the two spaces is interchangeable since  X = X ′′. The hypothesis of linear independence of the  νmin Theorem 2 is only made for convenience. When it does not hold, one can adapt the proof by picking a basis of  Nνof reduced dimension  M ′ < M, which then leads to a corresponding reduction in the number  M ′of degrees of freedom of the solution.

In the sequel, as we shall apply Theorem 2 to concrete scenarios, we shall implicitly interpret  f ∈ X ′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  X ′is isometrically embedded in some classical function spaces such as Lp(Rd) because of the bijective mapping (isometric isomorphism) that relates the two types of entities; for instance, there is a unique element of  f ∈ Lp(R) with p the conjugate exponent of  q ∈[1, ∞) such that the linear functional ζ ∈�Lq(Rd)�′can be specified as  ζ(g) = ⟨f, g⟩ =�Rd f(x)g(x)dxand vice versa. This allows us to identify  ζ = ζfas  f ∈ Lp(Rd), while it also gives a precise meaning to identities such as  Lp(Rd) =�Lq(Rd)�′.

The solution of the optimization problem in Theorem 2 is unique whenever the Banach space X (or  X ′) 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 ℓpregularization for p > 1 in Section 3.4.

3.1 Kernel/RKHS Methods in Machine Learning

Here, the search space  X ′is a reproducing-kernel Hilbert space on  Rddenoted by H with  ∥f∥2H = ⟨f, f⟩H, where  ⟨·, ·⟩His the underlying inner product. The predual space is  X = H′which agrees with  X ′ = H′′ = H(reflexive scenario). The RKHS property [3] is equivalent to the existence of a (unique) positive-definite kernel  rH : Rd × Rd → R(the reproducing kernel of H) such that

image

for all  f ∈ Hand any  xm ∈ Rd.

In the context of machine learning, the loss function E is usually chosen to be additive with  E(y, z) = �Mm=1 Em�ym, zm�[43] [29]. Given a series of data points�xm, ym�, m = 1, . . . , Mwith  xm ∈ Rd, the learning problem is then to estimate a function  f0 : Rd → Rsuch that

image

where  λ ∈ R+is an adjustable regularization parameter. In functional terms, the reproducing kernel represents the Schwartz kernel [27] [46] of the Riesz map R :  H′ → H : ν �→ ν∗ =�Rd rH(·, y)ν(y)dyso that  ν∗m(x) = R{δ(· −xm)}(x) = rH(x, xm). The application of Theorem 2 with  X ′ = Hthen immediately yields the parametric form of the solution

image

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 = rH(·, xn) ∈ H, one readily finds that  ∥f0∥2H = aT Ga, where the Gram matrix G ∈ RM×Mis specified by [G]m,n = rH(xm, xn). 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

image

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  f : Rd → Rfrom a noisy or imprecise series of linear measurements  ym = ⟨νm, f⟩ + ǫm, where  ǫmis the disturbance term. By using the same functional framework as in Section 3.1 with  ν1, . . . , νM ∈ H′ = X, and  X ′ = H′′ = H, one formulates the recovery problem as

image

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

image

with  ϕm = R{νm}, where R is the Riesz map  H′ = X → H = X ′. The next fundamental observation is that the bilinear form (νm, νn) �→ ⟨νm, R{νn}⟩is actually the inner product for the dual space  H′leading to  ⟨νm, ϕn⟩ =⟨νm, νn⟩H′. In fact, by using the property that  νmand  ϕm = ν∗mare Hilbert conjugates, we have that

image

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

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

image

where the system/Gram matrix  H ∈ RM×Mwith [H]m,n = ⟨νm, ϕn⟩ =⟨ϕm, ϕn⟩His 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

image

under the implicit assumption that H is invertible. We note that the latter is equivalent to the linear independence of the  ϕm(resp., the linear independence of the  νmdue 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 Rdis called a reproducing kernel Banach space (RKBS) if  δ(· − x) ∈ B′for any  x ∈ Rd. Then, the unique representer  rB(·, x) = JB′{δ(· − x)} ∈ Bwhen 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�xm, ym�Mm=1, m = 1, . . . , M, we want to find the unique solution of the optimization problem

image

where the loss function  E : R × R → Ris convex in its second argument and the regularization strength modulated by the function  ψ : R → R+, 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  X = B′and  X ′ = B′′ = Band  νm = δ(· − xm) ∈ B′, m = 1, . . . , M, where the latter inclusion is guaranteed by the RKBS property. We thereby obtain the parametric form of the solution as

image

with appropriate coefficients (am) ∈ RM, 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 JB′ {amr∗B(·, xm)} =amrB(·, xm). This implies that (23) yields a linear expansion in terms of kernels if and only if  M = 1 or if the duality map JB : B′ → Bis 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:  ℓp-Norm Regularization

A classical problem in signal processing is to recover an unknown discrete signal  s ∈ RNfrom a set of corrupted linear measurements  ym = hTms + ǫm, m = 1, . . . , M. The measurement vectors  h1, . . . , hM ∈ RNspecify the system matrix  H = [h1 h2 · · · hM]T ∈ RM×N. 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  M ≪ N(compressedsensing scenario). However, if the original signal is known to be sparse (i.e., ∥s∥0 ≤ K0with  K0 < 2M) 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  ℓpregularization (with p small to favor sparsity) on the solution and to formulate the reconstruction problem as

image

with  ∥x∥ℓp △=��Nn=1 |xn|p�1/p. 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  p ∈(1, ∞). The corresponding Banach space is  X ′ =(RN, ∥ · ∥ℓp) whose predual is  X = (RN, ∥ · ∥ℓq) with 1p+  1q = 1. Moreover,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 ν0 = HT a ∈ Xand by using the known form of the corresponding Banach q-to-p duality map JX : X → X ′, we then readily deduce that the solution can be represented as

image

for a suitable value of the (dual) parameter vector  a ∈ RM. 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  y ∈ RMand the dual variable  a ∈ RMin (25). In particular, for p = 2, we have that  s = HT a = �Mm=1 hmam, which confirms the well-known result that  s ∈span{hm}. The latter also explains why classical quadratic/Tikhonov regularization performs poorly when M is much smaller than N.

The limit case2of 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  f0,extof the solution set S of Problem (8) can be expressed as

image

for some 1  ≤ K0 ≤ Mwhere the  ekare some extremal points of the unit “regularization” ball  BX ′ = {f ∈ X ′:  ∥f∥X ′ ≤ 1}and (ak) ∈ RK0is 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  f0 ∈ Sof 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  ℓp(Z) or  Lp(Rd) with  p ∈(1, ∞) for which all unit vectors (i.e., e ∈ X ′with  ∥e∥X ′ = 1) are extremal points of the unitball. Indeed, since the corresponding solution is unique (by Theorem 2), we trivially have that  f0 = ∥f0∥X ′e1with  K0 = 1 and e1 = f0/∥f0∥X ′.

By contrast, the characterization in Theorem 3 is highly relevant for the non-strictly convex space  X ′ = ℓ1(Z) whose extreme vectors are intrinsically sparse; i.e,  ek = (±δ[n−nk])n∈Zfor some fixed offset  nk ∈ Z. Here,  δ[·] denotes the Kronecker impulse which is such that  δ[0] = 1 and δ[n] = 0 for n ̸= 0.Hence, the outcome is that the use of the  ℓ1penalty (e.g., (24) with p = 1) has a tendency to induce sparse solutions with  ∥f∥0 = K0 ≤ M, 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  Ω ⊂ Rdequipped with the supremum (or  L∞) norm is a classical Banach space denoted by

image

Its continuous dual

image

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  M(Ω) are point measures (a.k.a. Dirac impulses) of the form  ek = ±δ(· − xk) for some  xk ∈ Ω, with the property that

image

for any  ϕ ∈ C(Ω). For a series of (independent) analysis functions  ν1, . . . ,νM ∈ C(Ω) (e.g., Fourier exponentials), we can invoke Theorems 2 and 3 with X ′ = M(Ω) to deduce that the extreme points of the problem

image

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

image

with  K0 ≤ M, (ak) ∈ RK0, and  x1, . . . , xK0 ∈ Ω. 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  xkand  νmunder which (30) can provide a perfect recovery of spike trains of the form given by (31) with a small  K0[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  Rdis denoted by S(Rd). Its continuous dual is  S′(Rd): the space of tempered distributions. In this section, L :  S′(Rd) c.−−→ S′(Rd) is an invertible operator with continuous inverse L−1:  S′(Rd) c.−−→ S′(Rd). We also assume that the generalized impulse response of L−1is a bivariate function of slow growth  h : Rd × Rd → R. In other words, the inverse operator L−1has the explicit integral representation

image

for any  ϕ ∈ S(Rd). In conformity with the nomenclature of [53], the native Banach space for�L, M(Rd)�is

image

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

image

admits a solution, albeit not necessarily a unique one since the underlying search space  ML(Rd)—or, equivalently, the parent space  M(Rd)—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  M(Rd) take the form ek = ±δ(· − τ k) with  τ k ∈ Rd, which is consistent with the result in Section 4.1 for  M(Ω). Since the map L−1:  M(Rd) c.−−→ ML(Rd) is isometric, this allows us to identify the extreme points of the unit ball in  ML(Rd) as

image

where  h : Rd × Rd → Ris 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

image

with parameters  K0 ≤ M, τ 1, . . . , τ K0 ∈ Rd, and (ak) ∈ RK0. Moreover, since L{h(·, τ k)} = δ(· − τ k) and  ∥δ(· − τ k)∥M = ∥ek∥M = 1, the optimal regu-larization cost is  ∥Lf0∥M = �K0k=1 |ak| = ∥a∥ℓ1, which makes an interesting connection with  ℓ1-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  τ kare adaptive, meaning that their location as well as their cardinality  K0is data-dependent. In effect, it is the underlying  ℓ1-norm penalty that helps reducing the number  K0of 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 :  S′(Rd) c.−−→ S′(Rd) is linear shift-invariant (LSI) with frequency response  F�Lδ�(ω) = �L(ω), then  h(x, τ) = hLSI(x − τ) with

image

where the operator  F−1:  S′(Rd) → S′(Rd) 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  hLSI : Rd → Rand then infer the frequency response of the corresponding regularization operator

image

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

image

with  α ∈(0, 2). The limit case with  α = 2 (Gaussian) is excluded because thecorresponding frequency response in (38) (inverse of a Gaussian) fails to be slowly increasing.

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  ∥·∥ℓ1and its continuous-domain counterpart—the total variation  ∥ · ∥Mand 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].

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.

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  L1extremal 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  ℓ1 reg-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