Splines are universal solutions of linear inverse problems with generalized TV regularization

DOI10.1137/16M1061199zbMATH Open1382.41011arXiv1603.01427MaRDI QIDQ4592947FDOQ4592947

J. Ward, M. Unser, Julien Fageot

Publication date: 9 November 2017

Published in: SIAM Review (Search for Journal in Brave)

Abstract: Splines come in a variety of flavors that can be characterized in terms of some differential operator L. The simplest piecewise-constant model corresponds to the derivative operator. Likewise, one can extend the traditional notion of total variation by considering more general operators than the derivative. This leads us to the definition of the generalized Beppo-Levi space M, which is further identified as the direct sum of two Banach spaces. We then prove that the minimization of the generalized total variation (gTV) over M, subject to some arbitrary (convex) consistency constraints on the linear measurements of the signal, admits nonuniform L-spline solutions with fewer knots than the number of measurements. This shows that non-uniform splines are universal solutions of continuous-domain linear inverse problems with LASSO, L1, or TV-like regularization constraints. Remarkably, the spline-type is fully determined by the choice of L and does not depend on the actual nature of the measurements.

Full work available at URL: https://arxiv.org/abs/1603.01427

Recommendations

• Splines in higher order TV regularization
• Exact solutions of infinite dimensional total-variation regularized problems
• Structural Properties of Solutions to Total Variation Regularization Problems
• Exact recovery of non-uniform splines from the projection onto spaces of algebraic polynomials
• TV-based spline reconstruction with Fourier measurements: uniqueness and convergence of grid-based methods

zbMATH Keywords

total variationsplinessparsityinverse problemscompressed sensing

Mathematics Subject Classification ID

Spline approximation (41A15) Sampling theory in information and communication theory (94A20) Linear operators and ill-posed problems, regularization (47A52)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Nonlinear total variation based noise removal algorithms
• Title not available (Why is that?)
• Locally adaptive regression splines
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• A practical guide to splines
• Title not available (Why is that?)
• Stable signal recovery from incomplete and inaccurate measurements
• The Split Bregman Method for L1-Regularized Problems
• Sparse and redundant representations. From theory to applications in signal and image processing.
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• Fast Gradient-Based Algorithms for Constrained Total Variation Image Denoising and Deblurring Problems
• Scattered Data Approximation
• Compressed sensing
• An algorithm for total variation minimization and applications
• A mathematical introduction to compressive sensing
• Title not available (Why is that?)
• An EM algorithm for wavelet-based image restoration
• Title not available (Why is that?)
• Title not available (Why is that?)
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• Fractional Splines and Wavelets
• Sparsity and incoherence in compressive sampling
• Title not available (Why is that?)
• Les espaces du type de Beppo Levi
• Cardinal exponential splines: part I - theory and filtering algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• The restricted isometry property and its implications for compressed sensing
• Compressed Sensing and Redundant Dictionaries
• Super-resolution from noisy data
• Sampling-50 years after Shannon
• An Introduction to Sparse Stochastic Processes
• Super-resolution of point sources via convex programming
• Sampling Theory
• Sampling signals with finite rate of innovation
• Exact support recovery for sparse spikes deconvolution
• Harmonic analysis of the space BV.
• Support recovery for sparse super-resolution of positive measures
• Polyharmonic cardinal splines
• Generalized sampling and infinite-dimensional compressed sensing
• Shape-preserving, multiscale fitting of univariate data by cubic \(L_1\) smoothing splines
• L-splines
• Self-Similarity: Part I—Splines and Operators
• BREAKING THE COHERENCE BARRIER: A NEW THEORY FOR COMPRESSED SENSING
• Approximation properties of Sobolev splines and the construction of compactly supported equivalents
• Inverse problems in spaces of measures
• Splines in higher order TV regularization
• Spline solutions to L\(^1\) extremal problems in one and several variables
• Taut-string algorithm and regularization programs with \(G\)-norm data fit
• Canonical decomposition of steerable functions
• Riesz potentials, higher Riesz transforms and Beppo Levi spaces
• Representer Theorems for Sparsity-Promoting <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math> </inline-formula> Regularization

Cited In (30)

• Sparsest piecewise-linear regression of one-dimensional data
• On Representer Theorems and Convex Regularization
• A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization
• TV-based spline reconstruction with Fourier measurements: uniqueness and convergence of grid-based methods
• Understanding neural networks with reproducing kernel Banach spaces
• What Kinds of Functions Do Deep Neural Networks Learn? Insights from Variational Spline Theory
• Mini-workshop: Deep learning and inverse problems. Abstracts from the mini-workshop held March 4--10, 2018
• Deep learning architectures for nonlinear operator functions and nonlinear inverse problems
• On the extremal points of the ball of the Benamou–Brenier energy
• On the uniqueness of solutions for the basis pursuit in the continuum
• A New Approach for the Inversion of the Attenuated Radon Transform
• Explicit representations for Banach subspaces of Lizorkin distributions
• Sparsity of solutions for variational inverse problems with finite-dimensional data
• Energy on spheres and discreteness of minimizing measures
• Title not available (Why is that?)
• Splines in higher order TV regularization
• Functional penalised basis pursuit on spheres
• An Epigraphical Approach to the Representer Theorem
• Multikernel Regression with Sparsity Constraint
• Convex optimization in sums of Banach spaces
• TV-based reconstruction of periodic functions
• A superposition principle for the inhomogeneous continuity equation with Hellinger–Kantorovich-regular coefficients
• Sampling the Fourier Transform Along Radial Lines
• On the linear convergence rates of exchange and continuous methods for total variation minimization
• Learning quantities of interest from dynamical systems for observation-consistent inversion
• Title not available (Why is that?)
• From kernel methods to neural networks: a unifying variational formulation
• Dynamical programming for off-the-grid dynamic inverse problems
• Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain
• A unifying representer theorem for inverse problems and machine learning

This page was built for publication: Splines are universal solutions of linear inverse problems with generalized TV regularization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4592947)