2018

On Representer Theorems and Convex Regularization

Boyer, Claire, Chambolle, Antonin, De Castro, Yohann et al.

Understand

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.

Built on

Sur les intégrales de Fourier absolument convergentes et leur application à une transformation fonctionnelle
A. Beurling · 1938
Earlier work this paper cites.
The problem of moments
J. A. Shohat and J. D. Tamarkin · 1943
Earlier work this paper cites.
Remarks on problems in approximation theory
S. Zuhovickiĭ · 1948
Earlier work this paper cites.
Functions with generalized gradient and generalized surfaces
W. Fleming · 1957
Earlier work this paper cites.
Extremal structure of convex sets
V. L. Klee · 1957
Earlier work this paper cites.
Comonotone curves and polyhedra
T. S. Motzkin · 1957
Earlier work this paper cites.
On extreme points of convex sets
L. E. Dubins · 1962
Earlier work this paper cites.
The L-problem in an abstract normed linear space
M. Kreǐn · 1962
Earlier work this paper cites.
On approximation of real functions in the sense of P.L. Čebyšev
S. Zuhovickiĭ · 1962
Earlier work this paper cites.
On a theorem of Dubins
V. Klee · 1963
Earlier work this paper cites.
The operator theory of the pseudo-inverse i. bounded operators
F. J. Beutler · 1965
Earlier work this paper cites.
The maximum numbers of faces of a convex polytope
P. McMullen · 1970
Earlier work this paper cites.
Spline solutions to L1 extremal problems in one and several variables
S. D. Fisher and J. W. Jerome · 1975
Earlier work this paper cites.
The Markov moment problem and extremal problems: ideas and problems of P. L. Cebysev and A. A. Markov and their further development
M. G. Krein and A. A. Nudelman · 1977
Earlier work this paper cites.
Nonlinear total variation based noise removal algorithms
L. I. Rudin, S. Osher, and E. Fatemi · 1992
Earlier work this paper cites.
Convex Analysis and Minimization Algorithms I
J.-B. Hiriart-Urruty and C. Lemaréchal · 1993
Earlier work this paper cites.
Problems of distance geometry and convex properties of quadratic maps
A. I. Barvinok · 1995
Earlier work this paper cites.

Similar

Solving least squares problems
C. L. Lawson and R. J. Hanson · 1995
Cited alongside, same era.
Local strong homogeneity of a regularized estimator
M. Nikolova · 2000
Cited alongside, same era.
The geometry of semidefinite programming
G. Pataki · 2000
Cited alongside, same era.
Connected components of sets of finite perimeter and applications to image processing
L. Ambrosio, V. Caselles, S. Masnou, and J.-M. Morel · 2001
Cited alongside, same era.
A generalized representer theorem
B. Schölkopf, R. Herbrich, and A. J. Smola · 2001
Cited alongside, same era.
On duality theory of conic linear problems
A. Shapiro · 2001
Cited alongside, same era.
Learning with kernels :
B. Scholkopf and A. J. Smola · 2002
Cited alongside, same era.
Convex Optimization & Euclidean Distance Geometry
J. Dattorro · 2005
Cited alongside, same era.
Sparse nonnegative solution of underdetermined linear equations by linear programming
D. L. Donoho and J. Tanner · 2005
Cited alongside, same era.
Scattered data approximation
H. Wendland · 2005
Cited alongside, same era.
Infinite Dimensional Analysis: A Hitchhiker’s Guide
C. Aliprantis and K. Border · 2006
Cited alongside, same era.
Compressed sensing
D. L. Donoho · 2006
Cited alongside, same era.

Then

The convex geometry of linear inverse problems
V. Chandrasekaran, B. Recht, P. A. Parrilo, and A. S. Willsky · 2012
Later among the works it cites.
Intersecting singularities for multi-structured estimation
E. Richard, F. Bach, and J. P. Vert · 2013
Later among the works it cites.
Compressed sensing off the grid
G. Tang, B. N. Bhaskar, P. Shah, and B. Recht · 2013
Later among the works it cites.
Blind deconvolution using convex programming
A. Ahmed, B. Recht, and J. Romberg · 2014
Later among the works it cites.
Towards a mathematical theory of super-resolution
E. J. Candès and C. Fernandez-Granda · 2014
Later among the works it cites.
Tight convex relaxations for sparse matrix factorization
E. Richard, G. R. Obozinski, and J.-P. Vert · 2014
Later among the works it cites.
Extreme point inequalities and geometry of the rank sparsity ball
D. Drusvyatskiy, S. A. Vavasis, and H. Wolkowicz · 2015
Later among the works it cites.
Exact support recovery for sparse spikes deconvolution
V. Duval and G. Peyré · 2015
Later among the works it cites.
Convex relaxations for permutation problems
F. Fogel, R. Jenatton, F. Bach, and A. D’Aspremont · 2015
Later among the works it cites.
Generalized sampling and infinite-dimensional compressed sensing
B. Adcock and A. C. Hansen · 2016
Later among the works it cites.
Super-resolution of point sources via convex programming
C. Fernandez-Granda · 2016
Later among the works it cites.
Representer Theorems for Sparsity-Promoting ℓ 1 \ell_{1} Regularization
M. Unser, J. Fageot, and H. Gupta · 2016
Later among the works it cites.
Exact solutions to super resolution on semi-algebraic domains in higher dimensions
Y. De Castro, F. Gamboa, D. Henrion, and J.-B. Lasserre · 2017
Later among the works it cites.
Exact solutions of infinite dimensional total-variation regularized problems
Original
A. Flinth and P. Weiss · 2017
Later among the works it cites.
Splines are universal solutions of linear inverse problems with generalized tv regularization
M. Unser, J. Fageot, and J. P. Ward · 2017
Later among the works it cites.
Sparsity of solutions for variational inverse problems with finite-dimensional data
Original
K. Bredies and M. Carioni · 2018
Closest in time.
Continuous-domain solutions of linear inverse problems with tikhonov vs. generalized tv regularization
Original
H. Gupta, J. Fageot, and M. Unser · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…