Sparsest piecewise-linear regression of one-dimensional data
From MaRDI portal
Spline approximation (41A15) Numerical mathematical programming methods (65K05) Convex programming (90C25) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)
Abstract: We study the problem of one-dimensional regression of data points with total-variation (TV) regularization (in the sense of measures) on the second derivative, which is known to promote piecewise-linear solutions with few knots. While there are efficient algorithms for determining such adaptive splines, the difficulty with TV regularization is that the solution is generally non-unique, an aspect that is often ignored in practice. In this paper, we present a systematic analysis that results in a complete description of the solution set with a clear distinction between the cases where the solution is unique and those, much more frequent, where it is not. For the latter scenario, we identify the sparsest solutions, i.e., those with the minimum number of knots, and we derive a formula to compute the minimum number of knots based solely on the data points. To achieve this, we first consider the problem of exact interpolation which leads to an easier theoretical analysis. Next, we relax the exact interpolation requirement to a regression setting, and we consider a penalized optimization problem with a strictly convex data-fidelity cost function. We show that the underlying penalized problem can be reformulated as a constrained problem, and thus that all our previous results still apply. Based on our theoretical analysis, we propose a simple and fast two-step algorithm, agnostic to uniqueness, to reach a sparsest solution of this penalized problem.
Recommendations
- Splines in higher order TV regularization
- Splines are universal solutions of linear inverse problems with generalized TV regularization
- Exact solutions of one-dimensional total generalized variation
- Structural Properties of Solutions to Total Variation Regularization Problems
- Exact solutions of infinite dimensional total-variation regularized problems
Cites work
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A mathematical introduction to compressive sensing
- A representer theorem for deep neural networks
- Approximation by superpositions of a sigmoidal function
- Atomic decomposition by basis pursuit
- Atomic Norm Denoising With Applications to Line Spectral Estimation
- B-Spline-Based Exact Discretization of Continuous-Domain Inverse Problems With Generalized TV Regularization
- Banach space representer theorems for neural networks and ridge splines
- Breaking the coherence barrier: a new theory for compressed sensing
- Compressed sensing
- Continuous-Domain Solutions of Linear Inverse Problems With Tikhonov Versus Generalized TV Regularization
- Convex Analysis
- Deep learning
- Deep Neural Networks With Trainable Activations and Controlled Lipschitz Constant
- Distributed optimization and statistical learning via the alternating direction method of multipliers
- Error bounds for approximations with deep ReLU networks
- Exact reconstruction using Beurling minimal extrapolation
- Exact solutions of infinite dimensional total-variation regularized problems
- Exact Solutions to Super Resolution on Semi-Algebraic Domains in Higher Dimensions
- Exact support recovery for sparse spikes deconvolution
- Functional penalised basis pursuit on spheres
- Generalized inverses. Theory and applications.
- Generalized sampling and infinite-dimensional compressed sensing
- scientific article; zbMATH DE number 1804115 (Why is no real title available?)
- scientific article; zbMATH DE number 3719745 (Why is no real title available?)
- scientific article; zbMATH DE number 45848 (Why is no real title available?)
- scientific article; zbMATH DE number 3504682 (Why is no real title available?)
- scientific article; zbMATH DE number 3561857 (Why is no real title available?)
- scientific article; zbMATH DE number 1179314 (Why is no real title available?)
- scientific article; zbMATH DE number 845714 (Why is no real title available?)
- scientific article; zbMATH DE number 6438182 (Why is no real title available?)
- scientific article; zbMATH DE number 3240665 (Why is no real title available?)
- Hybrid-Spline Dictionaries for Continuous-Domain Inverse Problems
- Inverse problems in spaces of measures
- Locally adaptive regression splines
- MultiDimensional Sparse Super-Resolution
- On 'best' interpolation
- On representer theorems and convex regularization
- On Smoothest Interpolants
- On the \(O(1/n)\) convergence rate of the Douglas-Rachford alternating direction method
- On the approximation of real functions in the sense of P. L. Čebyšev
- On the global and linear convergence of the generalized alternating direction method of multipliers
- On the linear convergence rates of exchange and continuous methods for total variation minimization
- Optimal approximation of piecewise smooth functions using deep ReLU neural networks
- Optimal approximation with sparsely connected deep neural networks
- Optimization with sparsity-inducing penalties
- Periodic Splines and Gaussian Processes for the Resolution of Linear Inverse Problems
- Pocket guide to solve inverse problems with GlobalBioim
- Quantile smoothing splines
- Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit
- Representer Theorems for Sparsity-Promoting <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math> </inline-formula> Regularization
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sampling and Super Resolution of Sparse Signals Beyond the Fourier Domain
- Sparse regularization on thin grids. I: The \textsc{Lasso}.
- Sparse spikes super-resolution on thin grids II: the continuous basis pursuit
- Spike detection from inaccurate samplings
- Spline solutions to L\(^1\) extremal problems in one and several variables
- Splines are universal solutions of linear inverse problems with generalized TV regularization
- Super-resolution from noisy data
- Super-resolution of point sources via convex programming
- Superresolution via Sparsity Constraints
- Superresolution without separation
- Support recovery for sparse super-resolution of positive measures
- The alternating descent conditional gradient method for sparse inverse problems
- The Lasso problem and uniqueness
- Towards a Mathematical Theory of Super‐resolution
- TV-based reconstruction of periodic functions
Cited in
(8)- Linear regression with sparsely permuted data
- TV-based spline reconstruction with Fourier measurements: uniqueness and convergence of grid-based methods
- Nonconvex regularization for sparse neural networks
- On the uniqueness of solutions for the basis pursuit in the continuum
- Linear inverse problems with Hessian-Schatten total variation
- Measuring Complexity of Learning Schemes Using Hessian-Schatten Total Variation
- Controlled learning of pointwise nonlinearities in neural-network-like architectures
- Splines in higher order TV regularization
This page was built for publication: Sparsest piecewise-linear regression of one-dimensional data
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2074905)
