A fast primal-dual-active-jump method for minimization in BV((0,T) ℝ^d)

Abstract

We analyse a solution method for minimization problems over a space of ${\mathbb{R}}^d$-valued functions of bounded variation on an interval I. The presented method relies on piecewise constant iterates. In each iteration, the algorithm alternates between proposing a new point at which the iterate is allowed to be discontinuous and optimizing the magnitude of its jumps as well as the offset. A sublinear $\mathcal{O}(1/k)$ convergence rate for the objective function values is obtained in general settings. Under additional structural assumptions on the dual variable, this can be improved to a locally linear rate of convergence $\mathcal{O}({\zeta }^k)$ for some $\zeta <1$. Moreover, in this case, the same rate can be expected for the iterates in $L^1(I;{\mathbb{R}}^d)$.

Keywords:

• Bounded variation functions
• generalized conditional gradient
• sparsity

AMS:

• 26A45
• 65J22
• 65K05
• 90C25
• 49M05

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work was supported by Horizon 2020 Framework Programme[ERC advanced grant 668998 (OCLOC)].