Linear convergence of a one-cut conditional gradient method for total variation regularization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915640969789440 |
|---|---|
| author | Cristinelli, Giacomo Iglesias, José A. Walter, Daniel |
| author_facet | Cristinelli, Giacomo Iglesias, José A. Walter, Daniel |
| contents | We introduce a fully-corrective generalized conditional gradient method for convex minimization problems involving total variation regularization on multidimensional domains. It relies on alternatively updating an active set of subsets of the spatial domain and an iterate given by a conic combination of the associated characteristic functions. Different to previous approaches in the same spirit, the computation of a new candidate set only requires the solution of one prescribed mean curvature problem, instead of the resolution of a fractional minimization task analogous to finding a generalized Cheeger set. After discretization, the former can be realized by a single run of a graph cut algorithm, leading to a significant speedup in practice. We prove the global sublinear convergence of the resulting method, under mild assumptions, and its asymptotic linear convergence in a more restrictive two-dimensional setting which uses results of stability of surfaces of prescribed mean curvature under perturbations of the curvature. Finally, we numerically demonstrate this convergence behavior in some model PDE-constrained minimization problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_16899 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Linear convergence of a one-cut conditional gradient method for total variation regularization Cristinelli, Giacomo Iglesias, José A. Walter, Daniel Optimization and Control Numerical Analysis 49M41, 65J20, 52A40, 49J45, 49Q20 We introduce a fully-corrective generalized conditional gradient method for convex minimization problems involving total variation regularization on multidimensional domains. It relies on alternatively updating an active set of subsets of the spatial domain and an iterate given by a conic combination of the associated characteristic functions. Different to previous approaches in the same spirit, the computation of a new candidate set only requires the solution of one prescribed mean curvature problem, instead of the resolution of a fractional minimization task analogous to finding a generalized Cheeger set. After discretization, the former can be realized by a single run of a graph cut algorithm, leading to a significant speedup in practice. We prove the global sublinear convergence of the resulting method, under mild assumptions, and its asymptotic linear convergence in a more restrictive two-dimensional setting which uses results of stability of surfaces of prescribed mean curvature under perturbations of the curvature. Finally, we numerically demonstrate this convergence behavior in some model PDE-constrained minimization problems. |
| title | Linear convergence of a one-cut conditional gradient method for total variation regularization |
| topic | Optimization and Control Numerical Analysis 49M41, 65J20, 52A40, 49J45, 49Q20 |
| url | https://arxiv.org/abs/2504.16899 |