TV-based spline reconstruction with Fourier measurements: uniqueness and convergence of grid-based methods

DOI10.1016/J.CAM.2022.114937zbMATH Open1504.94032arXiv2202.05059OpenAlexW4308930804MaRDI QIDQ2104103FDOQ2104103

Authors: Thomas Debarre, Quentin Denoyelle, Julien Fageot 

Publication date: 9 December 2022

Published in: Journal of Computational and Applied Mathematics (Search for Journal in Brave)

Abstract: We study the problem of recovering piecewise-polynomial periodic functions from their low-frequency information. This means that we only have access to possibly corrupted versions of the Fourier samples of the ground truth up to a maximum cutoff frequency $K_c$. The reconstruction task is specified as an optimization problem with total-variation (TV) regularization (in the sense of measures) involving the $M$-th order derivative regularization operator $mathrmL=mathrm{D}^M$. The order $Mgeq1$ determines the degree of the reconstructed piecewise polynomial spline, whereas the TV regularization norm, which is known to promote sparsity, guarantees a small number of pieces. We show that the solution of our optimization problem is always unique, which, to the best of our knowledge, is a first for TV-based problems. Moreover, we show that this solution is a periodic spline matched to the regularization operator $mathrmL$ whose number of knots is upper-bounded by $2K_c$. We then consider the grid-based discretization of our optimization problem in the space of uniform $mathrmL$-splines. On the theoretical side, we show that any sequence of solutions of the discretized problem converges uniformly to the unique solution of the gridless problem as the grid size vanishes. Finally, on the algorithmic side, we propose a B-spline-based algorithm to solve the grid-based problem, and we demonstrate its numerical feasibility experimentally. On both of these aspects, we leverage the uniqueness of the solution of the original problem.

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

Recommendations

• Splines are universal solutions of linear inverse problems with generalized TV regularization
• Analysis and an interior-point approach for TV image reconstruction problems on smooth surfaces
• Reconstruction of splines from nonuniform samples
• Splines in higher order TV regularization
• Exact iterative reconstruction algorithm for multivariate irregularly sampled functions in spline-like spaces: The 𝐿^{𝑝}-theory
• A New Reconstruction Algorithm in Spline Signal Spaces
• B-Spline-Based Exact Discretization of Continuous-Domain Inverse Problems With Generalized TV Regularization
• Existence and uniqueness of spline reconstruction from local weighted average samples
• Constructive reconstruction from irregular sampling in multi-window spline-type spaces
• On stable reconstructions from nonuniform Fourier measurements

zbMATH Keywords

optimizationsplinesinverse problemsFourier analysisgeneralized total-variation regularizationgrid-based algorithms

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Spline approximation (41A15) Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42A38) Classical almost periodic functions, mean periodic functions (42A75)

Cites Work

• Pocket guide to solve inverse problems with GlobalBioIm
• Nonlinear total variation based noise removal algorithms
• TV-based reconstruction of periodic functions
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• A practical guide to splines
• Convex Analysis
• Title not available (Why is that?)
• Title not available (Why is that?)
• Super-resolution from noisy data
• Towards a Mathematical Theory of Super‐resolution
• Spike detection from inaccurate samplings
• Exact reconstruction using Beurling minimal extrapolation
• Exact support recovery for sparse spikes deconvolution
• A theory of super-resolution from short-time Fourier transform measurements
• Title not available (Why is that?)
• Inverse problems in spaces of measures
• On Representer Theorems and Convex Regularization
• B-Spline-Based Exact Discretization of Continuous-Domain Inverse Problems With Generalized TV Regularization
• On the uniqueness of solutions for the basis pursuit in the continuum
• The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
• The shaping of the Riesz representation theorem: A chapter in the history of analysis
• Sparsity of solutions for variational inverse problems with finite-dimensional data
• The sliding Frank–Wolfe algorithm and its application to super-resolution microscopy
• Sparse regularization on thin grids I: the Lasso
• Exact solutions of infinite dimensional total-variation regularized problems
• Spline solutions to L\(^1\) extremal problems in one and several variables
• Sparsest piecewise-linear regression of one-dimensional data
• Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization
• Hybrid-Spline Dictionaries for Continuous-Domain Inverse Problems
• Continuous-Domain Solutions of Linear Inverse Problems With Tikhonov Versus Generalized TV Regularization
• Periodic Splines and Gaussian Processes for the Resolution of Linear Inverse Problems
• On the linear convergence rates of exchange and continuous methods for total variation minimization
• Sparse spikes super-resolution on thin grids II: the continuous basis pursuit
• Multikernel Regression with Sparsity Constraint
• A fast homotopy algorithm for gridless sparse recovery

Cited In (1)

• Splines in higher order TV regularization

This page was built for publication: TV-based spline reconstruction with Fourier measurements: uniqueness and convergence of grid-based methods

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