Grid is Good. Adaptive Refinement Algorithms for Off-the-Grid Total Variation Minimization
Open Journal of Mathematical Optimization, Volume 6 (2025), article no. 3, 27 p.
We propose an adaptive refinement algorithm to solve total variation regularized measure optimization problems. The method iteratively constructs dyadic partitions of the unit cube based on (i) the resolution of discretized dual problems and (ii) the detection of cells containing points that violate the dual constraints. The detection is based on upper-bounds on the dual certificate, in the spirit of branch-and-bound methods. The interest of this approach is that it avoids the use of heuristic approaches to find the maximizers of dual certificates. We prove the convergence of this approach under mild hypotheses and a linear convergence rate under additional non-degeneracy assumptions. These results are confirmed by simple numerical experiments.
Received:
Revised:
Accepted:
Published online:
DOI:
10.5802/ojmo.39
Revised:
Accepted:
Published online:
Keywords:
Total variation, measure spaces, Frank–Wolfe
Author's affiliations:
Axel Flinth 1;
Frédéric de Gournay 2;
Pierre Weiss 3
License: 
CC-BY 4.0
CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
@article{OJMO_2025__6__A3_0,
author = {Axel Flinth and Fr\'ed\'eric de Gournay and Pierre Weiss},
title = {Grid is {Good.} {Adaptive} {Refinement} {Algorithms} for {Off-the-Grid} {Total} {Variation} {Minimization}},
journal = {Open Journal of Mathematical Optimization},
eid = {3},
pages = {1--27},
publisher = {Universit\'e de Montpellier},
volume = {6},
year = {2025},
doi = {10.5802/ojmo.39},
language = {en},
url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.39/}
}
TY - JOUR AU - Axel Flinth AU - Frédéric de Gournay AU - Pierre Weiss TI - Grid is Good. Adaptive Refinement Algorithms for Off-the-Grid Total Variation Minimization JO - Open Journal of Mathematical Optimization PY - 2025 SP - 1 EP - 27 VL - 6 PB - Université de Montpellier UR - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.39/ DO - 10.5802/ojmo.39 LA - en ID - OJMO_2025__6__A3_0 ER -
%0 Journal Article %A Axel Flinth %A Frédéric de Gournay %A Pierre Weiss %T Grid is Good. Adaptive Refinement Algorithms for Off-the-Grid Total Variation Minimization %J Open Journal of Mathematical Optimization %D 2025 %P 1-27 %V 6 %I Université de Montpellier %U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.39/ %R 10.5802/ojmo.39 %G en %F OJMO_2025__6__A3_0
Axel Flinth; Frédéric de Gournay; Pierre Weiss. Grid is Good. Adaptive Refinement Algorithms for Off-the-Grid Total Variation Minimization. Open Journal of Mathematical Optimization, Volume 6 (2025), article no. 3, 27 p. doi : 10.5802/ojmo.39. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.39/
[1] A rewriting system for convex optimization problems, J. Control Decis., Volume 5 (2018) no. 1, pp. 42-60 | DOI | MR
[2] Variational analysis in Sobolev and BV spaces: applications to PDEs and optimization, Society for Industrial and Applied Mathematics, 2014 | DOI | MR
[3] Partially finite convex programming, Part I: Quasi relative interiors and duality theory, Math. Program., Volume 57 (1992) no. 1, pp. 15-48 | DOI | MR
[4] On Representer Theorems and Convex Regularization, SIAM J. Optim., Volume 29 (2019) no. 2, pp. 1260-1281 | DOI | MR
[5] Inverse problems in spaces of measures, ESAIM, Control Optim. Calc. Var., Volume 19 (2013) no. 1, pp. 190-218 | DOI | Numdam | MR
[6] Towards a Mathematical Theory of Super-resolution, Commun. Pure Appl. Math., Volume 67 (2014) no. 6, pp. 906-956 | DOI | MR
[7] Sparse optimization on measures with over-parameterized gradient descent, Math. Program., Volume 194 (2022) no. 1, pp. 487-532 | DOI | MR
[8] On the global convergence of gradient descent for over-parameterized models using optimal transport, Adv. Neural Inf. Process. Syst., Volume 31 (2018), pp. 3036-3046
[9] A measure space approach to optimal source placement, Comput. Optim. Appl., Volume 53 (2012) no. 1, pp. 155-171 | DOI | MR
[10] Exact reconstruction using Beurling minimal extrapolation, J. Math. Anal. Appl., Volume 395 (2012) no. 1, pp. 336-354 | DOI | MR
[11] Exact solutions to Super Resolution on semi-algebraic domains in higher dimensions, IEEE Trans. Inf. Theory, Volume 63 (2017) no. 1, pp. 621-630 | DOI | MR
[12] TV-based spline reconstruction with Fourier measurements: Uniqueness and convergence of grid-based methods, J. Comput. Appl. Math., Volume 422 (2023), 114937, 13 pages | MR
[13] The sliding Frank–Wolfe algorithm and its application to super-resolution microscopy, Inverse Probl., Volume 36 (2019) no. 1, 014001, 42 pages | MR
[14] CVXPY: A Python-embedded modeling language for convex optimization, J. Mach. Learn. Res., Volume 17 (2016) no. 83, pp. 1-5 | MR | Zbl
[15] Exact support recovery for sparse spikes deconvolution, Found. Comput. Math., Volume 15 (2015) no. 5, pp. 1315-1355 | DOI | MR | Zbl
[16] Sparse inverse problems over measures: equivalence of the conditional gradient and exchange methods, SIAM J. Optim., Volume 29 (2019) no. 2, pp. 1329-1349 | DOI | MR | Zbl
[17] On the linear convergence rates of exchange and continuous methods for total variation minimization, Math. Program., Volume 190 (2021) no. 1, pp. 221-257 | DOI | MR | Zbl
[18] Exact solutions of infinite dimensional total-variation regularized problems, Information and Inference: A Journal of the IMA, Volume 8 (2018) no. 3, pp. 407-443 | DOI | MR | Zbl
[19] An algorithm for quadratic programming, Nav. Res. Logist. Q., Volume 3 (1956) no. 1-2, pp. 95-110 | DOI | MR
[20] A review of numerical methods for semi-infinite optimization, Semi-infinite programming and applications, Springer, 1983, pp. 158-178 | DOI
[21] Semi-infinite programming: theory, methods, and applications, SIAM Rev., Volume 35 (1993) no. 3, pp. 380-429 | DOI | MR
[22] Convex analysis and minimization algorithms II: Advanced Theory and Bundle Methods, Springer, 2013 | MR
[23] Optimal control of the undamped linear wave equation with measure valued controls, SIAM J. Control Optim., Volume 54 (2016) no. 3, pp. 1212-1244 | DOI | MR
[24] An introduction to polynomial and semi-algebraic optimization, Cambridge Texts in Applied Mathematics, 52, Cambridge University Press, 2015 | DOI | MR
[25] Branch-and-bound methods: A survey, Oper. Res., Volume 14 (1966) no. 4, pp. 699-719 | DOI | MR | Zbl
[26] Introductory lectures on convex optimization: A basic course, Applied Optimization, 87, Kluwer Academic Publishers, 2004, xviii+236 pages | DOI | MR
[27] Linear convergence of accelerated conditional gradient algorithms in spaces of measures, ESAIM, Control Optim. Calc. Var., Volume 27 (2021), 38, 37 pages | MR
[28] Support Localization and the Fisher Metric for off-the-grid Sparse Regularization, Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics (Proceedings of Machine Learning Research), Volume 89, PMLR (2019), pp. 1341-1350
[29] Numerical methods for semi-infinite programming: A survey, Semi-Infinite Programming, Springer, 1998, pp. 195-262 | DOI
[30] Sur la détermination des polynômes d’approximation de degré donnée, Comm. Soc. Math. Kharkov, Volume 10 (1934) no. 196, pp. 41-63
[31] Sparse recovery over continuous dictionaries-just discretize, 2013 Asilomar Conference on Signals, Systems and Computers, IEEE (2013), pp. 1043-1047 | DOI
[32] Compressed sensing off the grid, IEEE Trans. Inf. Theory, Volume 59 (2013) no. 11, pp. 7465-7490 | DOI | MR | Zbl
[33] The basins of attraction of the global minimizers of the non-convex sparse spike estimation problem, Inverse Probl., Volume 36 (2020) no. 4, 045003, 27 pages | MR
[34] Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, Volume 50 (2004) no. 10, pp. 2231-2242 | DOI | MR
[35] Splines Are Universal Solutions of Linear Inverse Problems with Generalized TV Regularization, SIAM Rev., Volume 59 (2017) no. 4, pp. 769-793 | DOI | MR
[36] An extension of Karmarkar’s projective algorithm for convex quadratic programming, Math. Program., Volume 44 (1989), pp. 157-179 | MR
[37] Scalable semidefinite programming, SIAM J. Math. Data Sci., Volume 3 (2021) no. 1, pp. 171-200 | DOI | MR
Cited by Sources:
