Source-linked AI summary
On Representer Theorems and Convex Regularization
Claire Boyer, Antonin Chambolle, Yohann De Castro, Vincent Duval, Frédéric De Gournay, Pierre Weiss
TL;DR
Sparse inverse-problem solutions are often sought as sums of a few atoms, but the theoretical legitimacy of that structure is the question at issue. The paper develops convex-geometric representer theorems, showing solutions can be expressed using a small number of extreme points or rays of regularizer level sets, and applies the framework to total gradient variation. The theorem's bounds weaken when the optimal regularizer value is its minimum.
Problem
The paper asks whether seeking inverse-problem solutions that are linear sums of a few atoms is theoretically justified.
Source: §1 · p. 2Method
It uses convex-set geometry to develop representer theorems for convex regularized inverse problems, identifying atoms with extreme points or points in extreme rays of regularizer level sets.
Source: §1 · p. 5, §5 · p. 24Results
Solutions can be described as convex combinations of a small number of extreme points and extreme rays of the regularizer level set.
Source: §5 · p. 24Takeaways & Limitations
The framework characterizes total-gradient-variation minimizers as sums of indicators of simple sets and offers an explanation for staircasing with few measurements.
Source: §1 · p. 5When the optimal regularizer value equals its minimum, the theorem's conclusions are slightly weaker and the convex combination may require one additional point.
Source: §3.1 · p. 8
Abstract
from arXiv · showhide
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 quasi-convex regularizers is also discussed. As a side result, we characterize the minimizers of the total gradient variation, which was still an unresolved problem.
1 Introduction
The introduction asks whether sparse solutions in inverse problems are theoretically justified and generalizes representer theorems from Tikhonov regularization to arbitrary convex regularizers. It connects sparse representations to convex-set geometry and previews applications including total gradient variation.
Representer theorems and Tikhonov regularization
- The introduction frames the question as whether sparse inverse-problem solutions, formed from a few atoms, have theoretical justification.It describes the objective as investigating the theoretical legitimacy of seeking such solutions.Source: §1 · p. 2
Representer theorems and convex regularization
- The paper generalizes representer theorems to arbitrary convex regularizers, extending beyond Tikhonov regularization and covering problems over spaces of measures.The introduction notes that descriptions of measure-recovery solutions have a long history, while the representer-theorem framing is newer in convex regularization.Source: §1 · p. 3
Representer theorems for convex sets
- The paper relates sparse-solution practice to convex geometry: Minkowski–Carathéodory bounds representations by m + 1 extreme points, while Klee also allows points in extreme rays.Dubins' theorem connects this geometry to intersections with affine spaces of codimension m.Source: §1 · pp. 4–5
- A refined variational analysis improves on the Dubins bound, ensuring at most m extreme points rather than the extra point that theorem yields.The introduction illustrates the excess with one linear measurement, for which Dubins' theorem would give two Dirac masses.Source: §1 · pp. 4–5
Contributions
- The proposed solutions use at most m atoms drawn from extreme points or extreme rays of regularizer level sets, plus a component in the regularizer's constancy space.The number-of-atoms bound depends on the level-set geometry and the relation between the measurement operator and the constancy space.Source: §1 · p. 5
- The results revisit linear and semidefinite programming, nonnegative constraints, nuclear norms, and analysis priors, and characterize total-gradient-variation minimizers as sums of indicators of simple sets.The total-gradient-variation representation provides a simple explanation for staircasing when only a few measurements are used.Source: §1 · p. 5
2 Notation and Preliminaries
The preliminaries establish terminology for convex sets, including rays, recession directions, extreme points, and faces. They also explain how quotienting out lineality produces a line-free set with a corresponding face decomposition.
Lines, rays, and linearly closed sets
- A set is linearly closed or bounded when its intersection with every line is closed or bounded, respectively; a ray is an open half-line.A line is an affine subspace of dimension one.Source: §2 · p. 6
Recession cone and lineality space
- The recession cone collects directions along which a set remains inside itself, while its lineality space is the largest vector space of invariant directions.For a linearly closed set, the recession cone consists of zero and vectors directing its rays.Source: §2 · p. 6
Extreme points, extremal rays, faces
- Extreme points cannot be removed while preserving convexity, and extreme rays are rays that contain any segment whose interior intersects them.Extreme points correspond to zero-dimensional faces; extreme rays are among the one-dimensional faces.Source: §2 · p. 6
Quotient by lines
- Quotienting out the lineality space yields a line-free set whose elementary faces correspond to the original set's faces plus the lineality space.The decomposition into a quotient-set element and a lineality-space element is unique.Source: §2 · p. 7
3 Abstract representer theorems
Theorem 1 bounds the facial dimension and atom count for solutions of convex-regularized inverse problems, with atoms drawn from extreme points or extreme rays of regularizer level sets. The results extend to level sets with lines and to several data-fitting settings, while existence of an extreme point may require additional topological conditions.
3.1 Main result
- A solution p belongs to a face of C⋆ of dimension at most m + j − 1 and admits the theorem’s corresponding convex-combination representation using extreme points or points in extreme rays.For extreme points of the solution set (j = 0), the stated representations use m extreme points, or m − 1 points of C⋆ that may include points in extreme rays.Source: §3.1 · pp. 7–8
- When t⋆ = infE R, the sharper theorem no longer applies: the face-dimension bound increases by one and the convex combination requires one additional point.In this case the measurement affine space need not be tangent to C⋆, so the general Dubins–Klee theorem is used.Source: §3.1 · p. 8
- The theorem extends to semi-strictly quasi-convex regularizers, a class that includes convex and strictly quasi-convex functions.The proof requires the semi-strictly quasi-convex property.Source: §3.1 · p. 9
3.2 The case of level sets containing lines
- For level sets containing lines, quotienting by K = lin(C⋆) gives representations of projected solutions with counts adjusted by d = dim Φ(K).The projected solution is a convex combination of m + j − d extreme points, or m + j − d − 1 points that may lie in extreme rays.Source: §3.2 · pp. 9–10
3.3.1 Convex data fitting term
- For convex data-fitting functions, the convex-regularization representation applies when infE R < R(p); if equality holds, the bounds require one more dimension.The result also holds when the solution set is convex, including when f is quasi-convex and R is convex.Source: §3.3.1 · pp. 11–12
3.3.2 Non-convex function
- For arbitrary, possibly non-convex data-fitting functions, a solution of the required form exists if the associated convex problem has a solution set with an extreme point.The selected point must also be a solution to the original problem.Source: §3.3.2 · p. 12
3.4 Ensuring the existence of extreme points
- A solution set may have no extreme points or finite-dimensional faces; in a locally convex Hausdorff space, closedness and local compactness ensure an extreme point, and compactness implies both.The section gives an example of a solution set without any extreme point.Source: §3.4 · pp. 12–13
4 Application to some popular regularizers
The paper analytically characterizes extreme points and extreme rays for numerous convex regularizers, using these descriptions to study solution properties across diverse applications.
4 Application to some popular regularizers
- Extreme points and extreme rays of numerous convex regularizers can be described analytically.The examples are illustrative rather than exhaustive.Source: §4 · p. 14
- These descriptions allow analysis of important properties of solutions to popular problems.Source: §4 · p. 14
- The examples span a diversity of applications, though the list is not exhaustive.Source: §4 · p. 14
4.1 Finite-dimensional examples
The finite-dimensional examples apply the structural results to nonnegative problems, linear programs, analysis priors, and matrix regularizers; the resulting sparse or low-rank structure depends on each regularizer’s extreme points and rays.
4.1.1 Nonnegativity constraints
- A nonempty nonnegative-constrained solution set contains an m-sparse solution, and its extreme points are m-sparse when the objective is convex and the set compact.For the nonnegative orthant regularizer, the relevant extreme rays are coordinate half-lines.Source: §4.1.1 · p. 15
4.1.2 Linear programming
- For a nonempty compact linear-program solution set, every extreme point is m-sparse, the standard basic-solution property.The extreme points are sums of at most m coordinate vectors.Source: §4.1.2 · pp. 15–16
4.1.3 ℓ1 analysis priors
- For surjective L, the ℓ1 analysis unit ball has extreme points ±L+e_i, and solutions use at most m − dim(Φker(L)) such atoms.Source: §4.1.3 · p. 17
- For nonsurjective L, extreme-point description is generally intractable; the proposed upper bound is pessimistic because the subspace may miss some extreme points.The bound nevertheless indicates possible combinatorial growth.Source: §4.1.3 · p. 17
4.1.4 Matrix examples
- For a positive-semidefinite matrix constraint with a solution, there is a solution of rank at most m.The cone’s extreme rays are rank-one positive-semidefinite matrices.Source: §4.1.4 · p. 18
- Because nuclear-norm unit-ball extreme points have rank one, nuclear-norm regularization can recover rank-m solutions.The extreme points are rank-one matrices uvT with unit-norm factors.Source: §4.1.4 · p. 19
- The Birkhoff polytope’s extreme points are permutation matrices.The polytope consists of doubly stochastic matrices.Source: §4.1.4 · p. 19
4.2 Examples in infinite dimension
The infinite-dimensional examples extend sparse-representation results to measures and analysis priors, and identify simple-set indicators as the atoms of total-gradient-variation solutions.
4.2.1 Problems formulated in Hilbert or Banach sequence spaces
- Hilbert spaces, countable sequences, and Banach sequence spaces ℓp for 1 ≤ p ≤ ∞ fit the framework, though their results are omitted for space limitations.Two cited works treat ℓ1 regularizers in this setting.Source: §4.2.1 · pp. 19–20
4.2.2 Linear programming and the moment problem
- For the nonnegative-measure linear-program and moment-problem setting, extreme points are m-sparse when the solution set is nonempty.The extreme rays of nonnegative measures are directed by Dirac masses.Source: §4.2.2 · p. 20
4.2.3 The total variation ball
- Total-variation regularization over measures yields m-sparse solutions under an existence assumption, with Dirac masses as atoms.For vector-valued measures, the stated extreme points are aδ_t with unit-norm a.Source: §4.2.3 · p. 21
4.2.4 Analysis priors in Banach spaces
- For the Banach-space analysis-prior result, the extreme points are ±L+δ_x under the stated surjectivity and topological-complement assumptions.The setting includes surjective Fredholm operators.Source: §4.2.4 · p. 22
- Existence of minimizers and extreme points for these analysis priors is harder to establish and requires careful topology choices.The paper notes that [48] provides a systematic construction of Banach spaces and pseudo-inverses.Source: §4.2.4 · p. 22
4.2.5 The total gradient variation
- The TV unit ball’s extreme points are indicators of indecomposable, saturated sets normalized by perimeter.The paper informally describes simple sets as simply connected sets with no holes.Source: §4.2.5 · p. 23
- With finitely many linear constraints, TV minimizers are sums of a small number of simple-set indicators, a result linked to the observed stair-casing tendency.The illustrated 200 × 200 image uses three disk-mean measurements and is represented by three such indicators.Source: §4.2.5 · p. 23, Figure 3 · p. 24
5 Conclusion
The conclusion presents a geometric representer theorem for convex-regularized inverse problems and emphasizes when its sparse structural description is informative.
5 Conclusion
- The solution set is described through convex combinations of a small number of extreme points and extreme rays of the regularizer level set.Source: §5 · p. 24
- The theorem is nontrivial when the level set has sufficiently flat boundary; for a strictly convex level set, the solution set is a single extreme point.The paper notes that commonly used sparsity-promoting regularizers often have the required flatness.Source: §5 · p. 24
- The authors suggest designing a regularizer by taking the convex hull of an anticipated family of solutions.They foresee that extreme-point and extreme-ray parameterizations may help design efficient numerical procedures.Source: §5 · p. 25
- In Banach spaces, the numerical procedures discussed require semi-infinite convex programs rather than simpler linear systems.Source: §5 · p. 25
6 Proofs of Section 3
The proof derives the face-dimension bound needed for Theorem 1’s finite extreme-point or extreme-ray representation, then handles lineality by passing to a quotient for Corollary 1.
6.1 Proof of Theorem 1
- After translating p to zero, T is the linear hull of F_C⋆(0), and T∩kerΦ is the linear hull of F_S⋆(0), whose dimension is j.Source: §6.1 · pp. 25–26
- A hypothetical m-dimensional complement Z makes Φ|Z bijective; the feasible convex perturbation contradicts minimality, yielding codim_T(T∩kerΦ)≤m−1.Source: §6.1 · pp. 25–26
- Theorem 1 represents p using at most m+j extreme points, or m+j−1 extreme points or points in an extreme ray, of the optimal level set’s face.Source: §6.1 · p. 26
6.2 Proof of Corollary 1
- For nontrivial K, the proof makes R invariant under translation along K and passes to quotient maps while preserving the optimum value.Source: §6.2 · pp. 26–27
- In the quotient, j-dimensional solution faces use at most m−d+j extreme points, or m−d+j−1 extreme points or points in an extreme ray of ˜C⋆.Source: §6.2 · p. 27
- For a singleton measurement set, the solution face is isomorphic to the quotient solution face times K∩kerΦ.Source: §6.2 · p. 27