# Extremal points of total generalized variation balls in 1D: characterization
and applications00footnotetext: 2020 Mathematics Subject Classification:
46A55, 90C49, 65J20, 52A40.00footnotetext: Keywords: total generalized
variation, regularization, extremal points, non-smooth optimization, sparsity.

José A. Iglesias, Daniel Walter Johann Radon Institute for Computational and
Applied Mathematics (RICAM), Austrian Academy of Sciences, Linz, Austria
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The total generalized variation (TGV) is a popular regularizer in inverse
problems and imaging combining discontinuous solutions and higher order
smoothing. In particular, empirical observations suggest that its order two
version strongly favors piecewise affine functions. In the present manuscript,
we formalize this statement for the one-dimensional TGV-functional by
characterizing the extremal points of its sublevel sets with respect to a
suitable quotient space topology. These results imply that 1D TGV-regularized
linear inverse problems with finite dimensional observations admit piecewise
affine minimizers. As further applications of this characterization we include
precise first-order necessary optimality conditions without requiring
convexity of the fidelity term, and a simple solution algorithm for TGV-
regularized minimization problems.

The total variation has been a widely considered prior for regularization of
inverse problems for several decades. A particularly popular application is
denoising of natural images since the seminal work [26]. However, it is
arguably even better suited to more involved situations where nearly piecewise
constant solutions are expected, like recovery of material inclusions in
various physical inverse problems (see for example [17, 13]). The reasons for
its success are varied. On the one hand, it typically produces solutions with
discontinuities, which can be thought to correspond to edges of objects in the
recovered images, or sharp changes of material parameters. On the other, its
formulation is purely local and in terms of derivatives, which in particular
enables a great amount of rigorous analysis of the resulting solutions. One of
the main drawbacks of the total variation, however, is the effect generally
known as staircasing. Inputs which are not piecewise constant but otherwise
very smooth tend to produce solutions with many discontinuities of small
amplitude, particularly in the presence of significant noise. A popular cure
for this problem is the use of regularizers involving higher order
derivatives, which for example can be made to not penalize linear functions.
Among such approaches, arguably the most successful is the total generalized
variation (TGV) first introduced in [7].

A clearly desirable feature of TGV is that it manages to introduce higher
order regularization and avoid staircasing while still allowing sharp
discontinuities in the solutions. Also of paramount importance is that, unlike
other models satisfying these first requirements, it admits a relatively
straightforward predual formulation. In turn, this allows the use of convex
nonsmooth optimization tools for its numerical solution, like the ubiquitous
[11] which was published around the same time. On the analysis side, topics
like existence of minimizers and relations to regularization theory are well
explored, see [9, 5, 6]. However, more detailed characterizations of the
behavior of solutions are significantly more scarce and with few exceptions
[28] they treat the one dimensional case and denoising only [8, 23, 25].

In this article, we consider the one-dimensional
$\operatorname{TGV}$-functional

$\displaystyle\operatorname{TGV}(u)=\inf_{w}\alpha\|Du-w\|_{M}+\beta\|Dw\|_{M}$

on an interval $(0,T)$ from a convex geometry point of view. Here,
$\alpha,\beta>0$ are suitable regularization parameters and $\|\cdot\|_{M}$ is
the Radon norm on $(0,T)$, i.e., the dual to the uniform norm. Denoting by
$\mathcal{L}$ the space of affine linear functions, we show that the set of
equivalence classes

$\displaystyle\mathcal{B}=\left\\{\,u\;|\;\operatorname{TGV}(u)\leq
1\,\right\\}+\mathcal{L}$

is compact with respect to the quotient space topology and can thus be written
as the closure of the convex hull of its extremal points
$\operatorname{Ext}\mathcal{B}$, by the Krein-Milman theorem. The main result
of the manuscript gives a precise characterization of
$\operatorname{Ext}\mathcal{B}$ as the equivalence classes corresponding to
two distinct sets of functions. More in detail, we have

$\displaystyle\operatorname{Ext}\mathcal{B}=\big{(}\left\\{\,u\;|\;Du=\pm\delta_{x}/\alpha,\leavevmode\nobreak\
x\in(0,T)\,\right\\}\cup\left\\{\,u\;|\;D^{2}u=\pm\delta_{x}/\beta,\leavevmode\nobreak\
\operatorname{dist}(x,\partial(0,T))>\beta/\alpha\,\right\\}\big{)}+\mathcal{L}.$

Most surprisingly, $\operatorname{Ext}\mathcal{B}$ contains the equivalence
classes of all piecewise constant functions with a single jump, i.e.,

$\displaystyle\left\\{\,u\;|\;Du=\pm\delta_{x}/\alpha,\leavevmode\nobreak\
x\in(0,T)\,\right\\}+\mathcal{L}$

while those corresponding to piecewise affine ones are only included if the
corresponding kink has a large enough distance to the boundary,

$\displaystyle\left\\{\,u\;|\;D^{2}u=\pm\delta_{x}/\beta,\leavevmode\nobreak\
\operatorname{dist}(x,\partial(0,T))>\beta/\alpha\,\right\\}+\mathcal{L}.$

This characterization has consequences in both the analysis and optimization
aspects related to the $\operatorname{TGV}$-regularizer. Within the first, we
derive precise necessary first-order optimality conditions and sufficient
conditions to ensure the existence of sparse, i.e., piecewise affine,
solutions to minimization problems incorporating the
$\operatorname{TGV}$-functional. In particular, based on convex representer
theorems, we show that linear inverse problems with finite-dimensional
observation and $\operatorname{TGV}$-regularization admit such minimizers.
These results are not constrained to denoising problems and confirm the
intuition that TGV-regularized solutions are encouraged to be piecewise
affine.

On the optimization side, this characterization enables us to formulate and
analyze a minimization algorithm that iteratively approximates solutions to
($\mathcal{P}$) by conic combinations of representatives of extremal points.
This means that every iterate is piecewise affine. In every iteration, the
method alternates between “adding” a new extremal point to the current iterate
and updating the nonnegative weights in the conic combination via solving a
finite dimensional problem with $\ell_{1}$-regularization. In particular, the
proposed method completely avoids, possibly complicated, evaluations of the
$\operatorname{TGV}$-functional. Moreover, its practical realization does not
require a discretization of the underlying interval, meaning that the
positions for the discontinuities of the function and its first derivative are
found directly and not constrained to be on a discrete grid. We give a
preliminary convergence analysis for the method showing subsequential
convergence of iterates and a convergence rate in terms of an adequate measure
of non-stationarity which dominates the suboptimality of the iterates in the
convex case.

As mentioned, at present we are only able to treat the one-dimensional case.
In the same spirit as previous works, this serves as a simplified setting in
which to infer characteristics of the solutions with the hope that these could
be generalized to higher dimensions. However, the one-dimensional case also
finds applications in its own right, like in [12] where it is applied for data
assimilation for the Burgers equation, whose solutions may contain shocks.
Moreover, in a number of works in signal processing [27, 22, 19, 18] priors
favoring discontinuous piecewise affine functions are considered for time-
domain signals. This motivates the numerical example in our last section. In
it, our solution algorithm is applied to the inverse problem of reconstructing
a piecewise affine signal from the values of its Fourier transform at a small
number of frequencies. This is an archetypical example of a regularization
problem with few measurements where a very sparse solution exists in light of
our theory, but with the added challenge that the measurements made and the
features to be reconstructed are of very different nature.

#### Organization of the paper.

In Section 1, after recalling the definition of the TGV-functional, we detail
how it can be considered in an adequate quotient space whose predual we
characterize. In Section 2 we prove the announced characterization of extremal
points. Section 3 deals with necessary first-order optimality conditions and
existence of sparse minimizers. In Section 4 we present the minimization
algorithm based on extremal points, which is then applied in Section 5 to the
test case of reconstruction from few Fourier measurements.

##  1 Functional space framework

Throughout the paper, we work with the total generalized variation of order
two with parameters $\alpha,\beta>0$, which is defined as

$\operatorname{TGV}_{\alpha,\beta}(u):=\sup\left\\{\int_{0}^{T}u\,v^{\prime\prime}\,\middle|\,v\in
C^{\infty}_{c}(0,T),\,\|v\|_{C}\leq\alpha,\,\|v^{\prime}\|_{C}\leq\beta\right\\},$
(1.1)

where $\|\cdot\|_{C}$ denotes the uniform norm on the space $C_{0}(0,T)$ of
continuous functions vanishing at the boundary. Whenever possible we omit the
dependence on the parameters in the notation of $\operatorname{TGV}$ for the
sake of brevity. Moreover, according to [9, Thm. 3.1], we have

$\operatorname{TGV}(u)=\inf_{w\in\mathrm{BV}(0,T)}\alpha\|Du-w\|_{M}+\beta\|Dw\|_{M},$
(1.2)

where by $\mathrm{BV}(0,T)$ we refer to the space of functions of bounded
variation on the interval $(0,T)$ and $\|\cdot\|_{M}$ denotes the canonical
norm on the space of Radon measures $M(0,T)=(C_{0}(0,T))^{\ast}$. Note that
$\mathrm{BV}(0,T)$ can be seen as the space of $L^{1}$ functions $u$ whose
distributional derivatives $Du$ are elements of $M(0,T)$. Abbreviating
$\operatorname{TV}(u)\coloneqq\|Du\|_{M}$, the corresponding norm is given by

$\displaystyle\|u\|_{\operatorname{BV}}=\|u\|_{L^{1}}+\operatorname{TV}(u)\quad\text{for
all}\leavevmode\nobreak\ u\in\mathrm{BV}(0,T).$

For further information on these spaces we refer the reader to Chapters 1 and
3 of [1].

Directly from the definition (1.1), we see that for all $c,d\in\mathbb{R}$ one
has $\operatorname{TGV}(u+cx+d)=\operatorname{TGV}(u)$. Accordingly, we denote
the subspaces of constant and affine linear functions by

$\displaystyle\mathcal{C}$
$\displaystyle\coloneqq\left\\{\,u\in\mathrm{BV}(0,T)\;\middle|\;u=c\cdot
1_{(0,T)},\leavevmode\nobreak\ c\in\mathbb{R}\,\right\\},\text{ and }$
$\displaystyle\mathcal{L}$
$\displaystyle\coloneqq\big{\\{}\,u\in\mathrm{BV}(0,T)\;\big{|}\;u(x)=cx+d,\,c,d\in\mathbb{R}\big{\\}}=\big{\\{}\,u\in\mathrm{BV}(0,T)\;\big{|}\;Du\in\mathcal{C}\,\big{\\}},$

so that $\operatorname{TGV}(u+\ell)=\operatorname{TGV}(u)$ for all
$u\in\mathrm{BV}(0,T)$ and $\ell\in\mathcal{L}$. As we will see it is
beneficial to consider $\operatorname{TGV}$ on the corresponding quotient
space $\mathrm{BV}(0,T)/\mathcal{L}$:

######  Proposition 1.

The total generalized variation $\operatorname{TGV}$ is an equivalent norm on
the quotient space $\mathrm{BV}(0,T)/\mathcal{L}$, which admits the dual
representation

$\begin{gathered}\mathrm{BV}(0,T)/\mathcal{L}=\big{(}C_{0,a}(0,T)\big{)}^{\ast},\text{
with }C_{0,a}(0,T):=\left\\{p\in
C_{0}(0,T)\;\middle|\;\int_{0}^{T}p\,\mathrm{d}x=0\right\\}\text{ and }\\\
\langle
u+\mathcal{L},p\rangle_{\big{(}BV(0,T)/\mathcal{L}\,,\,C_{0,a}(0,T)\big{)}}=\int_{(0,T)}p\,\mathrm{d}Du.\end{gathered}$
(1.3)

In particular, the unit ball

$\mathcal{B}:=\big{\\{}u+\mathcal{L}\in\mathrm{BV}(0,T)/\mathcal{L}\;\big{|}\;\operatorname{TGV}(u)\leq
1\big{\\}}$ (1.4)

is sequentially compact with respect to the corresponding weak-* topology in
$\mathrm{BV}(0,T)/\mathcal{L}$.

###### Proof.

To begin with, we notice that both $\mathcal{C}$ and $\mathcal{L}$ are closed
subspaces of $\mathrm{BV}(0,T)$ with respect to the weak-* topology. Moreover,
we may write

$\mathrm{BV}(0,T)/\mathcal{L}=\big{(}\mathrm{BV}(0,T)/\mathcal{C}\big{)}/(\mathcal{L}/\mathcal{C}).$

In the one dimensional situation we consider, the map

$\displaystyle\Lambda:BV(0,T)/\mathcal{C}$ $\displaystyle\to M(0,T)$
$\displaystyle u+\mathcal{C}$ $\displaystyle\mapsto Du$

is clearly continuous by the definition of the corresponding norms, and has as
an inverse the map assigning to each $\mu\in M(0,T)$ the equivalence class
$\big{[}x\mapsto\mu\big{(}(0,x)\big{)}\big{]}+\mathcal{C}$. Using the bounded
inverse theorem, this implies that it is an isomorphism of Banach spaces.
Furthermore, the image
$\Lambda(\mathcal{L}/\mathcal{C})=\mathbb{R}\mathscr{L}$ is the set of scalar
multiples of the Lebesgue measure restricted to $(0,T)$, which we denote by
$\mathscr{L}$. By results for general Banach spaces (an application of Hahn-
Banach, essentially) we have [16, Prop. 2.7] that if
$C_{0,a}(0,T)^{\perp}=\mathbb{R}\mathscr{L}$ then
$M(0,T)/(\mathbb{R}\mathscr{L})=\big{(}C_{0,a}(0,T)\big{)}^{\ast}$. To see the
equality for the annihilator, consider

$\mu\in M(0,T)\text{ satisfying }\int_{(0,T)}p\,\mathrm{d}\mu=0\text{ for all
}p\in C_{0,a}(0,T),$

and fix an arbitrary function $q_{0}\in C_{0}(0,T)$ with
$\int_{0}^{T}q_{0}\,\mathrm{d}x=1$. Now, for each $q\in C_{0}(0,T)$, just
consider the function

$C_{0,a}(0,T)\ni p=q-\left(\int_{0}^{T}q\,\mathrm{d}x\right)\,q_{0},\text{ so
that
}\int_{(0,T)}q\,\mathrm{d}\mu=\left(\int_{0}^{T}q\,\mathrm{d}x\right)\left(\int_{(0,T)}q_{0}\,\mathrm{d}\mu\right).$

Since the number $\int_{(0,T)}q_{0}\,\mathrm{d}\mu$ is independent of $q\in
C_{0}(0,T)$ and by the Riesz representation theorem
$M(0,T)=\big{(}C_{0}(0,T)\big{)}^{\ast}$, this means that

$\mu=\left(\int_{(0,T)}q_{0}\,\mathrm{d}\mu\right)\mathscr{L}.$

To see that $\operatorname{TGV}$ is an equivalent norm on
$\mathrm{BV}(0,T)/\mathcal{L}$, fix $u\in\mathrm{BV}(0,T)$ as well as $w_{u}$
with

$\displaystyle\inf_{w\in\mathrm{BV}}\alpha\|Du-w\|_{M}+\beta\|Dw\|_{M}$
$\displaystyle=\alpha\|Du-w_{u}\|_{M}+\beta\|Dw_{u}\|_{M}.$

Now, we can first use the Poincaré-Wirtinger inequality [1, Thm. 3.44, Rem.
3.45] in $\mathrm{BV}(0,T)$ twice to obtain that

$\displaystyle\operatorname{TGV}(u)$
$\displaystyle=\inf_{w\in\mathrm{BV}}\alpha\|Du-w\|_{M}+\beta\|Dw\|_{M}$ (1.5)
$\displaystyle=\alpha\|Du-w_{u}\|_{M}+\beta\|Dw_{u}\|_{M}$
$\displaystyle\geq\alpha\|Du-
w_{u}\|_{M}+CT\beta\big{\|}w_{u}-T^{-1}\textstyle{\int_{0}^{T}}w_{u}\big{\|}_{L^{1}}$
$\displaystyle\geq\min(\alpha,CT\beta)\big{(}\|Du-
w_{u}\|_{M}+\big{\|}w_{u}-T^{-1}\textstyle{\int_{0}^{T}}w_{u}\big{\|}_{L^{1}}\big{)}$
$\displaystyle\geq\min(\alpha,CT\beta)\inf_{c\in\mathbb{R}}\big{(}\|Du-
w_{u}\|_{M}+\big{\|}w_{u}-c\big{\|}_{L^{1}}\big{)}$
$\displaystyle\geq\min(\alpha,CT\beta)\inf_{c\in\mathbb{R}}\|D(u-cx)\|_{M}$
$\displaystyle\geq
CT\min(\alpha,CT\beta)\inf_{c\in\mathbb{R}}\big{\|}u-cx-T^{-1}\textstyle{\int_{0}^{T}}(u-cx)\big{\|}_{L^{1}}$
$\displaystyle\geq
CT\min(\alpha,CT\beta)\inf_{c,d\in\mathbb{R}}\big{\|}u-cx-d\big{\|}_{L^{1}},$

with which we can estimate

$\displaystyle\|u+\mathcal{L}\|_{\mathrm{BV}/\mathcal{L}}$
$\displaystyle=\inf_{\ell\in\mathcal{L}}\|u-\ell\|_{\mathrm{BV}}=\inf_{c,d\in\mathbb{R}}\|u-cx-d\|_{\mathrm{BV}}$
$\displaystyle=\inf_{c,d\in\mathbb{R}}\|u-cx-d\|_{L^{1}}+\|D(u-cx)\|_{M}\leq\frac{2}{CT\min(\alpha,CT\beta)}\operatorname{TGV}(u).$

On the other hand, testing the definition of $\operatorname{TGV}$ with
constant $w\equiv c$ tells us that

$\operatorname{TGV}(u)\leq\inf_{c\in\mathbb{R}}\alpha\|Du-c\|_{M}=\alpha\inf_{c\in\mathbb{R}}\|D(u-cx)\|_{M}=\inf_{\ell\in\mathcal{L}}\|D(u-\ell)\|_{M}\leq\|u+\mathcal{L}\|_{\mathrm{BV}/\mathcal{L}}.$

We remark that this equivalence of norms is not specific to the one-
dimensional case, and in fact a similar estimate is proved in [9, Thm. 3.3].

With the equivalence of norms and having identified a separable predual space,
compactness of $B$ can be characterized by sequences and follows by an
application of the Banach-Alaoglu theorem. ∎

##  2 Extremal points of $\operatorname{TGV}$

In this section, we consider the extremal points of the set $\mathcal{B}$:

######  Definition 1.

An element $u\in\mathcal{B}$ is called an extremal point of $\mathcal{B}$ if

$\displaystyle u=u_{1}+s(u_{2}-u_{1})\ \text{for some}\leavevmode\nobreak\
u_{1},u_{2}\in\mathcal{B}\text{ and }s\in(0,1)\text{ implies }u=u_{1}=u_{2}.$

Since $\mathcal{B}$ is weak* compact in $\mathrm{BV}(0,T)/\mathcal{L}$, the
set of all extremal points of $\mathcal{B}$, denoted by
$\operatorname{Ext}\mathcal{B}$ is nonempty due to the Krein-Milman theorem.
We prove the following characterization:

######  Theorem 1.

The extremal points of
$\mathcal{B}=\big{\\{}u+\mathcal{L}\in\mathrm{BV}(0,T)/\mathcal{L}\;\big{|}\;\operatorname{TGV}(u)\leq
1\big{\\}}$ satisfy

$\operatorname{Ext}\mathcal{B}=\pm\left(\left\\{\frac{1}{\alpha}S_{x_{0}}\;\Big{|}\;x_{0}\in(0,T)\right\\}\cup\left\\{\frac{1}{\beta}K_{x_{1}}\;\Big{|}\;\operatorname{dist}(x_{1},\partial(0,T))>\frac{\beta}{\alpha}\right\\}\right)+\mathcal{L},$
(2.1)

where, denoting by $1_{(a,b)}$ the characteristic function of an interval
$(a,b)$,

$S_{x_{0}}=1_{(x_{0},T)}\text{ and
}K_{x_{1}}=\begin{cases}1_{(0,x_{1})}(x_{1}-x)&\text{ if }x_{1}<T/2\\\
1_{(x_{1},T)}(x-x_{1})&\text{ if }x_{1}\geq T/2.\end{cases}$

The strategy is centered around the fact that since in one dimension we can
always find primitives, $\operatorname{TGV}$ can be rewritten as an infimal
convolution:

######  Lemma 1.

For every $\bar{u}\in\mathrm{BV}(0,T)$ we have

$\operatorname{TGV}(\bar{u})=\inf_{\begin{subarray}{c}v,h\in\mathrm{BV}(0,T),\\\
\bar{u}=v+h\end{subarray}}\left[\,\alpha\operatorname{TV}(v)+\beta\operatorname{TV}(Dh)\,\right],$
(2.2)

and if $\bar{w}\in\mathrm{BV}(0,T)$ is such that

$\displaystyle\operatorname{TGV}(\bar{u})=\alpha\|D\bar{u}-\bar{w}\|_{M}+\beta\|D\bar{w}\|_{M}$

then the infimum is attained for

$\bar{v}=\bar{u}-\int^{\boldsymbol{\cdot}}_{0}\bar{w}\leavevmode\nobreak\
\mathrm{d}t,\leavevmode\nobreak\
\bar{h}=\int^{\boldsymbol{\cdot}}_{0}\bar{w}\leavevmode\nobreak\ \mathrm{d}t.$
(2.3)

Moreover we can define $\operatorname{TGV}$ also in the quotient space
$\mathrm{BV}(0,T)/\mathcal{L}$, and there it can also be written as an infimal
convolution:

$\operatorname{TGV}(\bar{u})=\operatorname{TGV}(\bar{u}+\mathcal{L})=\inf_{\begin{subarray}{c}v+\mathcal{L},h+\mathcal{L}\in\mathrm{BV}(0,T)/\mathcal{L},\\\
\bar{u}=v+h\end{subarray}}\left[\,\alpha\inf_{\ell\in\mathcal{L}}\operatorname{TV}(v+\ell)+\beta\operatorname{TV}(Dh)\,\right].$
(2.4)

###### Proof.

First note that since $Dh\in\mathrm{BV}(0,T)$ we have, denoting by $D^{a}$ and
$D^{s}$ the absolutely continuous and singular parts with respect to the
Lebesgue measure, that $D^{s}h=0$ and thus

$\displaystyle D^{s}h=0,\leavevmode\nobreak\
D^{s}\bar{u}=D^{s}v,\leavevmode\nobreak\ D^{a}v=D^{a}\bar{u}-Dh.$

As a consequence we can rewrite

$\displaystyle\inf_{\begin{subarray}{c}v,h\in\mathrm{BV}(0,T),\\\
\bar{u}=v+h\end{subarray}}\left[\,\alpha\operatorname{TV}(v)+\beta\operatorname{TV}(Dh)\,\right]$
$\displaystyle=\inf_{Dh\in\mathrm{BV}(0,T)}\alpha\|D^{s}\bar{u}\|_{M}+\alpha\|D^{a}\bar{u}-Dh\|_{M}+\beta\operatorname{TV}(Dh)$
$\displaystyle=\inf_{w\in\mathrm{BV}(0,T)}\alpha\|D\bar{u}-w\|_{M}+\beta\operatorname{TV}(w)$

where we use that for every $w\in\mathrm{BV}(0,T)$ there is
$W\in\mathrm{BV}(0,T)$ with $DW=w$. Moreover we have $\bar{u}=\bar{v}+\bar{h}$
and

$\displaystyle\alpha\operatorname{TV}(\bar{v})+\beta\operatorname{TV}(D\bar{h})=\alpha\|D\bar{u}-\bar{w}\|_{M}+\beta\|D^{2}\bar{w}\|_{M}=\operatorname{TGV}(\bar{u})$

finishing the proof of (2.2) and (2.3). Finally, to deduce (2.4) from (2.2) we
just notice that by definition
$\operatorname{TV}(Dh)=\operatorname{TV}\big{(}D(h+\ell)\big{)}$ for all
$\ell\in\mathcal{L}$. ∎

Then we have the following more general negative result, which allows us to
reduce the possible candidates for extremal points:

######  Lemma 2.

Let $f,g$ be convex positively one-homogeneous functionals defined on some
Banach space $X$, and

$(f\,\Box\,g)(u):=\inf_{u=v+w}f(v)+g(w)$ (2.5)

their infimal convolution. Given $u_{0}\in X$, assume that either
$f(u_{0})\neq 1$ or $g(u_{0})\neq 1$, and $v_{0},w_{0}$ are such that

$(f\,\Box\,g)(u_{0})=1,\quad u_{0}=v_{0}+w_{0},\quad f(v_{0})+g(w_{0})=1,\quad
f(v_{0})\neq 0,\quad g(w_{0})\neq 0$

so (2.5) is exact at $u_{0}$ with the infimum attained by $v_{0}$ and $w_{0}$.
Then $u_{0}$ cannot be an extremal point of the convex set

$\left\\{u\in X\,\middle|\,(f\,\Box\,g)(u)\leq 1\right\\}.$

###### Proof.

First, notice that we must have $f(v_{0})\leq g(v_{0})$. To see this, assume
for the sake of contradiction that $g(v_{0})<f(v_{0})$. Being convex and one-
homogeneous $g$ is sublinear, so we have that

$g(v_{0}+w_{0})\leq g(v_{0})+g(w_{0})<f(v_{0})+g(w_{0})$

and the pair $(v_{0},w_{0})$ was not optimal for the infimal convolution,
since $(0,v_{0}+w_{0})$ has lower energy. Similarly we conclude that
$g(w_{0})\leq f(w_{0})$.

Moreover, we claim that

$(f\,\Box\,g)(v_{0})=f(v_{0})\in(0,1),\quad(f\,\Box\,g)(w_{0})=g(w_{0})\in(0,1).$
(2.6)

To see this, notice that if on the contrary we had for some $v_{1},w_{1}$ with
$v_{0}=v_{1}+w_{1}$ that

$(f\,\Box\,g)(v_{0})=f(v_{1})+g(w_{1})<f(v_{0})$

we would end up, using the sublinearity, with

$f(v_{0})+g(w_{0})>f(v_{1})+g(w_{0})+g(w_{1})\geq f(v_{1})+g(w_{0}+w_{1}),$

and again the pair $(v_{0},w_{0})$ could not have been optimal for
$(f\,\Box\,g)(u_{0})$. The claim for $w_{0}$ is again entirely similar.

Using in (2.6) that the infimal convolution is one-homogeneous as well we
arrive at

$(f\,\Box\,g)\left(\frac{v_{0}}{f(v_{0})}\right)=1,\quad(f\,\Box\,g)\left(\frac{w_{0}}{g(w_{0})}\right)=1,$

which means that we can write

$u_{0}=f(v_{0})\frac{v_{0}}{f(v_{0})}+g(w_{0})\frac{w_{0}}{g(w_{0})}.$

Now if $v_{0}/f(v_{0})\neq w_{0}/g(w_{0})$, these two points and $u_{0}$ are
collinear in $\left\\{u\in X\,\middle|\,(f\,\Box\,g)(u)=1\right\\}$, and
$u_{0}$ could not be extremal. Otherwise

$v_{0}=c\,w_{0}\text{ with }c:=f(v_{0})/g(w_{0}),\text{ so
}u_{0}=(1+c)w_{0}=(1+c^{-1})v_{0}.$

By one-homogeneity and the first part of the proof

$\displaystyle g(u_{0})=(1+c)g(w_{0})$
$\displaystyle\leq(1+c)f(w_{0})=f(u_{0})\text{ and }$ $\displaystyle
f(u_{0})=(1+c^{-1})f(v_{0})$ $\displaystyle\leq(1+c^{-1})g(v_{0})=g(u_{0}),$

from which we conclude $f(u_{0})=g(u_{0})=(f\,\Box\,g)(u_{0})=1$, contrary to
our assumption. ∎

Applied to our case, the above lemma yields:

######  Proposition 2.

Denoting $\mathcal{B}:=\\{u+\mathcal{L}\;\big{|}\;\operatorname{TGV}(u)\leq
1\\}$ we have

$\operatorname{Ext}\mathcal{B}\subset\pm\left(\left\\{\,u\;\Big{|}\;\|Du\|_{M}\leq\frac{1}{\alpha}\,\right\\}\cup\left\\{\,u\;\Big{|}\;\|D^{2}u\|_{M}\leq\frac{1}{\beta}\,\right\\}\right)+\mathcal{L}\subset\mathcal{B},$
(2.7)

and every element in $\operatorname{Ext}\mathcal{B}$ is either of the form
$\pm\\{S_{x}/\alpha+\mathcal{L}\\}$ or $\pm\\{K_{x}/\beta+\mathcal{L}\\}$.

###### Proof.

We consider $\operatorname{TGV}$ as an infimal convolution in
$\mathrm{BV}(0,T)/\mathcal{L}$ as in (2.4) of Lemma 1. First, we notice that
for each equivalence class $u+\mathcal{L}$ there exist representatives
$\bar{u}$ for which

$\inf_{\ell\in\mathcal{L}}\|D(u+\ell)\|_{M}=\|D\bar{u}\|_{M},$ (2.8)

since this is a convex and coercive functional in $\mathcal{L}/\mathcal{C}$.
This also implies that the functional
$u\mapsto\inf_{\ell\in\mathcal{L}}\|D(u+\ell)\|_{M}$ is convex, since if
$u+\mathcal{L}=(1-\lambda)(u_{1}+\mathcal{L})+\lambda(u_{2}+\mathcal{L})$ and
$\bar{u_{1}},\bar{u_{2}}$ are such representatives we have

$\displaystyle\inf_{\ell\in\mathcal{L}}\|D(u+\ell)\|_{M}$
$\displaystyle\leq\big{\|}D\big{(}(1-\lambda)\bar{u_{1}}+\lambda\bar{u_{2}}\big{)}\big{\|}_{M}$
$\displaystyle\leq(1-\lambda)\|D\bar{u_{1}}\|_{M}+\lambda\|D\bar{u_{2}}\|_{M}$
$\displaystyle=(1-\lambda)\inf_{\ell\in\mathcal{L}}\|D(u_{1}+\ell)\|_{M}+\lambda\inf_{\ell\in\mathcal{L}}\|D(u_{2}+\ell)\|_{M}.$

Moreover since $\mathcal{L}$ is a linear subspace the functional above is also
positively one-homogeneous, so we can apply Lemma 2. In view of it, to arrive
at (2.7) we just need to check that

$\left\\{u+\mathcal{L}\,\Big{|}\,\alpha\inf_{\ell\in\mathcal{L}}\|D(u+\ell)\|_{M}\leq
1\right\\}=\left\\{\,u\;\Big{|}\;\|Du\|_{M}\leq\frac{1}{\alpha}\,\right\\}+\mathcal{L},$

which again follows directly by the existence of minimal representatives
(2.8).

Notice that the assumptions of Lemma 2 are not a restriction since the case
$\|Du\|_{M}/\alpha=\|D^{2}u\|_{M}/\beta=\operatorname{TGV}(u)=1$ (for $u$ an
optimal representative as above) is also included in (2.7). ∎

For the positive direction, the piecewise constant functions in (2.1) can be
handled directly:

######  Proposition 3.

Let $u\in\\{S_{x}/\alpha\\}+\mathcal{L}$, $x\in(0,T)$, be given. Assume that
there are $u_{1}+\mathcal{L},u_{2}+\mathcal{L}\in\mathcal{B}$ as well as
$\lambda\in(0,1)$ with $u=(1-\lambda)u_{1}+\lambda u_{2}$. Then we have
$u_{1},u_{2}\in\\{S_{x}/\alpha\\}+\mathcal{L}$.

###### Proof.

Again we may assume that $\mathrm{TGV}(u_{1})=\mathrm{TGV}(u_{2})=1$. For
every $i=1,2$ there exists $w_{i}\in\mathrm{BV}(0,T)$ with

$\displaystyle\alpha\|Du_{i}-w_{i}\|_{M}+\beta\|Dw_{i}\|_{M}=\alpha\|D^{s}u_{i}\|_{M}+\alpha\|D^{a}u_{i}-w_{i}\|_{M}+\beta\|Dw_{i}\|_{M}=\operatorname{TGV}(u_{i})=1.$

In particular, this implies

$\displaystyle\alpha\|D^{s}u_{i}\|_{M}\leq\alpha\|D^{s}u_{i}\|_{M}+\alpha\|D^{a}u_{i}-w_{i}\|_{M}+\beta\|Dw_{i}\|_{M}=\operatorname{TGV}(u_{i})=1.$
(2.9)

By assumption we have that

$\displaystyle Du=\delta_{x}/\alpha+c=(1-\lambda)Du_{1}+\lambda Du_{2}$

for some $c\in\mathbb{R}$. Thus, separating into singular and absolutely
continuous parts, we get

$\displaystyle\delta_{x}/\alpha=(1-\lambda)D^{s}u_{1}+\lambda
D^{s}u_{2},\leavevmode\nobreak\ c=(1-\lambda)D^{a}u_{1}+\lambda D^{a}u_{2}.$

By extremality of $\delta_{x}$ for the unit ball in $M(0,T)$ and
$\lambda\in(0,1)$, the first equality is only possible if
$D^{s}u_{1}=D^{s}u_{2}=\delta_{x}/\alpha$. Now, since $\alpha|D^{s}u_{i}|=1$,
(2.9) yields

$\displaystyle\alpha\|D^{a}u_{i}-w_{i}\|_{M}+\beta\|Dw_{i}\|_{M}=\inf_{w\in\mathrm{BV}(0,T)}\left[\,\alpha\|D^{a}u_{i}-w\|_{M}+\beta\|Dw\|_{M}\,\right]=0.$

which is only possible if $D^{a}u_{i}\in\mathcal{C}$. Combining the previous
observations we get that $Du_{i}\in\\{\delta_{x}/\alpha\\}+\mathcal{C}$ and
thus $u_{i}\in\\{S_{x}/\alpha\\}+\mathcal{L}$. ∎

To proceed further, we need to examine in detail the behaviour of
$\operatorname{TGV}$ for piecewise affine functions of the form $K_{x_{1}}$.

######  Proposition 4.

Consider the functions $K_{x_{1}}$ defined in Theorem 1. Assuming $x_{1}\geq
T/2$, if

$\frac{\beta}{\alpha}\leq T-x_{1}$ (2.10)

we have
$\operatorname{TGV}_{\alpha,\beta}(K_{x_{1}})=\beta\|D^{2}u\|_{M}=\beta$, and
otherwise
$\operatorname{TGV}_{\alpha,\beta}(K_{x_{1}})=\alpha\|Du\|_{M}=\alpha(T-x_{1})$.
For $x_{1}<T/2$ analogous statements hold, in which each appearance of
$T-x_{1}$ is replaced by $x_{1}$. Moreover, as long as
$\beta/\alpha\neq\min(x_{1},T-x_{1})$ the inner minimization problem

$\operatorname*{arg\,min}_{w\in\mathrm{BV}(0,T)}\alpha\|DK_{x_{1}}-w\|_{M}+\beta\|Dw\|_{M}$
(2.11)

admits a unique minimizer $w_{K_{x_{1}}}$, where the uniqueness is understood
in terms of almost everywhere equality.

###### Proof.

By definition, in case $x_{1}\in[T/2,T)$ we have $K_{x_{1}}(x)=(x-x_{1})^{+}$
and if $x_{1}\in(0,T)$ instead $K_{x_{1}}(x)=(x-x_{1})^{+}-x+x_{1}$. Since
(2.11) is invariant by sign changes and constant shifts in $DK_{x_{1}}$, we
can consider without loss of generality just the function $(\cdot-x_{1})^{+}$.
We then notice that since $D(\cdot-x_{1})^{+}(x)\in\\{0,1\\}$, as in [15,
Prop. 4.5] by comparing with truncations one sees that any minimizer of (2.11)
takes values in the interval $[0,1]$ almost everywhere. Moreover, by [1, Thm.
3.27] we can compute one-dimensional $\operatorname{TV}$ through the essential
(pointwise) variation

$\operatorname{TV}(w)=\inf_{z=w\leavevmode\nobreak\
a.e.}\sup\left\\{\sum_{i=1}^{n-1}|z(t_{i+1})-z(t_{i})|\,\middle|\,n\geq 2,\
0<t_{1}<\ldots<t_{n}<T\right\\},$ (2.12)

and the infimum is achieved for a particular representative $z_{w}$, which
will be assumed in the rest of the proof (that is, from here on $w=z_{w}$). In
particular (2.12) implies that

$\operatorname{TV}(w)\geq\sup_{x\in(0,T)}w(x)-\inf_{x\in(0,T)}w(x)=\sup w-\inf
w.$ (2.13)

To see this, assume $w$ is not constant (since otherwise there is nothing to
prove) and consider sequences $\\{x_{k}\\}_{k}$ and $\\{y_{k}\\}_{k}$ for
which $w(x_{k})\to\inf w$ and $w(y_{k})\to\sup w$. Since $w$ is not constant,
for all $k$ large enough we must have $\min(x_{k},y_{k})<\max(x_{k},y_{k})$,
which allows to use these points for partitions in (2.12). With (2.13) we have
for (2.11) the lower energy bound

$\displaystyle\alpha\|DK-w\|_{M}+\beta\|Dw\|_{M}$ $\displaystyle\geq\alpha
x_{1}\inf w+\alpha(T-x_{1})(1-\sup w)+\beta(\sup w-\inf w)$ (2.14)
$\displaystyle=(\alpha x_{1}-\beta)\inf w+(\beta-\alpha(T-x_{1}))\sup
w+\alpha(T-x_{1}),$

where we note that the last term does not depend on $w$. Our strategy is to
first minimize the right hand side with respect to $\inf w$ and $\sup w$ and
then produce functions with these extrema for which (2.14) holds with
equality, which must then be minimizers. To accomplish this for every
$\alpha$, $\beta$ and $x_{1}$ we distinguish four cases:

  * •

If $x_{1}\geq\beta/\alpha$ and $(T-x_{1})\geq\beta/\alpha$, then the right
hand side of (2.14) is clearly lowest if $\inf w=0$ and $\sup w=1$, in which
case it reaches the value $\beta$. Moreover, when $w=D(\cdot-
x_{1})^{+}=S_{x_{1}}$ we have equality in (2.14), so it is a minimizer with
cost $\beta$.

  * •

For $x_{1}<\beta/\alpha$ and $(T-x_{1})<\beta/\alpha$, the first term compels
us to maximize $\inf w$ while the second term enforces minimizing $\sup w$. In
case $x_{1}-\beta/\alpha>(T-x_{1})-\beta/\alpha$ (that is, $x_{1}>T/2$) the
second term is stronger, so it is advantageous to choose $\sup w=0$, hence
$w\equiv 0$ minimizes. In case $x_{1}\leq T/2$ we can use $w\equiv 1$ instead.
Moreover, in both cases the bound (2.14) is attained with the value $\alpha$.

  * •

The two remaining cases $x_{1}<\beta/\alpha\leq(T-x_{1})$ and
$x_{1}\geq\beta/\alpha>(T-x_{1})$ can be handled as simplifications of the
previous one, since in this case there is no competition between the two terms
and we can just choose $w\equiv 1$ or $w\equiv 0$ respectively. Again, there
is equality in (2.14) with value $\alpha$.

Finally, we notice that the only possibility that does not lead to a unique
minimizer is when one of the terms of the right hand side of (2.14) vanishes.
This means that either $x_{1}=\beta/\alpha$ in which case $w=c\,D(\cdot-
x_{1})^{+}$ is a minimizer for all $c\in[0,1]$, or that
$(T-x_{1})=\beta/\alpha$ with $w=c+(1-c)D(\cdot-x_{1})^{+}$ minimizing for all
$c\in[0,1]$. ∎

With this, we can prove that all of the piecewise affine functions in (2.1)
are indeed extremal:

######  Proposition 5.

Let $u\in\\{K_{x}/\beta\\}+\mathcal{L}$,
$\operatorname{dist}(x,\partial(0,T))>\beta/\alpha$, be given. Assume that
there are $u_{1},u_{2}\in B$ as well as $\lambda\in(0,1)$ with
$u=(1-\lambda)u_{1}+\lambda u_{2}$. Then we have
$u_{1},u_{2}\in\\{K_{x}/\beta\\}+\mathcal{L}$.

###### Proof.

We may assume without loss of generality that
$\mathrm{TGV}(u_{1})=\mathrm{TGV}(u_{2})=1$. For $i=1,2$ there exists
$w_{i}\in\mathrm{BV}(0,T)$ with

$\displaystyle\beta\|Dw_{i}\|_{M}\leq\alpha\|Du_{i}-w_{i}\|_{M}+\beta\|Dw_{i}\|_{M}=\operatorname{TGV}(u_{i})=1.$

Moreover, by Proposition 4 the problem

$\displaystyle\min_{w\in\mathrm{BV}(0,T)}\left[\,\alpha\|Du-w\|_{M}+\beta\|Dw\|_{M}\,\right]$

has a unique minimizer given by $w=Du$. Now, by assumption, we have
$Du=(1-\lambda)Du_{1}+\lambda Du_{2}$. Consequently, the function
$w_{\lambda}=(1-\lambda)w_{1}+\lambda w_{2}$ satisfies

$\displaystyle 1=\operatorname{TGV}(u)$ $\displaystyle\leq\alpha\|Du-
w_{\lambda}\|_{M}+\beta\|Dw_{\lambda}\|_{M}$
$\displaystyle\leq(1-\lambda)\operatorname{TGV}(u_{1})+\lambda\operatorname{TGV}(u_{2})=1.$

Thus we conclude $w_{\lambda}=Du$ and

$\displaystyle\delta_{x}/\beta=(1-\lambda)Dw_{1}+\lambda Dw_{2}$

Again, by extremality of $\delta_{x}$ for the unit ball in $M(0,T)$, we get
$w_{i}\in\\{S_{x}/\beta\\}+\mathcal{C}$. Now, since

$\displaystyle 1=\beta\|Dw_{i}\|_{M}\leq\operatorname{TGV}(u_{i})=1$

we arrive at $w_{i}=Du_{i}$ which finally yields
$u_{i}\in\\{K_{x}/\beta\\}+\mathcal{L}$. ∎

On the other hand the equality case can be resolved manually:

######  Remark 1.

If $\operatorname{dist}(x_{1},\partial(0,T))=\beta/\alpha$ then
$K_{x_{1}}/\beta+\mathcal{L}$ is not in $\operatorname{Ext}B$. To see this,
assuming without loss of generality that $x_{1}>T/2$, we can write
$K_{x_{1}}/\beta$ as the convex combination

$\frac{1}{\beta}K_{x_{1}}=\frac{1}{2}u_{1}+\frac{1}{2}u_{2}\,\text{ with
}\,u_{1}=\frac{2}{\beta}K_{x_{1}}-\frac{2}{\beta}K_{(T+x_{1})/2}\text{ and
}\,u_{2}=\frac{2}{\beta}K_{(T+x_{1})/2},$

and $u_{1}+\mathcal{L},u_{2}+\mathcal{L}$ belong to $\mathcal{B}$ since
arguing as in Proposition 4 we have that the inner minimizers must be
$w_{i}\equiv 0$ and

$\operatorname{TGV}(u_{1})=\alpha\|Du_{1}\|_{M}=\operatorname{TGV}(u_{2})=\alpha\|Du_{2}\|_{M}=\frac{\alpha}{\beta}(T-x_{1})=1.$

Finally, putting the above facts together we get:

###### Proof of Theorem 1.

By Proposition 2, elements in $\operatorname{Ext}\mathcal{B}$ can only be
equivalence classes corresponding to either piecewise constant functions with
one jump in $\pm\\{S_{x}/\alpha\\}+\mathcal{L}$ or piecewise affine functions
with one kink in $\pm\\{K_{x}/\beta\\}+\mathcal{L}$. Proposition 3 implies
that all the piecewise constant candidates are indeed extremal. For the
piecewise affine candidates, we see by Proposition 5 that those with
$\operatorname{dist}(x,\partial(0,T))>\beta/\alpha$ are also extremal, and by
Proposition 4 that those with
$\operatorname{dist}(x,\partial(0,T))<\beta/\alpha$ are not. The equality case
is resolved by Remark 1. ∎

##  3 Optimization problems with $\operatorname{TGV}$-regularization

In the following, we discuss the consequences of Theorem 1 on minimization
problems of the form

$\displaystyle\min_{u\in\mathrm{BV}(0,T)}J(u),\quad
J(u)=f(u)+\operatorname{TGV}_{\alpha,\beta}(u).$ ($\mathcal{P}$)

Here, $f\colon L^{2}(0,T)\to\mathbb{R}$ denotes a smooth but not necessarily
convex fidelity term and the $\operatorname{TGV}$-functional plays the role of
a regularizer. From a practical point of view, problems of this form are
interesting since the inclusion of the $\operatorname{TGV}$-functional is
expected to favor piecewise affine minimizers. This section aims at
formalizing this observation. In particular, we present sufficient conditions
for the existence of a solution $\bar{u}$ which is sparse in the sense that,
up to a shift in $\mathcal{L}$, it can be written as a finite conic
combination of piecewise constant and continuous piecewise affine functions,
i.e., there are sets $\\{\bar{x}^{S}_{j}\\}^{N_{S}}_{j=1},\leavevmode\nobreak\
\\{\bar{x}^{K}_{j}\\}^{N_{K}}_{j=1}$ in $(0,T)$ such that

$\displaystyle\bar{u}=(1/\alpha)\sum^{N_{S}}_{j=1}\bar{\sigma}^{S}_{j}\bar{\lambda}^{S}_{j}S_{\bar{x}^{S}_{j}}+(1/\beta)\sum^{N_{K}}_{i=j}\bar{\sigma}^{K}_{j}\bar{\lambda}^{K}_{j}K_{\bar{x}^{K}_{j}}+\bar{a}x+\bar{b}.$
(3.1)

for some $\bar{\sigma}^{S}_{j},\bar{\sigma}^{K}_{j}\in\\{-1,1\\}$,
$\bar{\lambda}^{S}_{j},\bar{\lambda}^{K}_{j}\geq
0,\bar{a},\bar{b}\in\mathbb{R}$. Two characteristic cases are discussed.
First, we show that the kinks and jumps of a solution $\bar{u}$ correspond to
maximizers and minimizers of certain dual variables. This can be derived from
necessary first-order optimality conditions for Problem ($\mathcal{P}$) which
are provided in Section 3.2. Consequently, if these only admit finitely many
global extrema, the function $\bar{u}$ is of the form (3.1). Second, we
consider structured objective functionals of the form $f(u)=F(Hu)$ where $F$
is convex and $H$ is a linear operator with finite range. In this case, the
existence of a sparse solution follows from convex representer theorems for
abstract minimization problems, see [3, 2]. Loosely speaking, applied to the
present problem, these state the existence of a minimizer $\bar{u}$ which is
given by a finite conic combination of functions $\bar{u}_{j}$ with
$\bar{u}_{j}+\mathcal{L}\in\operatorname{Ext}\mathcal{B}$. Thus, in virtue of
Theorem 1, it will be of the form (3.1).

###  3.1 Linear minimization over $\operatorname{TGV}$-balls

For abbreviation set

$\displaystyle\mathcal{S}\coloneqq\left\\{\,\pm
S_{x}/\alpha\;|\;x\in(0,T)\,\right\\},\leavevmode\nobreak\
\mathcal{K}\coloneqq\left\\{\,\pm
K_{x}/\beta\;|\;x\in(\beta/\alpha,T-\beta/\alpha)\,\right\\}$

throughout the following sections. Moreover, with abuse of notation, define

$\displaystyle\operatorname{Ext}B\coloneqq\mathcal{S}\cup\mathcal{K}\subset\mathrm{BV}(0,T),\text{
for }B:=\big{\\{}u\in\mathrm{BV}(0,T)\;|\;\operatorname{TGV}(u)\leq
1\big{\\}}.$

Note that for the unit ball $\mathcal{B}$ in $\mathrm{BV}(0,T)/\mathcal{L}$,
see (1.4), and its set of extremal points, Theorem 1, we have

$\displaystyle\mathcal{B}=\left\\{\,u+\mathcal{L}\;|\;u\in
B\,\right\\},\leavevmode\nobreak\
\operatorname{Ext}\mathcal{B}=\left\\{\,u+\mathcal{L}\;|\;u\in\operatorname{Ext}B\,\right\\}.$

Now, given $\varphi\in L^{2}(0,T)$, consider the infimizing problem

$\displaystyle\inf_{v\in B}(\varphi,v)_{L^{2}}.$ (3.2)

Problems of this form will play a vital role in the following sections. We
point out that the set $B$ is unbounded in $\mathrm{BV}(0,T)$, i.e., (3.2)
does not necessarily admit a minimizer. In the following lemma we show that it
is well-posed if $\varphi$ is orthogonal to the kernel of the
$\operatorname{TGV}$-functional. Moreover, in order to find a solution, it
suffices to minimize over the smaller set $\operatorname{Ext}B$.

######  Theorem 2.

Assume that $\varphi\in L^{2}(0,T)$ satisfies $(\varphi,\ell)_{L^{2}}=0$ for
all $\ell\in\mathcal{L}$. Then (3.2) admits a minimizer in $B$ and there holds

$\displaystyle\min_{v\in
B}(\varphi,v)_{L^{2}}=\min_{v\in\operatorname{Ext}B}(\varphi,v)_{L^{2}}.$

###### Proof.

Let $v\in B$ be arbitrary but fixed. Using that $T<+\infty$ and the Sobolev
embedding [1, Thm. 3.47] for $\mathrm{BV}(0,T)$ there holds

$\displaystyle(\varphi,v)_{L^{2}}=(\varphi,v+\ell)_{L^{2}}\leq\|\varphi\|_{L^{2}}\|v+\ell\|_{L^{2}}\leq\|\varphi\|_{L^{2}}\|v+\ell\|_{L^{\infty}}\leq
c\,\|v+\ell\|_{\mathrm{BV}}\quad\text{for all}\leavevmode\nobreak\
\ell\in\mathcal{L}$

for some $c>0$ independent of $v$ and $\ell$. In particular, this implies

$\displaystyle(\varphi,v)_{L^{2}}\leq
c\inf_{\ell\in\mathcal{L}}\|v+\ell\|_{\mathrm{BV}},$

i.e., $\varphi$ induces a linear and continuous functional
$\Phi\colon\mathrm{BV}(0,T)/\mathcal{L}\to\mathbb{R}$ with

$\displaystyle\Phi(u+\mathcal{L})=(\varphi,u)_{L^{2}}\quad\text{for
all}\leavevmode\nobreak\ u+\mathcal{L}\in\mathrm{BV}(0,T)/\mathcal{L}.$

Now by Proposition 1 and the Banach-Alaoglu theorem, the set $\mathcal{B}$ is
weak* compact in $\mathrm{BV}(0,T)/\mathcal{L}$. Hence there exists
$\bar{v}\in B$ with

$\displaystyle\Phi(\bar{v}+\mathcal{L})=\min_{v+\mathcal{L}\in\mathcal{B}}\Phi(v+\mathcal{L}).$
(3.3)

Now we claim that

$\displaystyle\min_{v+\mathcal{L}\in\mathcal{B}}\Phi(v+\mathcal{L})=\min_{v+\mathcal{L}\in\operatorname{Ext}(\mathcal{B})}\Phi(v+\mathcal{L}).$
(3.4)

In order to prove this, consider the convex and compact image set

$\displaystyle\Phi(\mathcal{B})\coloneqq\left\\{\,\Phi(v+\mathcal{L})\;|\;v\in
B\,\right\\}\subset\mathbb{R},$

for which it is readily verified that

$\displaystyle\operatorname{Ext}\Phi(\mathcal{B})=\left\\{\min_{v+\mathcal{L}\in\mathcal{B}}\Phi(v+\mathcal{L}),\max_{v+\mathcal{L}\in\mathcal{B}}\Phi(v+\mathcal{L})\right\\}.$

By invoking [3, Lemma 3.2] we finally get

$\displaystyle\min_{v+\mathcal{L}\in\mathcal{B}}\Phi(v+\mathcal{L})\in\left\\{\min_{v+\mathcal{L}\in\operatorname{Ext}\mathcal{B}}\Phi(v+\mathcal{L}),\max_{v+\mathcal{L}\in\operatorname{Ext}\mathcal{B}}\Phi(v+\mathcal{L})\right\\}.$

which proves (3.4). Now, let $\bar{v}\in\operatorname{Ext}B$ be such that
(3.3) holds. Then we have

$\displaystyle(\varphi,\bar{v})_{L^{2}}=\Phi(\bar{v}+\mathcal{L})\leq\Phi(v+\mathcal{L})=(\varphi,v)_{L^{2}}\quad\text{for
all}\leavevmode\nobreak\ v\in B.$

Together with $\operatorname{Ext}B\subset B$ the proof is finished. ∎

###  3.2 Necessary first-order optimality conditions

The aim of this section is to prove first-order necessary optimality
conditions for Problem ($\mathcal{P}$). Later, these will be used to infer
structural properties of its minimizers. For this purpose, start by defining
the $L^{2}$-subdifferential of the $\operatorname{TGV}$-functional at
$\bar{u}\in\mathrm{BV}(0,T)$ as

$\displaystyle\partial_{2}\operatorname{TGV}(\bar{u})\coloneqq\left\\{\,\varphi\in
L^{2}(0,T)\;|\;(\varphi,u-\bar{u})_{L^{2}}+\operatorname{TGV}(\bar{u})\leq\operatorname{TGV}(u)\quad\text{for
all}\leavevmode\nobreak\ u\in\mathrm{BV}(0,T)\;\,\right\\}.$ (3.5)

Note that $\partial_{2}\operatorname{TGV}(\bar{u})$ can be empty. A full
characterization of the subdifferential is given as follows:

######  Theorem 3.

Let $\bar{u}\in\mathrm{BV}(0,T)$ be given and let $\bar{w}\in\mathrm{BV}(0,T)$
be such that

$\displaystyle\operatorname{TGV}(\bar{u})=\alpha\|D\bar{u}-\bar{w}\|_{M}+\beta\|D\bar{w}\|_{M}.$

Moreover, for $\bar{\varphi}\in L^{2}(0,T)$ define

$\displaystyle\bar{p}=-\int^{\boldsymbol{\cdot}}_{0}\bar{\varphi}(x)\leavevmode\nobreak\
\mathrm{d}x,\leavevmode\nobreak\
\bar{P}=-\int^{\boldsymbol{\cdot}}_{0}\bar{p}(x)\leavevmode\nobreak\
\mathrm{d}x.$ (3.6)

Then we have $\bar{\varphi}\in\partial_{2}\operatorname{TGV}(\bar{u})$ if and
only if

  * •

There holds

$\bar{p}\in H^{1}_{0}(0,T),\leavevmode\nobreak\ \bar{P}\in H^{2}(0,T)\cap
H^{1}_{0}(0,T),\leavevmode\nobreak\
\|\bar{p}\|_{C}\leq\alpha,\leavevmode\nobreak\ \|\bar{P}\|_{C}\leq\beta.$
(3.7)

  * •

We have

$\begin{split}\operatorname{supp}(D\bar{u}-\bar{w})_{\pm}&\subset\left\\{\,x\in(0,T)\;|\;\bar{p}(x)=\pm\alpha\,\right\\},\\\
\operatorname{supp}(D\bar{w})_{\pm}&\subset\left\\{\,x\in(0,T)\;|\;\bar{P}(x)=\pm\beta\,\right\\}.\end{split}$
(3.8)

We break down the proof into smaller steps. The following proposition serves
as a starting point.

######  Proposition 6.

Let $\bar{u}\in\mathrm{BV}(0,T)$ and $\bar{\varphi}\in L^{2}(0,T)$. Then there
holds $\bar{\varphi}\in\partial_{2}\operatorname{TGV}(\bar{u})$ if and only if

$\displaystyle(\bar{\varphi},\ell)_{L^{2}}=0,\leavevmode\nobreak\
(\bar{\varphi},\bar{u})_{L^{2}}=\operatorname{TGV}(\bar{u}),\leavevmode\nobreak\
(\bar{\varphi},v)_{L^{2}}\leq\operatorname{TGV}(v)$

for all $\ell\in\mathcal{L}$, $v\in\mathrm{BV}(0,T)$.

###### Proof.

By definition, there holds
$\bar{\varphi}\in\partial_{2}\operatorname{TGV}(\bar{u})$ if and only if

$\displaystyle(\bar{\varphi},u-\bar{u})_{L^{2}}+\operatorname{TGV}(\bar{u})\leq\operatorname{TGV}(u)\quad\text{for
all}\leavevmode\nobreak\ u\in\mathrm{BV}(0,T)$ (3.9)

Of course, this is equivalent to $\bar{u}$ being a minimizer of

$\displaystyle\min_{v\in\mathrm{BV}(0,T)}\left[-(\bar{\varphi},v)_{L^{2}}+\operatorname{TGV}(v)\right].$
(3.10)

Since $\operatorname{TGV}(\cdot)$ is positively one-homogeneous and
$\operatorname{TGV}(u+\ell)=\operatorname{TGV}(u)$ for all
$u\in\mathrm{BV}(0,T)$ and $\ell\in\mathcal{L}$, this holds (with value zero)
if and only if

$\displaystyle(\bar{\varphi},\ell)_{L^{2}}=0,\leavevmode\nobreak\
(\bar{\varphi},\bar{u})_{L^{2}}=\operatorname{TGV}(\bar{u}),\leavevmode\nobreak\
(\bar{\varphi},v)_{L^{2}}\leq\operatorname{TGV}(v)$ (3.11)

for all $\ell\in\mathcal{L}$ and $v\in\mathrm{BV}(0,T)$. ∎

Now we first prove that $\bar{\varphi}$ is orthogonal to $\mathcal{L}$ if and
only if $\bar{p}$ and $\bar{P}$ admit zero boundary conditions.

######  Lemma 3.

Let $\bar{\varphi}\in L^{2}(0,T)$ be given and let $\bar{p}$ and $\bar{P}$ be
defined as in (3.6). The following statements are equivalent:

  * •

There holds $(\bar{\varphi},\ell)_{L^{2}}=0$ for all $\ell\in\mathcal{L}$.

  * •

We have $\bar{p}\in H^{1}_{0}(0,T)$ and $\bar{P}\in H^{1}_{0}(0,T)\cap
H^{2}(0,T)$.

###### Proof.

By construction we have $\bar{p}\in H^{1}(0,T)$, $\bar{P}\in H^{2}(0,T)$ and
$\bar{p}(0)=\bar{P}(0)=0$. Consequently it suffices to show that
$(\bar{\varphi},\ell)_{L^{2}}=0$ for all $\ell\in\mathcal{L}$ holds if and
only if $\bar{p}(T)=\bar{P}(T)=0$. Testing $\bar{\varphi}$ with
$u_{1}=1_{(0,T)}\in\mathcal{L}$ and $u_{2}=x\in\mathcal{L}$ reveals

$\displaystyle(\bar{\varphi},u_{1})_{L^{2}}=-\bar{p}(T)$

as well as

$\displaystyle(\bar{\varphi},u_{2})_{L^{2}}=-\bar{p}(T)+(\bar{p},u_{1})_{L^{2}}=-\bar{p}(T)-\bar{P}(T)$

by partial integration. Noting that
$\mathcal{L}=\operatorname{span}\\{u_{1},u_{2}\\}$ finishes the proof. ∎

Next, it is shown that the boundedness condition

$\displaystyle(\bar{\varphi},v)_{L^{2}}\leq\operatorname{TGV}(v)\quad\text{for
all}\leavevmode\nobreak\ v\in\mathrm{BV}(0,T)$

corresponds to certain bounds on the uniform norm of $\bar{p}$ and $\bar{P}$,
respectively.

######  Lemma 4.

Assume that there holds

$\displaystyle(\bar{\varphi},\ell)_{L^{2}}=0\quad\text{for
all}\leavevmode\nobreak\ \ell\in\mathcal{L}.$

Then the following statements are equivalent:

  * 1.

There holds $(\bar{\varphi},v)_{L^{2}}\leq\operatorname{TGV}(v)$ for all
$v\in\mathrm{BV}(0,T)$.

  * 2.

We have

$\displaystyle\|\bar{p}\|_{C}\leq\alpha,\text{ and }|\bar{P}(x)|\leq\beta\
\text{for all}\leavevmode\nobreak\
x\in\left[\frac{\beta}{\alpha},T-\frac{\beta}{\alpha}\right].$

  * 3.

We have $\|\bar{p}\|_{C}\leq\alpha$ and $\|\bar{P}\|_{C}\leq\beta$.

###### Proof.

Note that there holds

$\displaystyle(\bar{\varphi},v)_{L^{2}}\leq\operatorname{TGV}(v)\ \text{for
all}\leavevmode\nobreak\ v\in\mathrm{BV}(0,T)\Leftrightarrow\max_{v\in
B}(\bar{\varphi},v)_{L^{2}}\leq
1\Leftrightarrow\max_{v\in\operatorname{Ext}B}(\bar{\varphi},v)_{L^{2}}\leq
1.$

due to the positive one-homogeneity of the $\operatorname{TGV}$-functional as
well as Theorem 2. Testing $\bar{\varphi}$ with $\pm S_{x}$ and $\pm K_{x}$
and integrating by parts yields

$\displaystyle\pm(\bar{\varphi},S_{x})_{L^{2}}=\pm\bar{p}(x),\leavevmode\nobreak\
(\bar{\varphi},K_{x})_{L^{2}}=(\bar{p},DK_{x})_{L^{2}}=\pm\bar{P}(x)$

for every $x\in(0,T)$. Due to the characterization of $\operatorname{Ext}B$ in
Theorem 1 we thus conclude the equivalence of $1.$ and $2.$. Moreover, we
directly get that $3.$ implies $1.$ by the definition of $\operatorname{TGV}$
in (1.1) and of $\bar{p}$ and $\bar{P}$ in (3.6). Hence it only remains to
show that $2.$ implies $3.$. To this end, we estimate

$\displaystyle|\bar{P}(x)|\leq\int^{x}_{0}|p_{k}(x)|\leavevmode\nobreak\
\mathrm{d}x\leq\alpha|x|\leq\beta\quad\text{for all}\leavevmode\nobreak\
x\in\left(0,\frac{\beta}{\alpha}\right]$

as well as

$\displaystyle|\bar{P}(x)|\leq\int^{T}_{x}|p_{k}(x)|\leavevmode\nobreak\
\mathrm{d}x\leq\alpha|T-x|\leq\beta\quad\text{for all}\leavevmode\nobreak\
x\in\left[T-\frac{\beta}{\alpha},T\right)$

using

$\displaystyle\bar{P}(x)=-\int^{x}_{0}\bar{p}(x)\leavevmode\nobreak\
\mathrm{d}x=\int^{T}_{x}\bar{p}(x)\leavevmode\nobreak\
\mathrm{d}x-\bar{P}(T)=\int^{T}_{x}\bar{p}(x)\leavevmode\nobreak\
\mathrm{d}x.$

Hence we have $\|\bar{P}\|_{C}\leq\beta$. ∎

Finally we require the following result on the support of Radon measures.

######  Lemma 5.

Let $\mu\in M(0,T)$ and $p\in C_{0}(0,T)$ be given. Moreover let $\gamma>0$
with $\|p\|_{C}\leq\gamma$ be given. Then there holds

$\displaystyle\langle p,\mu\rangle=\gamma\|\mu\|_{M}$ (3.12)

if and only if

$\displaystyle\operatorname{supp}\mu_{\pm}\subset\left\\{\,x\in(0,T)\;|\;\bar{p}(x)=\pm\gamma\,\right\\}$
(3.13)

where $\mu=\mu_{+}-\mu_{-}$ denotes the Jordan decomposition.

###### Proof.

Obviously, both, (3.12) and (3.13), trivially hold if $\mu=0$. Thus, w.l.o.g,
assume that $\mu\neq 0$. In this case, both conditions can only hold if
$\|p\|_{C}=\gamma$ due to

$\displaystyle\langle
p,\mu\rangle\leq\|p\|_{C}\|\mu\|_{M}\leq\gamma\|\mu\|_{M}$

and $\operatorname{supp}\mu\neq\emptyset$. Now, let us first assume (3.12).
Since $\mu\neq 0$ and $p\neq 0$, (3.13) is implied by [10, Lemma 3.4].
Conversely, assume (3.13). Then we have

$\displaystyle\langle p,\mu\rangle$
$\displaystyle=\int^{T}_{0}p(x)\leavevmode\nobreak\
\mathrm{d}\mu(x)=\gamma\int^{T}_{0}\leavevmode\nobreak\
\mathrm{d}|\mu|(x)=\alpha\|\mu\|_{M},$

finishing the proof. ∎

Putting together the previous observations we finally prove Theorem 3.

###### Proof of Theorem 3.

In virtue of Proposition 6 and Lemmas 3 and 4 it suffices to show that (3.8)
is equivalent to

$\displaystyle(\bar{\varphi},\bar{u})_{L^{2}}=\operatorname{TGV}(\bar{u})$
(3.14)

if we have $\|\bar{p}\|_{C}\leq\alpha$ and $\|\bar{P}\|_{C}\leq\beta$. For
this purpose note that there holds

$\displaystyle\operatorname{TGV}(\bar{u})=\alpha\|D\bar{u}-\bar{w}\|_{M}+\beta\|D\bar{w}\|_{M}.$

as well as

$\displaystyle(\bar{\varphi},\bar{u})_{L^{2}}=\langle\bar{p},D\bar{u}-\bar{w}\rangle+\langle\bar{P},D\bar{w}\rangle$

due to Lemma 1 and partial integration. Now we point out

$\displaystyle\langle\bar{p},D\bar{u}-\bar{w}\rangle\leq\|p\|_{C}\|D\bar{u}-\bar{w}\|_{M},\leavevmode\nobreak\
\langle\bar{P},D\bar{w}\rangle\leq\|P\|_{C}\|D\bar{w}\|_{M}.$

Consequently, (3.14) holds if and only if

$\displaystyle\langle\bar{p},D\bar{u}-\bar{w}\rangle=\|p\|_{C}\|D\bar{u}-\bar{w}\|_{M},\leavevmode\nobreak\
\langle\bar{P},D\bar{w}\rangle=\|P\|_{C}\|D\bar{w}\|_{M}.$

The equivalence between then (3.8) and (3.14) follows immediately from Lemma
5. ∎

In the following we silently assume the existence of a minimizer to
($\mathcal{P}$). The Riesz-representative of the Fréchet-derivative of $f$ at
$u\in L^{2}(0,T)$ is further denoted by $\nabla f(u)\in L^{2}(0,T)$. Using
Theorem 3, the following first order necessary optimality conditions for
Problem ($\mathcal{P}$) are readily derived.

######  Theorem 4.

Let $\bar{u}\in\mathrm{BV}(0,T)$ denote a minimizer to ($\mathcal{P}$) and set

$\displaystyle\bar{p}=\int^{\boldsymbol{\cdot}}_{0}\nabla
f(\bar{u})(x)\leavevmode\nobreak\
\mathrm{d}x,\quad\bar{P}(x)=-\int^{\boldsymbol{\cdot}}_{0}\bar{p}(x)\leavevmode\nobreak\
\mathrm{d}x.$ (3.15)

Then $\bar{p}$ and $\bar{P}$ satisfy (3.7) and (3.8). If $f$ is convex and
(3.7) as well as (3.8) are satisfied for $\bar{p},\bar{P}$ in (3.15), then
$\bar{u}$ is a solution to ($\mathcal{P}$).

###### Proof.

Since $f$ is Fréchet-differentiable and $\bar{u}$ is a minimizer of
($\mathcal{P}$) there holds $-\nabla
f(\bar{u})\in\partial_{2}\operatorname{TGV}(\bar{u})$. According to Theorem 3,
this is equivalent to $\bar{p}$ and $\bar{P}$ satisfying (3.7) and (3.8).
Finally, if $f$ is convex, then $-\nabla
f(\bar{u})\in\partial_{2}\operatorname{TGV}(\bar{u})$ is also sufficient for
optimality. This finishes the proof. ∎

Similar conditions were already derived in [23] for a quadratic $f$. However
their results rely on the Fenchel duality theorem for convex problems. In
contrast, we take the direct approach involving the subdifferential in Theorem
3 which easily extends to the nonconvex case. Exploiting Theorem 4, we can
conclude first structural properties of minimizers to ($\mathcal{P}$). In
particular, every minimizer is affine linear close to the boundary.

######  Lemma 6.

Let $\bar{u}\in\mathrm{BV}(0,T)$ denote a minimizer to ($\mathcal{P}$). Then
there is $\varepsilon>0$ as well as $a_{1},a_{2},b_{1},b_{2}\in\mathbb{R}$
such that

$\displaystyle\bar{u}(x)=a_{1}x+b_{1}\text{ for }x\in(0,\varepsilon),\text{
and }\leavevmode\nobreak\ \bar{u}(x)=a_{2}x+b_{2}\text{ for
}x\in(T-\varepsilon,T).$

###### Proof.

Since $\bar{p},\bar{P}\in H^{1}_{0}(0,T)$ and $H^{1}_{0}(0,T)\hookrightarrow
C_{0}(0,T)$ there is $\varepsilon>0$ such that

$\displaystyle\max\left\\{|\bar{p}(x)|/\alpha,|\bar{P}(x)|/\beta\right\\}<1\quad\forall
x\in(0,\varepsilon)\cup(T-\varepsilon,T).$

Hence from (3.8) we conclude

$\displaystyle D\bar{w}=0,\leavevmode\nobreak\
D\bar{u}-\bar{w}=0\quad\text{on}\leavevmode\nobreak\
(0,\varepsilon)\cup(T-\varepsilon,T).$

By integration this implies $D\bar{u}=\bar{w}\equiv a_{1}$ and thus
$\bar{u}(x)=a_{1}c+b_{1}$ for some $a_{1},a_{2}\in\mathbb{R}$ on
$(0,\varepsilon)$. The statement for $(T-\varepsilon,T)$ follows analogously.
∎

Moreover, if the regularization parameters are large, then
$\operatorname{TGV}(\bar{u})=0$, i.e., $\bar{u}\in\mathcal{L}$. We note that
results in this spirit were proved in [24] for the the denoising case.

######  Lemma 7.

Let $f\colon L^{2}(0,T)\to\mathbb{R}$ be norm-coercive, i.e., there holds

$\displaystyle\|u_{k}\|_{L^{2}}\rightarrow+\infty\Rightarrow
f(u_{k})\rightarrow+\infty.$

Moreover assume that $\nabla f$ maps bounded sets to bounded sets. Then there
are $\alpha^{*},\beta^{*}>0$ such that for all
$\alpha>\alpha^{*},\beta>\beta^{*}$, every solution $\bar{u}$ to
($\mathcal{P}$) is of the form $\bar{u}(x)=a_{\bar{u}}x+b_{\bar{u}}$ for some
$a_{\bar{u}},b_{\bar{u}}\in\mathbb{R}$.

###### Proof.

First, we claim that the solution set of ($\mathcal{P}$) is bounded in
$L^{2}(0,T)$ independently of $\alpha$ and $\beta$. If this is not the case,
then there are sequences $\\{(\alpha_{k},\beta_{k})\\}_{k}$ as well as
$\\{\bar{u}_{k}\\}_{k}$ such that $\bar{u}_{k}$ is a minimizer of
($\mathcal{P}$) with $\alpha=\alpha_{k},\leavevmode\nobreak\ \beta=\beta_{k}$
as well as $\|\bar{u}_{k}\|_{L^{2}(\Omega)}\rightarrow+\infty$. Then there
also holds

$\displaystyle+\infty=\limsup_{k\rightarrow\infty}f(\bar{u}_{k})\leq\limsup_{k\rightarrow\infty}J(\bar{u}_{k})\leq
J(0)=f(0)<+\infty$

which yields a contradiction. Now, let $\alpha,\beta>0$ be arbitrary and let
$\bar{u}$ denote any minimizer of ($\mathcal{P}$) with dual variables
$\bar{p},\leavevmode\nobreak\ \bar{P}$ as defined in (3.15) and
$\bar{w}\in\mathrm{BV}(0,T)$ with

$\displaystyle\operatorname{TGV}(\bar{u})=\alpha\|D\bar{u}-\bar{w}\|_{M}+\beta\|D\bar{w}\|_{M}.$

Since $\nabla f$ maps bounded sets to bounded sets, there holds $\|\nabla
f(\bar{u})\|_{L^{2}}\leq M$ for some $M>0$ independent of $\bar{u}$ as well as
of $\alpha,\beta$. For every $x\in(0,T)$ we then estimate

$\displaystyle|\bar{p}(x)|\leq\int^{T}_{0}|\nabla
f(\bar{u})(x)|\leavevmode\nobreak\ \mathrm{d}x\leq T\|\nabla
f(\bar{u})\|_{L^{2}}\leq TM$

as well as

$\displaystyle|\bar{P}(x)|\leq T\max_{x\in(0,T)}|\bar{p}(x)|\leq T^{2}\|\nabla
f(\bar{u})\|_{L^{2}}\leq T^{2}M.$

Hence, for every $\alpha>TM$ and $\beta>T^{2}M$, we conclude

$\displaystyle D\bar{w}=0,\leavevmode\nobreak\
D\bar{u}-\bar{w}=0\quad\text{on}\leavevmode\nobreak\ (0,T)$

from (3.8). As in Lemma 6, we finally get that $\bar{u}$ is affine linear
finishing the proof for $\alpha^{*}=TM$ and $\beta^{*}=T^{2}M$. ∎

###  3.3 Existence of sparse minimizers

In this section we put the focus on investigating sufficient conditions for
the existence of a sparse minimizer $\bar{u}$ in the sense of (3.1). Two
characteristic settings are considered. First, we show that any minimizer of
($\mathcal{P}$) is sparse if the associated dual variables $\bar{p}$ and
$\bar{P}$ only admite a finite number of global maximizers and minimizers.

######  Theorem 5.

Let $\bar{u}\in\mathrm{BV}(0,T)$ denote a minimizer to ($\mathcal{P}$) and let
$\bar{w}\in\mathrm{BV}(0,T)$ be such that

$\displaystyle\operatorname{TGV}(\bar{u})=\alpha\|D\bar{u}-\bar{w}\|_{M}+\beta\|D\bar{w}\|_{M}.$

Moreover let $\bar{p}$ and $\bar{P}$ be defined as in (3.15) and assume that
there are sets $\\{\bar{x}^{S}_{j}\\}^{N_{S}}_{j=1}$,
$\\{\bar{x}^{K}_{j}\\}^{N_{K}}_{j=1}$ in $(0,T)$, $N_{S},N_{K}\geq 0$, with

$\displaystyle\left\\{\,x\in(0,T)\;|\;\bar{p}(x)=\pm\alpha\,\right\\}=\left\\{\bar{x}^{S}_{j}\right\\}^{N_{S}}_{j=1},\quad\left\\{\,x\in(0,T)\;|\;\bar{P}(x)=\pm\beta\,\right\\}=\left\\{\bar{x}^{K}_{j}\right\\}^{N_{K}}_{j=1}.$
(3.16)

Then $\bar{u}$ is of the form (3.1) where

$\displaystyle\bar{\sigma}^{S}_{j}=\bar{p}(\bar{x}^{S}_{j})/\alpha,\leavevmode\nobreak\
j=1,\dots,N_{S},\quad\bar{\sigma}^{K}_{j}=\bar{P}(\bar{x}^{K}_{j})/\beta,\leavevmode\nobreak\
j=1,\dots,N_{K}$

and $(\bar{\lambda}^{S},\bar{\lambda}^{K},\bar{a},\bar{b})$ is a solution to

$\displaystyle\min_{\begin{subarray}{c}{\lambda}^{S}\in\mathbb{R}^{N_{S}}_{+},\
{\lambda}^{K}\in\mathbb{R}^{N_{K}}_{+}\\\
a,b\in\mathbb{R}\end{subarray}}\left[f\big{(}u(\lambda^{S},\lambda^{K},a,b)\big{)}+\sum^{N_{S}}_{j=1}{\lambda}^{S}_{j}+\sum^{N_{K}}_{j=1}{\lambda}^{K}_{j}\right]$
(3.17)

subject to

$\displaystyle
u(\lambda^{S},\lambda^{K},a,b)=(1/\alpha)\sum^{N_{S}}_{j=1}\bar{\sigma}^{S}_{j}{\lambda}^{S}_{j}S_{\bar{x}^{S}_{j}}+(1/\beta)\sum^{N_{K}}_{j=1}\bar{\sigma}^{K}_{j}{\lambda}^{K}_{j}K_{\bar{x}^{K}_{j}}+{a}x+{b}.$
(3.18)

Moreover there holds

$\displaystyle\bar{w}=(1/\alpha)\sum^{N_{K}}_{j=1}\bar{\sigma}^{K}_{j}\bar{\lambda}^{K}_{j}S_{\bar{x}^{K}_{j}}+\bar{a},\text{
and
}\operatorname{TGV}(\bar{u})=\sum^{N_{S}}_{j=1}\bar{\lambda}^{S}_{j}+\sum^{N_{K}}_{j=1}\bar{\lambda}^{K}_{j}.$

###### Proof.

In virtue of Theorem 4 and (3.8) we get

$\displaystyle
D\bar{w}=(1/\beta)\sum^{N_{K}}_{j=1}\bar{\sigma}^{K}_{j}\bar{\lambda}^{K}_{j}\delta_{\bar{x}^{K}_{j}}$

for some $\bar{\lambda}^{K}\in\mathbb{R}^{N_{K}}_{+}$. Hence, by integration,
there holds

$\displaystyle\bar{w}=(1/\beta)\sum^{N_{K}}_{j=1}\bar{\sigma}^{K}_{j}\bar{\lambda}^{K}_{j}S_{\bar{x}^{K}_{j}}+\bar{a}$

where $\bar{a}\in\mathbb{R}$. Then, again invoking (3.8), we conclude

$\displaystyle
D\bar{u}=(1/\alpha)\sum^{N_{S}}_{j=1}\bar{\sigma}^{S}_{j}\bar{\lambda}^{S}_{j}\delta_{\bar{x}^{K}_{j}}+\bar{w}$

and thus integrating yields

$\displaystyle\bar{u}=(1/\alpha)\sum^{N_{S}}_{j=1}\bar{\sigma}^{S}_{j}\bar{\lambda}^{S}_{j}S_{\bar{x}^{S}_{j}}+(1/\beta)\sum^{N_{K}}_{i=j}\bar{\sigma}^{K}_{j}\bar{\lambda}^{K}_{j}K_{\bar{x}^{K}_{j}}+\bar{a}x+\bar{b}$

for some $\bar{\lambda}^{S}\in\mathbb{R}^{N_{S}}_{+},\bar{b}\in\mathbb{R}$.
Next we prove that

$\displaystyle\operatorname{TGV}(\bar{u})=\sum^{N_{S}}_{j=1}\bar{\lambda}^{S}_{j}+\sum^{N_{K}}_{j=1}\bar{\lambda}^{K}_{j}.$
(3.19)

We readily verify that

$\displaystyle\operatorname{TGV}\big{(}u(\lambda^{S},\lambda^{K},a,b)\big{)}\leq\sum^{N_{S}}_{j=1}{\lambda}^{S}_{j}+\sum^{N_{K}}_{j=1}{\lambda}^{K}_{j}$

due to the convexity and positive one-homogeneity of the
$\operatorname{TGV}$-functional as well as $\operatorname{TGV}(\pm S_{x})\leq
1,\leavevmode\nobreak\ \operatorname{TGV}(\pm K_{x})\leq 1$ for every
$x\in(0,T)$. Moreover there holds

$\displaystyle\sum^{N_{S}}_{j=1}\bar{\lambda}^{S}_{j}+\sum^{N_{K}}_{j=1}\bar{\lambda}^{K}_{j}=-(\nabla
f(\bar{u}),\bar{u})_{L^{2}}\leq\operatorname{TGV}(\bar{u})$

due to

$\displaystyle\pm\bar{p}(x)=\mp(\nabla
f(\bar{u}),S_{x})_{L^{2}},\quad\pm\bar{P}(x)=\mp(\nabla
f(\bar{u}),K_{x})_{L^{2}}$

for every $x\in(0,T)$ as well as Proposition 6. This proves (3.19). Finally,
combining the previous observations, we arrive at

$\displaystyle
f(\bar{u})+\sum^{N_{S}}_{j=1}\bar{\lambda}^{S}_{j}+\sum^{N_{K}}_{j=1}\bar{\lambda}^{K}_{j}=J(\bar{u})$
$\displaystyle\leq J\big{(}u(\lambda^{S},\lambda^{K},a,b)\big{)}$
$\displaystyle\leq
f\big{(}u(\lambda^{S},\lambda^{K},a,b)\big{)}+\sum^{N_{S}}_{j=1}{\lambda}^{S}_{j}+\sum^{N_{K}}_{j=1}{\lambda}^{K}_{j}$

As a consequence, $(\bar{\lambda}^{S},\bar{\lambda}^{K},\bar{a},\bar{b})$ is a
minimizer of (3.17). ∎

In particular, this result is applicable if the dual variables are analytic.

######  Corollary 1.

Let $\bar{u}\in\mathrm{BV}(0,T)$ be a minimizer to ($\mathcal{P}$). Moreover
assume that the dual variables $\bar{p},\bar{P}$, see (3.15), are analytic.
Then $\bar{u}$ is of the form (3.1).

###### Proof.

Since the dual variables are nonzero and $\bar{p},\bar{P}\in C_{0}(0,T)$, we
conclude that the functions $\tilde{p}=\bar{p}-\alpha$ and
$\tilde{P}=\bar{P}-\beta$ are analytic and non-constant. Thus, the zero sets
of $\tilde{p}$ and $\tilde{P}$ cannot have any accumulation points, so they
are finite. As a consequence, Theorem 5 is applicable and the statement
follows. ∎

For the second setting, assume that the smooth part $f$ of the objective
functional is of composite form, i.e., $f(u)=F(Hu)$ where $F$ is a convex
function and $H$ is a linear and continuous operator with finite range. In
this setting, the following theorem states the existence of a sparse minimizer
without further assumptions on the dual variables.

######  Theorem 6.

Let $f(u)=F(Hu)$ be given where $H\colon L^{2}(0,T)\to Y$ is a linear and
continuous operator, $Y\simeq\mathbb{R}^{N}$ is a Hilbert space , and $F\colon
Y\to\mathbb{R}$ is convex and continuously Fréchet-differentiable. Moreover
assume that $F$ is norm-coercive on $Y$, i.e.,

$\displaystyle\|y\|_{Y}\rightarrow+\infty\Rightarrow F(y)\rightarrow+\infty$

and $H(L^{2}(0,T))=Y$. Define the subspace

$\displaystyle
H(\mathcal{L})\coloneqq\left\\{\,Hu\;|\;u\in\mathcal{L}\,\right\\}.$

Then Problem ($\mathcal{P}$) admits a solution $\bar{u}$ of the form (3.1)
with $N_{k}+N_{S}\leq N-\operatorname{dim}(H(\mathcal{L}))$ and

$\displaystyle\operatorname{TGV}(\bar{u})=\sum^{N_{S}}_{j=1}\bar{\lambda}^{S}_{j}+\sum^{N_{K}}_{j=1}\bar{\lambda}^{K}_{j}.$

###### Proof.

Given the stated assumptions, it is readily verified that [3, Theorem 1] can
be applied to Problem $\mathcal{P}$. This yields the existence of at least one
minimizer $\bar{u}$ to ($\mathcal{P}$) with

$\displaystyle\bar{u}=\bar{\psi}+\sum^{\bar{N}}_{j=1}\bar{\lambda}_{j}\bar{u}_{j},\leavevmode\nobreak\
\operatorname{TGV}(\bar{u})=\sum^{\bar{N}}_{j=1}\bar{\lambda}_{j}$

for some $\bar{\psi}\in\mathcal{L}$, $\bar{\lambda}_{j}>0$,
$\bar{u}_{j}\in\mathrm{BV}(0,T)$ with
$\bar{u}_{j}+\mathcal{L}\in\operatorname{Ext}\mathcal{B}$ and
$\bar{N}\leq\operatorname{dim}(Y/H(\mathcal{L}))$. The claim then follows by
the definition of $\mathcal{L}$, the characterization of
$\operatorname{Ext}\mathcal{B}$ in Theorem 1 and
$\operatorname{dim}(Y/H(\mathcal{L}))=\operatorname{dim}(Y)-\operatorname{dim}(H(\mathcal{L}))$.
∎

######  Remark 2.

It is worth pointing out that the results of Theorem 6 remain valid for
proper, convex and lower semicontinuous functionals $F\colon Y\to\mathbb{R}$.

######  Remark 3.

Of course, Theorem 5 and 6 raise the question whether there holds

$\displaystyle\operatorname{TGV}(u)=\sum^{N_{K}}_{j=1}\lambda^{K}_{j}+\sum^{N_{S}}_{j=1}\lambda^{S}_{j}$

for every $u\in\mathrm{BV}(0,T)$ of the form (3.18). This is not the case as
we will see in the following. For this purpose let $\alpha,\beta>0$, $T>0$ as
well as $\bar{x}_{1},\bar{x}_{2}\in[T/2,T-\beta/\alpha)$,
$\bar{x}_{2}>\bar{x}_{1}$, be such that

$\displaystyle|\bar{x}_{1}-\bar{x}_{2}|<\frac{\beta}{2\alpha}.$

Moreover, fix coefficients $\bar{\lambda}_{1},\bar{\lambda}_{2}>0$ with

$\displaystyle|\bar{\lambda}_{1}-\bar{\lambda}_{2}|<\frac{\beta}{2\alpha},\leavevmode\nobreak\
|T-\bar{x}_{2}|<\bar{\lambda}_{1}+\bar{\lambda}_{2}.$

Set
$\bar{u}=\bar{\lambda}_{1}K_{\bar{x}_{1}}/\beta-\bar{\lambda}_{2}K_{\bar{x}_{2}}/\beta$.
Then we readily calculate

$\displaystyle\operatorname{TGV}(\bar{u})\leq\frac{\alpha}{\beta}\|\bar{\lambda}_{1}S_{\bar{x}_{1}}-\bar{\lambda}_{2}S_{\bar{x}_{2}}\|_{L^{1}}$
$\displaystyle=\frac{\alpha}{\beta}\left(\bar{\lambda}_{1}|\bar{x}_{2}-\bar{x}_{1}|+|\bar{\lambda}_{2}-\bar{\lambda}_{1}||T-\bar{x}_{2}|\right)$
$\displaystyle<\bar{\lambda}_{1}/2+|T-\bar{x}_{2}|/2$
$\displaystyle<\bar{\lambda}_{1}+\bar{\lambda}_{2}$

which gives a counterexample.

##  4 A minimization algorithm

This section is devoted to the analysis of a simple solution algorithm for
Problem ($\mathcal{P}$). In particular, the presented procedure does not rely
on a discretization of the underlying functions. This is a challenging problem
for a variety of reasons. First, it requires to work directly on the non-
reflexive space $\mathrm{BV}(0,T)$. Second, we also have to take into account
the nonsmoothness of the $\operatorname{TGV}$-functional. Finally, note that
evaluating $\operatorname{TGV}(u)$ already requires the solution of a
nonsmooth minimization problem. Our method follows the spirit of [4] and
alternates between the update of a set $\mathcal{A}_{k}$ in
$\operatorname{Ext}B$ via solving a linear minimization problem over $B$ and
improving the iterate
$u_{k}\in\operatorname{cone}(\mathcal{A}_{k})+\mathcal{L}$. The former can be
implemented efficiently using Theorem 2 while the latter is done by minimizing
a $\ell_{1}$-regularized surrogate functional over the finite dimensional set
$\operatorname{cone}(\mathcal{A}_{k})+\mathcal{L}$. This completely avoids
evaluating the $\operatorname{TGV}$-functional throughout the iterations and
eventually guarantees the subsequential convergence of $\\{u_{k}\\}_{k}$
towards stationary points of ($\mathcal{P}$).

###  4.1 The procedure

Given a finite ordered set $\mathcal{A}=\\{u_{j}\\}^{N}_{j=1}$ in
$\operatorname{Ext}B$ consider the following finite dimensional minimization
problem:

$\displaystyle\min_{\lambda\in\mathbb{R}^{N}_{+},\ell\in\mathcal{L}}\left[f\left(\sum^{N}_{j=1}\lambda_{j}u_{j}+\ell\right)+\sum^{N}_{j=1}\lambda_{j}\right].$
($\mathcal{P}(\mathcal{A})$)

Note that the objective functional in ($\mathcal{P}(\mathcal{A})$) constitutes
an upper bound on $J$ for every function
$u\in\operatorname{cone}(\mathcal{A})+\mathcal{L}$.

######  Lemma 8.

Let $(\lambda,\ell)\in\mathbb{R}^{N}_{+}\times\mathcal{L}$ be arbitrary and
set

$\displaystyle
u=\sum^{N}_{j=1}\lambda_{j}u_{j}+\ell\in\operatorname{cone}(\mathcal{A})+\mathcal{L}.$

Then there holds

$\displaystyle J(u)\leq f(u)+\sum^{N}_{j=1}\lambda_{j}.$

###### Proof.

Since the $\operatorname{TGV}$-functional is convex and one-homogeneous it is
also sublinear. Hence there holds

$\displaystyle\operatorname{TGV}(u)\leq\sum^{N}_{j=1}\lambda_{j}\operatorname{TGV}(u_{j})=\sum^{N}_{j=1}\lambda_{j}$
(4.1)

using $\operatorname{TGV}(u_{j})=1$ as well as componentwise nonnegativity of
$\lambda$. The claim readily follows. ∎

Now we propose a greedy method for the computation of a stationary point of
($\mathcal{P}$) which works as follows: Let the current active set
$\mathcal{A}_{k}=\\{u^{k}_{j}\\}^{N_{k}}_{j=1}$, $N_{k}\geq 0$, in
$\operatorname{Ext}B$ as well as the iterate $u_{k}$ be given. Assume that
$u_{k}$ is constituted by a minimizing pair $(\lambda^{k},\ell^{k})$ to
$(\mathcal{P}(\mathcal{A}_{k}))$ as

$\displaystyle u_{k}=\sum^{N_{k}}_{j=1}\lambda^{k}_{j}u^{k}_{j}+\ell_{k}.$
(4.2)

Then, we first compute the current dual variables defined by

$\displaystyle p_{k}=\int^{\boldsymbol{\cdot}}_{0}\nabla
f(u_{k})(s)\leavevmode\nobreak\ \mathrm{d}s,\leavevmode\nobreak\
P_{k}=-\int^{\boldsymbol{\cdot}}_{0}p_{k}(s)\leavevmode\nobreak\
\mathrm{d}s\in C_{0}(0,T)$ (4.3)

as well as points $\hat{x}^{S}_{k},\hat{x}^{K}_{k}\in(0,T)$ with

$\displaystyle|p_{k}(\hat{x}^{S}_{k})|=\|p_{k}\|_{C},\leavevmode\nobreak\
|P_{k}(\hat{x}^{K}_{k})|=\|P_{k}\|_{C}.$

If $\max\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\\}\leq 1$ the method stops
with $\bar{u}=u_{k}$ being a stationary point for ($\mathcal{P}$).

######  Proposition 7.

Let $(\lambda^{k},\ell^{k})\in\mathbb{R}^{N}_{+}\times\mathcal{L}$ denote a
minimizer of $(\mathcal{P}(\mathcal{A}_{k}))$ and set

$\displaystyle u_{k}=\sum^{N_{k}}_{j=1}{\lambda}^{k}_{j}u^{k}_{j}+\ell^{k}.$

Define the dual variables $p_{k}$ and $P_{k}$ as in (4.3). Then these satisfy
$p_{k}\in H^{1}_{0}(0,T)$ and $P_{k}\in H^{2}(0,T)\cap H^{1}_{0}(0,T)$, and if
$\max\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\\}\leq 1$ then $u_{k}$ is a
stationary point of ($\mathcal{P}$) and
$\operatorname{TGV}(u_{k})=\sum^{N_{k}}_{j=1}\lambda^{k}_{j}$.

###### Proof.

The necessary first-order optimality conditions for Problem
$(\mathcal{P}(\mathcal{A}_{k}))$ are given by

$\displaystyle(\nabla f(u_{k}),\ell)_{L^{2}}=0\ \text{for
all}\leavevmode\nobreak\ \ell\in\mathcal{L},\quad-(\nabla
f(u_{k}),u^{k}_{j})_{L^{2}}\leq 1\ \text{for all}\leavevmode\nobreak\
j=1,\dots,N_{k}$ (4.4)

implying $p_{k}\in H^{1}_{0}(0,T)$ and $P_{k}\in H^{2}(0,T)\cap
H^{1}_{0}(0,T)$ by Lemma 3, as well as

$\displaystyle-(\nabla
f(u_{k}),u_{k})_{L^{2}}=\sum^{N_{k}}_{j=1}\lambda^{k}_{j}.$ (4.5)

Moreover, if

$\displaystyle\max\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\\}\leq 1,$

then we have

$\displaystyle-(\nabla f(u_{k}),u)\leq\operatorname{TGV}(u)\quad\text{for
all}\leavevmode\nobreak\ u\in\mathrm{BV}(0,T)$

according to Lemma 4. Combining these observations with (4.1) we conclude

$\displaystyle\sum^{N_{k}}_{j=1}\lambda^{k}_{j}=-(\nabla
f(u_{k}),u_{k})_{L^{2}}\leq\operatorname{TGV}(u_{k})\leq\sum^{N_{k}}_{j=1}\lambda^{k}_{j}$

Thus, in virtue of Proposition 6, $u_{k}$ is a stationary point of
($\mathcal{P}$) and
$\operatorname{TGV}(u_{k})=\sum^{N_{k}}_{j=1}\lambda^{k}_{j}$. ∎

Otherwise, if $\max\\{\|\bar{p}\|_{C}/\alpha,\|\bar{P}\|_{C}/\beta\\}>1$,
define

$\displaystyle\widehat{u}_{k}=\begin{cases}(\operatorname{sign}(p_{k}(\hat{x}^{S}_{k}))/\alpha)\,S_{\hat{x}^{S}_{k}}&\|p_{k}\|_{C}/\alpha\geq\|P_{k}\|_{C}/\beta\\\
-(\operatorname{sign}(P_{k}(\hat{x}^{K}_{k})/\beta)\,L_{\hat{x}^{K}_{k}}&\text{else}.\end{cases}$
(4.6)

and update the active set by adding $\widehat{u}_{k}$ to it. More in detail,
set

$\displaystyle\mathcal{A}^{+}_{k}=\mathcal{A}_{k}\cup\\{\widehat{u}_{k}\\}=\\{u^{k,+}_{j}\\}^{N^{+}_{k}}_{j=1}$
(4.7)

where we denote

$\displaystyle N^{+}_{k}=N_{k}+1,\leavevmode\nobreak\
u^{k,+}_{j}=u^{k}_{j}\leavevmode\nobreak\ \text{for all}\leavevmode\nobreak\
j=1,\dots,N,\leavevmode\nobreak\ u^{k,+}_{N^{+}_{k}}=\widehat{u}_{k}$

for abbreviation. The following proposition serves several purposes. First, it
shows that this update step is well-posed, i.e., $\widehat{u}_{k}$ is indeed
an element of $\operatorname{Ext}B$. Second, it relates the choice of
$\widehat{u}_{k}$ to the minimization of a particular linear functional over
$B$.

######  Proposition 8.

Let $\widehat{u}_{k}$ be defined as in (4.6). Then there holds
$\widehat{u}_{k}\in\operatorname{Ext}B$ as well as

$\displaystyle-\max{\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\\}}=(\nabla
f(u_{k}),\widehat{u}_{k})_{L^{2}}=\min_{v\in B}(\nabla f(u_{k}),v)_{L^{2}}.$
(4.8)

Moreover, there exists $C_{\widehat{u}}>0$ with
$\|\widehat{u}_{k}\|_{L^{2}}\leq C_{\widehat{u}}$ for all $k\geq 1$.

###### Proof.

First, note that $\pm S_{x}/\alpha\in\operatorname{Ext}B$ for all $x\in(0,T)$.
Thus, in order to prove that $\widehat{u}_{k}\in\operatorname{Ext}B$, it
suffices to show $\hat{x}^{K}_{k}\in(\beta/\alpha,T-\beta/\alpha)$ if
$\|p_{k}\|_{C}/\alpha<\|P_{k}\|_{C}/\beta$. In this case we readily verify

$\displaystyle|P_{k}(x)|\leq\int^{x}_{0}|p_{k}(x)|\leavevmode\nobreak\
\mathrm{d}x\leq|x|\|p_{k}\|_{C}<\frac{\alpha|x|}{\beta}\|P_{k}\|_{C}$

as well as

$\displaystyle|P_{k}(x)|\leq\int^{T}_{x}|p_{k}(x)|\leavevmode\nobreak\
\mathrm{d}x\leq|T-x|\|p_{k}\|_{C}<\frac{\alpha|T-x|}{\beta}\|P_{k}\|_{C}$

by noting that

$\displaystyle P_{k}(x)=-\int^{x}_{0}p_{k}(x)\leavevmode\nobreak\
\mathrm{d}x,\quad 0=-\int^{T}_{0}p_{k}(x)\leavevmode\nobreak\
\mathrm{d}x=P_{k}(x)-\int^{T}_{x}p_{k}(x)\leavevmode\nobreak\ \mathrm{d}x$

for every $x\in(0,T)$. Here we made explicit use of $P_{k}\in C_{0}(0,T)$ and
$\|p_{k}\|_{C}/\alpha<\|P_{k}\|_{C}/\beta$. Consequently we get
$|P_{k}(x)|<\|P_{k}\|_{C}$ for all
$x\in[0,T]\setminus(\beta/\alpha,T-\beta/\alpha)$ and thus
$\hat{x}^{K}_{k}\in(\beta/\alpha,T-\beta/\alpha)$.

Next we prove (4.8). To start we invoke (4.4) and Theorem 2 to arrive at

$\displaystyle\min_{v\in B}(\nabla f(u_{k}),v)_{L^{2}}$
$\displaystyle=\min_{v\in\operatorname{Ext}(B)}(\nabla f(u_{k}),v)_{L^{2}}.$

Moreover, from the characterization of $\operatorname{Ext}(B)$ in Theorem 1,
we have

$\displaystyle\min_{v\in\operatorname{Ext}(B)}$ $\displaystyle(\nabla
f(u_{k}),v)_{L^{2}}$
$\displaystyle=\min\left\\{\min_{\begin{subarray}{c}x\in(0,T),\\\
\sigma\in\\{-1,1\\}\end{subarray}}\sigma(\nabla
f(u_{k}),S_{x})_{L^{2}}/\alpha,\
\inf_{\begin{subarray}{c}x\in(\beta/\alpha,T-\beta/\alpha),\\\
\sigma\in\\{-1,1\\}\end{subarray}}\sigma(\nabla
f(u_{k}),K_{x})_{L^{2}}/\beta\right\\}.$

By partial integration we now verify

$\displaystyle\min_{\begin{subarray}{c}x\in(0,T),\\\
\sigma\in\\{-1,1\\}\end{subarray}}\sigma(\nabla
f(u_{k}),S_{x})_{L^{2}}/\alpha=\min_{\begin{subarray}{c}x\in(0,T),\\\
\sigma\in\\{-1,1\\}\end{subarray}}-\frac{\sigma
p_{k}(x)}{\alpha}\geq-\frac{\|p_{k}\|_{C}}{\alpha}$

as well as

$\displaystyle\inf_{\begin{subarray}{c}x\in(\beta/\alpha,T-\beta/\alpha),\\\
\sigma\in\\{-1,1\\}\end{subarray}}\sigma(\nabla
f(u_{k}),K_{x})_{L^{2}}/\beta=\inf_{\begin{subarray}{c}x\in(\beta/\alpha,T-\beta/\alpha),\\\
\sigma\in\\{-1,1\\}\end{subarray}}\frac{\sigma
P_{k}(x)}{\beta}\geq-\frac{\|P_{k}\|_{C}}{\beta}.$

In summary, these observations yield

$\displaystyle\min_{v\in B}(\nabla
f(u_{k}),v)_{L^{2}}\geq-\max\left\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\right\\}.$

The proof is now finished noting that

$\displaystyle(\nabla f(u_{k}),\widehat{u}_{k})_{L^{2}}$
$\displaystyle=\begin{cases}-\operatorname{sign}(p_{k}(\hat{x}^{s}_{k}))\frac{p_{k}(\hat{x}^{s}_{k})}{\alpha}&\|p_{k}\|_{C}/\alpha\geq\|P_{k}\|_{C}/\beta\\\
-\operatorname{sign}(P_{k}(\hat{x}^{\ell}_{k}))\frac{P_{k}(\hat{x}^{\ell}_{k})}{\beta}&\|p_{k}\|_{C}/\alpha<\|P_{k}\|_{C}/\beta\\\
\end{cases}$
$\displaystyle=\begin{cases}-\|p_{k}\|_{C}&\|p_{k}\|_{C}/\alpha\geq\|P_{k}\|_{C}/\beta\\\
-\|P_{k}\|_{C}/\beta&\|p_{k}\|_{C}/\alpha<\|P_{k}\|_{C}/\beta\\\ \end{cases}$
$\displaystyle=-\max\left\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\right\\}.$

Finally, $\|\widehat{u}_{k}\|_{L^{2}}\leq C_{\widehat{u}}$ for some
$C_{\widehat{u}}>0$ and all $k\geq 1$ follows by a direct computation. ∎

Subsequently, the next iterate is found as

$\displaystyle
u_{k+1}=\sum^{N^{+}_{k}}_{j=1}\lambda^{k,+}u^{k,+}_{j}+\ell^{k,+}$ (4.9)

for a minimizer $(\lambda^{k,+},\ell^{k,+})$ of
$(\mathcal{P}(\mathcal{A}^{+}_{k}))$. Now, the active set is pruned by
removing all extreme points which were assigned a zero weight, i.e.,

$\displaystyle\mathcal{A}_{k+1}=\mathcal{A}^{+}_{k}\setminus\left\\{\,u^{k,+}_{j}\;\middle|\;\lambda^{k,+}_{j}=0,\leavevmode\nobreak\
j\in\\{1,\dots,N^{+}_{k}\\}\,\right\\}$ (4.10)

and the iteration counter $k$ is incremented by one. Observe that this ensures
the well-posedness of Algorithm 1, i.e., $u_{k+1}$ is constituted by a
minimizing pair $(\lambda^{k+1},\ell^{k+1})$ in the sense of (4.2).

######  Proposition 9.

Let $u_{k+1}$ and $\mathcal{A}_{k+1}$ be defined as in (4.9) and (4.10),
respectively. Denoting $\mathcal{A}_{k+1}=\\{u^{k+1}_{j}\\}^{N_{k+1}}_{j=1}$,
there is a minimizing pair $(\lambda^{k+1},\ell^{k+1})$ to
$(\mathcal{P}(\mathcal{A}_{k+1}))$ such that $\lambda^{k+1}_{j}>0$,
$j=1,\dots,N_{k+1}$ as well as

$\displaystyle
u_{k+1}=\sum^{N_{k+1}}_{j=1}\lambda^{k+1}_{j}u^{k+1}_{j}+\ell^{k+1},\quad\sum^{N^{+}_{k}}_{j=1}\lambda^{k,+}_{j}=\sum^{N_{k+1}}_{j=1}\lambda^{k+1}_{j},\quad\min(\mathcal{P}(\mathcal{A}^{+}_{k}))=\min(\mathcal{P}(\mathcal{A}_{k+1})).$

###### Proof.

Introduce the set of indices

$\displaystyle\mathcal{I}_{k}\coloneqq\left\\{\,j\in\\{1,\dots,N^{+}_{k}\\}\;\middle|\;\lambda^{k,+}_{j}>0\right\\}.$

By construction there holds

$\displaystyle\mathcal{A}_{k+1}=\left\\{\,u^{k,+}_{j}\;\middle|\;j\in\mathcal{I}_{k}\,\right\\}\subset\mathcal{A}^{+}_{k}$

as well as

$\displaystyle
u_{k+1}=\sum_{j\in\mathcal{I}_{k}}\lambda^{k,+}_{j}u^{k,+}_{j}+\ell^{k,+}\in\operatorname{cone}(\mathcal{A}_{k+1})+\mathcal{L}$

and

$\displaystyle\min(\mathcal{P}(\mathcal{A}_{k+1}))\leq
f(u_{k+1})+\sum_{j\in\mathcal{I}_{k}}\lambda^{k,+}_{j}=f(u_{k+1})+\sum^{N^{+}_{k}}_{j=1}\lambda^{k,+}_{j}=\min(\mathcal{P}(\mathcal{A}^{+}_{k}))\leq\min(\mathcal{P}(\mathcal{A}_{k+1})).$

This finishes the proof. ∎

Finally, the iteration counter is incremented by one, i.e., $k\coloneqq k+1$
and the next iteration starts. The individual steps of the method are again
summarized in Algorithm 1. Note that we have incorporated a ”zeroth” iteration
without an extreme point insertion step to ensure that $p_{1},P_{1}\in
C_{0}(0,T)$.

Input: $\mathcal{A}_{0}=\\{u^{0}_{j}\\}^{N_{0}}_{j=1}$ in
$\operatorname{Ext}B$.

Output: Stationary point $\bar{u}$ to ($\mathcal{P}$).

1\. Compute a minimizer $(\lambda^{1},\ell^{1})$ to
$(\mathcal{P}(\mathcal{A}_{0}))$ and set  $\displaystyle
u_{1}=\sum^{N_{0}}_{j=1}\lambda^{1}_{j}u^{0}_{j}+\ell^{1},\leavevmode\nobreak\
\mathcal{A}_{1}=\mathcal{A}_{0}\setminus\left\\{\,u^{0}_{i}\;|\;\lambda^{1}_{j}=0,\leavevmode\nobreak\
j\in\\{1,\dots,N_{0}\\}\,\right\\}$

for $k=1,2,\dots$ do

2\. Compute $p_{k},P_{k}\in C_{0}(0,T)$ as in (4.3) and
$\hat{x}^{S}_{k},\leavevmode\nobreak\ \hat{x}^{K}_{k}\in(0,T)$ with
$\displaystyle|p_{k}(\hat{x}^{S}_{k})|=\|p_{k}\|_{C},\leavevmode\nobreak\
|P_{k}(\hat{x}^{K}_{k})|=\|P_{k}\|_{C}$

if $\|p_{k}\|_{C}\leq\alpha,\leavevmode\nobreak\ \|P_{k}\|_{C}\leq\beta$ then

3\. Terminate with $\bar{u}=u_{k}$ a stationary point to ($\mathcal{P}$).

else

4\. Define $\widehat{u}_{k}$ and
$\mathcal{A}^{+}_{k}=\\{u^{k,+}_{j}\\}^{N^{+}_{k}}_{j=1}$ according to (4.6)
and (4.7).

5\. Compute a minimizer $(\lambda^{k,+},\ell^{k,+})$ to
$(\mathcal{P}(\mathcal{A}^{+}_{k}))$, set  $\displaystyle
u_{k+1}=\sum^{N^{+}_{k}}_{j=1}\lambda^{k,+}_{j}u^{k,+}_{j}+\ell^{k,+},\leavevmode\nobreak\
\mathcal{A}_{k+1}=\mathcal{A}^{+}_{k}\setminus\left\\{\,u^{k,+}_{j}\;\middle|\;\lambda^{k,+}_{j}=0,\leavevmode\nobreak\
j\in\\{1,\dots,N^{+}_{k}\\}\,\right\\}$ and increment $k=k+1$.

end if

end for

Algorithm 1 Solution algorithm for ($\mathcal{P}$)

######  Remark 4.

It is worth pointing out that Algorithm 1 does not guarantee the monotonicity
of the objective functional values $\\{J(u_{k})\\}_{k}$. More in detail, by
construction, we only get $J(u_{k})\leq\min(\mathcal{P}(\mathcal{A}_{k}))$ as
well as
$\min(\mathcal{P}(\mathcal{A}_{k+1}))\leq\min(\mathcal{P}(\mathcal{A}_{k}))$
for every $k\geq 1$. This observation could serve as a motivation to consider
the alternative subproblem

$\displaystyle\min_{\lambda\in\mathbb{R}^{N}_{+},\ell\in\mathcal{L}}\left[J\left(\sum^{N}_{j=1}\lambda_{j}u_{j}+\ell\right)\right].$
($\mathcal{P}_{\text{TGV}}(\mathcal{A})$)

instead of ($\mathcal{P}(\mathcal{A})$). In general, this leads to a different
method since
$\min(\mathcal{P}_{\text{TGV}}(\mathcal{A}))<\min(\mathcal{P}(\mathcal{A}))$
in some cases. For a particular example based on the functions of Remark 3 we
refer to Appendix A. While solving
$(\mathcal{P}_{\text{TGV}}(\mathcal{A}^{+}_{k}))$ in step 5 ensures

$\displaystyle
J(u_{k+1})=\min(\mathcal{P}_{\text{TGV}}(\mathcal{A}_{k+1}))\leq\mathcal{P}_{\text{TGV}}(\mathcal{A}_{k})=J(u_{k})$

for every $k\geq 1$, it also requires tailored solution algorithms to handle
the appearing $\operatorname{TGV}$-functional. In contrast,
$(\mathcal{P}(\mathcal{A}^{+}_{k}))$ represents a smooth minimization problem
with inequality constraints which can be tackled by commonly available black-
box solvers.

###  4.2 Convergence rates

In the following, we always denote by

$\displaystyle\mathcal{A}_{k}=\\{u^{k}_{j}\\}^{N_{k}}_{j=1}\subset\operatorname{Ext}B,\leavevmode\nobreak\
u_{k}=\sum^{N_{k}}_{j=1}\lambda^{k}_{j}u^{k}_{j},\leavevmode\nobreak\
(\lambda^{k},\ell^{k})\in\operatorname*{arg\,min}(\mathcal{P}(\mathcal{A}_{k}))$

the active set and iterate generated by Algorithm 1 in iteration $k\geq 1$.
The associated dual variables $p_{k}\in H^{1}_{0}(0,T)$, $P_{k}\in
H^{2}(0,T)\cap H^{1}_{0}(0,T)$ as well as the new candidate function
$\widehat{u}_{k}$ are defined as in (4.3) and (4.6), respectively. The
following assumptions on the objective functional $j$ are made throughout this
section.

######  Assumption 1.

Assume that:

  * A1

The function $f\colon L^{2}(0,T)\to\mathbb{R}$ is continuously Fréchet
differentiable.

  * A2

The Riesz-representative $\nabla f\colon L^{2}(0,T)\to L^{2}(0,T)$ of the
derivative is Lipschitz continuous, i.e., there is $L_{f}>0$ with

$\displaystyle\|\nabla f(u_{1})-\nabla f(u_{2})\|_{L^{2}}\leq
L_{f}\|u_{1}-u_{2}\|_{L^{2}}\quad\text{for all}\leavevmode\nobreak\
u_{1},u_{2}\in L^{2}(0,T).$

  * A3

There holds $f(u)\geq-C_{f}$ for all $u\in L^{2}(0,T)$ and some $C_{f}>0$.

  * A4

The sublevel sets of $J$ are bounded in $\mathrm{BV}(0,T)$.

By standard arguments, it is readily verified that these assumptions guarantee
the existence of at least one global minimizer in Problem ($\mathcal{P}$).

######  Proposition 10.

Let Assumption 1 hold. Then Problem ($\mathcal{P}$) admits at least one
minimizer.

###### Proof.

Let $\\{u_{j}\\}_{j}$ denote an infimizing sequence for ($\mathcal{P}$), i.e.,

$\displaystyle\lim_{j\rightarrow\infty}J(u_{j})=\inf_{u\in\mathrm{BV}(0,T)}J(u)\geq-
C_{f}.$

According to Assumption 1 (A4), $\\{u_{j}\\}_{j}$ is bounded in $BV(0,T)$.
Thus, it admits at least one subsequence, denoted by the same index with
$u_{j}\rightharpoonup^{*}\bar{u}$ for some $\bar{u}\in\mathrm{BV}(0,T)$. This
implies $u_{j}\rightarrow\bar{u}$ in $L^{2}(0,T)$ due to
$\mathrm{BV}(0,T)\hookrightarrow_{c}L^{2}(0,T)$. Due to the weak lower
semicontinuity of the $\operatorname{TGV}$-functional as well as the
continuity of $f$ we finally arrive at

$\displaystyle\inf_{u\in\mathrm{BV}(0,T)}J(u)=\liminf_{j\rightarrow\infty}J(u_{j})\geq
J(\bar{u})\geq\inf_{u\in\mathrm{BV}(0,T)}J(u).$

This proves that $\bar{u}$ is a minimizer of ($\mathcal{P}$). ∎

Throughout this section we silently assume that Algorithm 1 does not converge
after finitely many iterations but generates a sequence $\\{u_{k}\\}_{k}$ in
$\mathrm{BV}(0,T)$. In order to measure the non-stationary of the iterate
$u_{k}$ consider the following constraint violation

$\displaystyle\Psi(u_{k}):=M_{0}\left(\max\left\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\right\\}-1\right)\leavevmode\nobreak\
\text{where}\leavevmode\nobreak\ M_{0}=f(0)+C_{f}.$ (4.11)

Note that we have $\Psi(u_{k})>0$, due to the termination criterion of
Algorithm 1, as well as $\operatorname{TGV}(u_{k})\leq M_{0}$ for all $k\geq
1$ since

$\displaystyle-C_{f}+\operatorname{TGV}(u_{k})\leq
J(u_{k})\leq\min(\mathcal{P}(\mathcal{A}_{k}))\leq f(0).$ (4.12)

The following proposition relates $\Psi(u_{k})$ to the “per-iteration descent”
of Algorithm 1 with respect to the residual

$\displaystyle\widehat{r}_{J}(u_{k})\coloneqq
f(u_{k})+\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-\min_{u\in\mathrm{BV}(0,T)}J(u).$
(4.13)

######  Proposition 11.

Let $\Psi(u_{k})$ and $\widehat{r}_{J}(u_{k})$ be defined as in (4.11) and
(4.13), respectively. There holds

$\displaystyle\widehat{r}_{J}(u_{k+1})-\widehat{r}_{J}(u_{k})\leq-s\Psi(u_{k})+\frac{s^{2}L_{f}}{2}\|u_{k}-\widehat{u}_{k}\|^{2}_{L^{2}}\quad\text{for
all}\leavevmode\nobreak\ s\in[0,1]$ (4.14)

for all $k\geq 1$. In particular, we have

$\displaystyle\widehat{r}_{J}(u_{k+1})-\widehat{r}_{J}(u_{k})\leq-\max\left\\{\frac{\Psi(u_{k})^{2}}{2L_{f}\|u_{k}-\widehat{u}_{k}\|^{2}_{L^{2}}},\Psi(u_{k})-\frac{L_{f}}{2}\|u_{k}-\widehat{u}_{k}\|^{2}_{L^{2}}\right\\}.$
(4.15)

and thus
$\min(\mathcal{P}(\mathcal{A}_{k+1}))<\min(\mathcal{P}(\mathcal{A}_{k}))$ for
all $k\geq 1$.

###### Proof.

For every $s\in[0,1]$ define

$\displaystyle\tilde{u}_{k,s}\coloneqq
sM_{0}\widehat{u}_{k}+(1-s)\sum^{N_{k}}_{j=1}\lambda^{k}_{j}u^{k}_{j}+\ell^{k}\in\operatorname{cone}(\mathcal{A}^{+}_{k})+\mathcal{L}.$

By construction there holds

$\displaystyle\widehat{r}_{J}(u_{k+1})-\widehat{r}_{J}(u_{k})\leq
f(\tilde{u}_{k,s})-f(u_{k})+s\left(M_{0}-\sum^{N_{k}}_{j=1}\lambda^{k}_{j}\right)$

Utilizing a Taylor’s expansion as well as the Lipschitz continuity of $\nabla
f$ we get

$\displaystyle f(\tilde{u}_{k,s})-f(u_{k})\leq-s(\nabla
f(u_{k}),u_{k}-M_{0}\widehat{u}_{k})_{L^{2}}+\frac{s^{2}L_{f}}{2}\|u_{k}-\widehat{u}_{k}\|^{2}_{L^{2}}$

as in the proof of the standard descent lemma, see [21, (1.2.5)]. Then, using
(4.4) as well as (4.8), we arrive at

$\displaystyle-s(\nabla
f(u_{k}),u_{k}-M_{0}\widehat{u}_{k})_{L^{2}}=s\left(\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-M_{0}\max\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\\}\right)$

Combining the previous observations, finally yields

$\displaystyle\widehat{r}_{J}(u_{k+1})-\widehat{r}_{J}(u_{k})\leq-s\Psi(u_{k})+\frac{s^{2}L_{f}}{2}\|u_{k}-\widehat{u}_{k}\|^{2}_{L^{2}}.$

The claim in (4.15) now follows immediately by minimizing the right-hand side
w.r.t. $s\in[0,1]$. ∎

In the following, Proposition 11 is used to show that $\Psi(u_{k})$
asymptotically vanishes. Moreover, based on the next lemma, we also conclude
that $\sum^{N_{k}}_{j=1}\lambda^{k}_{j}$ approximates
$\operatorname{TGV}(u_{k})$ for large $k$.

######  Lemma 9.

For all $k\geq 1$ we have

$\displaystyle
0\leq\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-\operatorname{TGV}(u_{k})\leq\Psi(u_{k}).$

###### Proof.

Recall that $\operatorname{TGV}(u_{k})\leq M_{0}$ for all $k\geq 1$ according
to (4.12). Hence we have

$\displaystyle(\nabla
f(u_{k}),u_{k})_{L^{2}}+\operatorname{TGV}(u_{k})-\min_{\operatorname{TGV}(v)\leq
M_{0}}\left[(\nabla f(u_{k}),v)_{L^{2}}+\operatorname{TGV}(v)\right]\geq 0$

Moreover, we readily calculate

$\displaystyle(\nabla f(u_{k}),u_{k})_{L^{2}}+\operatorname{TGV}(u_{k})$
$\displaystyle-\min_{\operatorname{TGV}(v)\leq M_{0}}\left[(\nabla
f(u_{k}),v)_{L^{2}}+\operatorname{TGV}(v)\right]$
$\displaystyle=\operatorname{TGV}(u_{k})-\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-\min_{\begin{subarray}{c}v\in
B,\\\ m\in[0,M_{0}]\end{subarray}}\left[m\big{(}(\nabla
f(u_{k}),v)_{L^{2}}+1\big{)}\right]$
$\displaystyle=\operatorname{TGV}(u_{k})-\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-\min_{m\in[0,M_{0}]}\left[m\big{(}1-\max\left\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\right\\}\big{)}\right]$
$\displaystyle=\operatorname{TGV}(u_{k})-\sum^{N_{k}}_{j=1}\lambda^{k}_{j}+M_{0}\big{(}\max\left\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\right\\}-1\big{)}$

where we use (4.5) in the first term of the left-hand side, (4.8) as well as
the positive one homogeneity of the $\operatorname{TGV}$-function in the third
and $\max\left\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\right\\}>1$ in the
final equality. Combining both statements and reordering yields the claimed
statement. ∎

######  Theorem 7.

Let $\\{u_{k}\\}_{k}$ be generated by Algorithm 1 and let Assumption 1 hold.
Then we have

$\displaystyle\lim_{k\rightarrow\infty}\Psi(u_{k})+\left|\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-\operatorname{TGV}(u_{k})\right|=0.$

###### Proof.

We only prove $\lim_{k\rightarrow\infty}\Psi(u_{k})=0$, the result on
$\operatorname{TGV}(u_{k})$ then follows from Lemma 9. We proceed similarly to
[20]. First, note that $\\{u_{k}\\}_{k}$ and $\\{\widehat{u}_{k}\\}_{k}$ are
bounded in $L^{2}(0,T)$ in virtue of $J(u_{k})\leq f(0)$ for all $k\geq 1$,
Assumption 1 (A3) and Proposition 8. Moreover we have

$\displaystyle
0\leq\sum^{\infty}_{j=1}\left[\widehat{r}_{J}(u_{k})-\widehat{r}_{J}(u_{k+1})\right]\leq\widehat{r}_{J}(u_{1})$

and thus
$\lim_{k\rightarrow\infty}\left[\widehat{r}_{J}(u_{k})-\widehat{r}_{J}(u_{k+1})\right]=0$.
Now, let $\varepsilon>0$ be arbitrary but fixed and let $C>0$ be such that
$\max\\{\|u_{k}\|_{L^{2}},M_{0}\|\widehat{u}_{k}\|_{L^{2}}\\}\leq C$, $k\geq
1$. Furthermore, choose $s_{\varepsilon}\in[0,1]$ and
$K_{\varepsilon}\in\mathbb{N}$ with

$\displaystyle
s_{\varepsilon}\leq\frac{\varepsilon}{4L_{f}C^{2}},\quad\widehat{r}_{J}(u_{k})-\widehat{r}_{J}(u_{k+1})\leq\frac{s_{\varepsilon}\varepsilon}{2}\quad\text{for
all}\leavevmode\nobreak\ k\geq K_{\varepsilon}.$

Inserting $s_{\varepsilon}$ into (4.14) we arrive at

$\displaystyle
0\leq\Psi(u_{k})\leq\frac{\widehat{r}_{J}(u_{k})-\widehat{r}_{J}(u_{k+1})}{s_{\varepsilon}}+s_{\varepsilon}2L_{f}C^{2}\leq\varepsilon\quad\text{for
all}\leavevmode\nobreak\ k\geq K_{\varepsilon}.$

Since $\varepsilon>0$ was chosen arbitrarily, we finally conclude
$\lim_{k\rightarrow\infty}\Psi(u_{k})=0$. ∎

Next we show that $\\{u_{k}\\}_{k}$ converges, on subsequences, towards
stationary points of ($\mathcal{P}$).

######  Corollary 2.

The sequence $\\{u_{k}\\}_{k}$ admits at least one weak* accumulation point in
$\mathrm{BV}(0,T)$. Every such point $\bar{u}$ satisfies $-\nabla
f(\bar{u})\in\partial_{2}\operatorname{TGV}(\bar{u})$.

###### Proof.

Since $\mathrm{BV}(0,T)$ is the topological dual of a separable Banach space
and $\\{u_{k}\\}_{k}$ is bounded in $\mathrm{BV}(0,T)$, the existence of a
weak* convergent subsequence follows from the Banach-Alaoglu theorem. Fix an
arbitrary weak* convergent subsequence, denoted by the same symbol, with limit
$\bar{u}$. Define

$\displaystyle\bar{p}=\int^{\boldsymbol{\cdot}}_{0}\nabla
f(\bar{u})(x)\leavevmode\nobreak\ \mathrm{d}x,\leavevmode\nobreak\
\bar{P}=-\int^{\boldsymbol{\cdot}}_{0}\bar{p}(x)\leavevmode\nobreak\
\mathrm{d}x.$

Since $\mathrm{BV}(0,T)\hookrightarrow_{c}L^{2}(0,T)$ there holds
$u_{k}\rightarrow\bar{u}$ in $L^{2}(0,T)$. Using this strong convergence as
well as Assumption 1 (A2) and (4.4) we get

$\displaystyle(\nabla
f(\bar{u}),\ell)_{L^{2}}=\lim_{k\rightarrow\infty}(\nabla
f(u_{k}),\ell)_{L^{2}}=0\quad\text{for all}\leavevmode\nobreak\
\ell\in\mathcal{L}.$ (4.16)

Thus, $\bar{p}\in H^{1}_{0}(0,T)$ and $\bar{P}\in H^{2}(0,T)\cap
H^{1}_{0}(0,T)$. Moreover, we immediately get

$\displaystyle p_{k}\rightarrow\bar{p},\leavevmode\nobreak\
P_{k}\rightarrow\bar{P}\quad\text{in }C_{0}(0,T)$

and

$\displaystyle
M_{0}(\max\\{\|\bar{p}\|_{C}/\alpha,\|\bar{P}\|_{C}/\beta\\}-1)=\lim_{k\rightarrow\infty}\Psi(u_{k})=0.$

In view of Lemma 4, this implies

$\displaystyle-(\nabla
f(\bar{u}),v)_{L^{2}}\leq\operatorname{TGV}(v)\quad\text{for
all}\leavevmode\nobreak\ v\in\mathrm{BV}(0,T).$ (4.17)

Finally, observe that

$\displaystyle\operatorname{TGV}(\bar{u})\leq\liminf_{k\rightarrow\infty}\operatorname{TGV}(u_{k})\leq\liminf_{k\rightarrow\infty}\sum^{N_{k}}_{j=1}\lambda^{k}_{j}$

as well as

$\displaystyle\liminf_{k\rightarrow\infty}\sum^{N_{k}}_{j=1}\lambda^{k}_{j}=\liminf_{k\rightarrow\infty}-(\nabla
f(u_{k}),u_{k})_{L^{2}}=-(\nabla
f(\bar{u}),\bar{u})_{L^{2}}\leq\operatorname{TGV}(\bar{u}).$

using the lower semicontinuity of $\operatorname{TGV}$ as well as (4.5). This
yields $-(\nabla f(\bar{u}),\bar{u})_{L^{2}}=\operatorname{TGV}(\bar{u})$.
Combining the previous observations we arrive at $-\nabla
f(\bar{u})\in\partial_{2}\operatorname{TGV}(\bar{u})$ according to Proposition
6. ∎

This section is finished by a quantitative description of the asymptotic
behavior of $\Psi(u_{k})$. More in detail, it is shown that the smallest
constraint violation encountered up to iteration $k\geq 1$ vanishes at a rate
of $1/k^{1/2}$.

######  Theorem 8.

Let $\\{u_{k}\\}_{k}$ be generated by Algorithm 1 and let Assumption 1 hold.
Moreover, let $C>0$ be such that
$\max\\{\|u_{k}\|_{L^{2}},M_{0}\|\widehat{u}_{k}\|_{L^{2}}\\}\leq C$ for all
$k\geq 1$. Then we have

$\displaystyle\min_{1\leq j\leq k}\Psi(u_{k})+\min_{1\leq j\leq
k}\left|\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-\operatorname{TGV}(u_{k})\right|\leq\sqrt{\frac{8L_{f}C^{2}\widehat{r}_{J}(u_{1})}{k}}\quad\text{
for all }k\geq 1.$

###### Proof.

Again, we only prove the result for $\Psi(u_{k})$ and point out Lemma 9.
First, invoking (4.15) we arrive at

$\displaystyle\widehat{r}_{J}(u_{k+1})-\widehat{r}_{J}(u_{k})\leq-\max\left\\{\frac{\Psi(u_{k})^{2}}{8L_{f}C^{2}},\Psi(u_{k})-2C^{2}\right\\}\leq-\frac{\min_{1\leq
j\leq k}\Psi(u_{j})^{2}}{8L_{f}C^{2}}.$ (4.18)

Summing up over $1\leq j\leq$ on both sides we get

$\displaystyle-\widehat{r}_{J}(u_{1})\leq\widehat{r}_{J}(u_{k+1})-\widehat{r}_{J}(u_{1})\leq-k\frac{\min_{1\leq
j\leq k}\Psi(u_{j})^{2}}{8L_{f}C^{2}}.$

Rearranging and taking the square root then yields the desired statement.∎

Moreover, if $f$ is convex, there holds
$J(u_{k})-\min_{u\in\mathrm{BV}(0,T)}J(u)=\mathcal{O}(1/k)$.

######  Theorem 9.

Let $\\{u_{k}\\}_{k}$ be generated by Algorithm 1, let Assumption 1 hold and
assume that $f$ is convex. Then we have

$\displaystyle
J(u_{k})-\min_{u\in\mathrm{BV}(0,T)}J(u)\leq\widehat{r}_{J}(u_{k})\leq\Psi(u_{k}).$

Moreover, let $C>0$ be such that
$\max\\{\|u_{k}\|_{L^{2}},M_{0}\|\widehat{u}_{k}\|_{L^{2}}\\}\leq C$ for all
$k\geq 1$. Then we have

$\displaystyle
J(u_{k})-\min_{u\in\mathrm{BV}(0,T)}J(u)\leq\widehat{r}_{J}(u_{k})\leq\frac{\widehat{r}_{J}(u_{1})}{1+q(k-1)}\quad\text{where}\leavevmode\nobreak\
q=\frac{\widehat{r}_{J}(u_{1})}{8L_{f}C^{2}}.$

###### Proof.

Let $\bar{u}$ denote an arbitrary minimizer to ($\mathcal{P}$). Then there
holds $\operatorname{TGV}(\bar{u})\leq M_{0}$ as well as

$\displaystyle
J(u_{k})-\min_{u\in\mathrm{BV}(0,T)}J(u)=J(u_{k})-J(\bar{u})\leq\widehat{r}_{J}(u_{k})$

By convexity of $f$ we further have

$\displaystyle\widehat{r}_{J}(u_{k})$ $\displaystyle\leq(\nabla
f(u_{k}),u_{k}-\bar{u})_{L^{2}}-\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-\operatorname{TGV}(\bar{u})=-(\nabla
f(u_{k}),\bar{u})_{L^{2}}+\operatorname{TGV}(\bar{u})$
$\displaystyle\leq-\min_{\operatorname{TGV}(u)\leq M_{0}}\left[(\nabla
f(u_{k}),u)_{L^{2}}+\operatorname{TGV}(u)\right].$

where we explicitly use (4.5). Now, invoking Proposition 8 yields

$\displaystyle-\min_{\operatorname{TGV}(u)\leq M_{0}}\left[(\nabla
f(u_{k}),u)_{L^{2}}+\operatorname{TGV}(u)\right]$
$\displaystyle=-\min_{m\in[0,M_{0}]}m\min_{v\in B}\left[(\nabla
f(u_{k}),v)_{L^{2}}+1\right]$
$\displaystyle=\max_{m\in[0,M_{0}]}\left[m(\max{\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\\}}-1)\right]$
$\displaystyle=\Psi(u_{k}).$

Thus, (4.18) can be further estimated by

$\displaystyle\frac{\widehat{r}_{J}(u_{k+1})}{\widehat{r}_{J}(u_{1})}-\frac{\widehat{r}_{J}(u_{k})}{\widehat{r}_{J}(u_{1})}\leq-\frac{\widehat{r}_{J}(u_{1})}{8L_{f}C^{2}}\left(\frac{\widehat{r}_{J}(u_{k})}{\widehat{r}_{J}(u_{1})}\right)^{2}$

The claimed convergence rate is now immediately deduced from [14, Lemma 5.1].
∎

##  5 Deconvolution from restricted Fourier measurements

The final section is devoted to illustrating the theoretical results as well
as to highlighting the practical utility of Algorithm 1. For this purpose,
recall the definition of the Fourier transform of $u\in L^{2}(0,T)$ extended
by zero to $\mathbb{R}$ as

$\displaystyle(\mathcal{F}u)(\zeta)=\int^{T}_{0}u(x)\operatorname{exp}(-i\zeta
x)\leavevmode\nobreak\ \mathrm{d}x$

for every $\zeta\in\mathbb{R}$. Given a finite number of frequencies
$\zeta_{j}\in\mathbb{R}$, $j=1,\dots,M$, our interest lies in reconstructing
an unknown piecewise affine signal $u^{\dagger}$ from measurements of the form
$m^{d}_{j}:=(\mathcal{F}u)(\zeta_{j})+\varepsilon_{j}$, $j=1,\dots,M$, where
$\varepsilon_{j}$ denotes additive noise. This problem is severely ill-posed
due to the gap between the infinite-dimensional nature of the unknown signal
and the limited availability of measurements. For example, consider $T=10$ and
the ground truth $u^{\dagger}$ depicted in Figure 1(a). Its Fourier transform
$\mathcal{F}u^{\dagger}$ is sampled at eight equidistant points in $(0,T)$,
see Figure 1(b). Then there are $\bar{a}_{j},\bar{b}_{j}\in\mathbb{R}$,
$j=1,\dots,M$, such that the function

$\displaystyle\tilde{u}(x)=\sum^{M}_{j=1}\bar{a}_{j}\cos(\zeta_{j}x)-\bar{b}_{j}\sin(\zeta_{j}x)$
(5.1)

satisfies
$(\mathcal{F}\tilde{u})(\zeta_{j})=(\mathcal{F}u^{\dagger})(\zeta_{j})$ for
all $j=1,\dots,M$. Note that $\tilde{u}$ does not share any structural
features of $u^{\dagger}$ and even has a period smaller than $T$ due to the
location of the first frequency measurement.

(a) Ground truth $u^{\dagger}$.

(b) $\mathcal{F}u^{\dagger}$ and $\zeta_{j}$.

(c) Function $\tilde{u}$ from (5.1).

Figure 1: Inverse problem setup.

In order to preserve the piecewise affine linear structure of $u^{\dagger}$ in
the reconstruction and to alleviate the ill-posedness of this inversion, we
thus propose to consider the $\operatorname{TGV}$-regularized problem

$\displaystyle\min_{u\in\mathrm{BV}(0,T)}J(u)\coloneqq\left[\frac{1}{2}\sum^{M}_{j=1}|(\mathcal{F}u)(\zeta_{j})-m^{d}_{j}|^{2}_{\mathbb{C}}+\operatorname{TGV}(u)\right].$
(P)

For abbreviation, define

$\displaystyle F\colon\mathbb{C}^{M}\to\mathbb{R},\leavevmode\nobreak\
F(m)=\frac{1}{2}\sum^{M}_{j=1}|m_{j}-m^{d}_{j}|^{2}_{\mathbb{C}},$

as well as the linear and continuous observation operator

$\displaystyle H\colon L^{2}(0,T)\to\mathbb{C}^{M},\quad
Hu=\left((\mathcal{F}u)(\zeta_{1}),\dots,(\mathcal{F}u)(\zeta_{M})\right)^{\top}.$
(5.2)

The following proposition addresses the existence of sparse minimizers to (P).

######  Proposition 12.

Let $H_{|\mathcal{L}}$ be injective. Then $f=F\circ H$ satisfies Assumption 1
and (P) admits a minimizer $\bar{u}$ of the form (3.1) with $N_{K}+N_{S}\leq
2M-2$. Moreover, the optimal observation is unique, i.e., for two solutions
$\bar{u}_{1},\leavevmode\nobreak\ \bar{u}_{2}$ to (P) we have
$H\bar{u}_{1}=H\bar{u}_{2}$.

###### Proof.

Assumptions 1 (A1)-(A3) can be verified by direct calculations. In order to
show (A4), let $B>0$ and $u\in\mathrm{BV}(0,T)$ with $J(u)\leq B$ be arbitrary
but fixed. Then there holds

$\displaystyle\max\left\\{\big{|}Hu-m^{d}\big{|}_{\mathbb{C}^{M}},\operatorname{TGV}(u)\right\\}\leq
C_{B}$

for some $C_{B}>0$ depending on $B$ but not on $u$. In the following $c>0$
denotes a generic constant which is independent of $u$. We start by estimating

$\displaystyle\|u\|_{\mathrm{BV}}\leq
c\big{(}\|u\|_{L^{1}}+\operatorname{TGV}(u)\big{)}\leq
c\big{(}\|u\|_{L^{2}}+\operatorname{TGV}(u)\big{)}\leq
c\big{(}\|u\|_{L^{2}}+C_{B}\big{)}.$

Denoting by $\mathcal{L}^{\top}$ the orthogonal complement of $\mathcal{L}$ in
$L^{2}(0,T)$ and by $P_{\mathcal{L}},\leavevmode\nobreak\
P_{\mathcal{L}^{\top}}$, the respective orthogonal projections, we have

$\displaystyle\|u\|_{L^{2}}=\|P_{\mathcal{L}}u\|_{L^{2}}+\|P_{\mathcal{L}^{\top}}u\|_{L^{2}},\leavevmode\nobreak\
\|P_{\mathcal{L}^{\top}}u\|_{L^{2}}=\|u+\mathcal{L}\|_{L^{2}/\mathcal{L}}.$

Now, estimating as in the proof of Proposition 1 and utilizing the continuous
embedding $\mathrm{BV}(0,T)\hookrightarrow L^{2}(0,T)$, there holds

$\displaystyle\|P_{\mathcal{L}^{\top}}u\|_{L^{2}}=\|u+\mathcal{L}\|_{L^{2}/\mathcal{L}}\leq
c\|u+\mathcal{L}\|_{\mathrm{BV}/\mathcal{L}}\leq c\operatorname{TGV}(u)\leq
c\,C_{B}.$

Moreover, using the injectivity of $H$ on $\mathcal{L}$, we get

$\displaystyle\|P_{\mathcal{L}}u\|_{L^{2}}$ $\displaystyle\leq
c\left(|HP_{\mathcal{L}}u|_{\mathbb{C}^{M}}\right)\leq
c\left(|HP_{\mathcal{L}^{\top}}u|_{\mathbb{C}^{M}}+|Hu-m^{d}|_{\mathbb{C}^{M}}+|m^{d}|_{\mathbb{C}^{M}}\right)$
$\displaystyle\leq
c\left(\operatorname{TGV}(u)+|Hu-m^{d}|_{\mathbb{C}^{M}}+|m^{d}|_{\mathbb{C}^{M}}\right)$
$\displaystyle\leq c\left(2C_{B}+|m^{d}|_{\mathbb{C}^{M}}\right).$

Hence, combining both estimates, we conclude that the sublevel set
$\\{\,u\in\mathrm{BV}(0,T)\;|\;J(u)\leq B\,\\}$ is bounded. Since $B>0$ was
chosen arbitrary, Assumption 1 (A4) follows. Thus, according to Proposition
10, Problem (P) admits at least one minimizer. Invoking Theorem 6 then yields
the existence of minimizer of the form (3.1) with $N_{k}+N_{S}\leq 2M-2$ since
$\mathbb{C}^{M}\simeq\mathbb{R}^{2M}$ and
$\operatorname{dim}(H(\mathcal{L}))=2$. The uniqueness of the optimal
observation follows immediately from the strict convexity of $F$. ∎

In the following, the optimal observation is denoted by $\bar{m}$. While
Proposition 12 ensures the existence of at least one minimizer in the form
(3.1), Corollary 1 implies that all solutions to (P) are sparse if the optimal
misfit is nonzero.

######  Corollary 3.

Assume that $\bar{m}\neq m^{d}$. Then every solution to (P) is of the form
(3.1).

###### Proof.

Let $\bar{u}$ be an arbitrary minimizer to (P) and let $\bar{m}$ denote the
unique optimal observation. We readily verify that $\nabla f(\bar{u})$, and
thus also $\bar{p}$ and $\bar{P}$, (3.15), are analytic on $(0,T)$ due to

$\displaystyle\nabla
f(\bar{u})(x)=\sum^{M}_{j=1}\operatorname{Re}(\bar{m}_{j}-m^{d}_{j})\cos(\zeta_{j}x)-\sum^{M}_{j=1}\operatorname{Im}(\bar{m}_{j}-m^{d}_{j})\sin(\zeta_{j}x).$

Moreover there holds $\nabla f(\bar{u})\neq 0$ since the functions
$\cos(\zeta_{j}x),\leavevmode\nobreak\ \sin(\zeta_{j}x)$, $j=1,\dots,M$, are
linearly independent and $\bar{m}-m^{d}\neq 0$. The claimed statement now
follows immediately from Corollary 1. ∎

In order to illustrate the advantages of solving Problem (P), we return to the
setup described in Figure 1, i.e., we set

$\displaystyle u^{\dagger}$
$\displaystyle=-4.5K_{2}+5S_{6.3}-8.2K_{7.8}-8.3S_{9.1}+3x+2$
$\displaystyle=\bar{\mu}_{1}K_{2}+\bar{\mu}_{2}S_{6.3}+\bar{\mu}_{3}K_{7.8}+\bar{\mu}_{4}S_{9.1}+3x+2,$

see Figure 1(a), and choose $T=10$ as well as $\zeta_{j}=j\cdot(10/9)$,
$j=1,\dots,8$, as depicted in Figure 1(b). Subsequently, a measurement vector
$m^{d}\in\mathbb{C}^{8}$ is generated by setting
$m^{d}=Hu^{\dagger}+\varepsilon$ where $\varepsilon\in\mathbb{C}^{8}$ is a
noise vector with
$\|\varepsilon\|_{\mathbb{C}^{8}}/\|Hu^{\dagger}\|_{\mathbb{C}^{8}}=0.1$. The
regularization parameters are chosen empirically as $\alpha=2.205$ and
$\beta=2.5344$. By direct computation, it is readily verified that $H$ is
injective on $\mathcal{L}$ in this case. Hence, Problem (P) admits a solution
which can be computed using Algorithm 1.

###  5.1 Practical realization of Algorithm 1

Let us briefly discuss the practical realization of Algorithm 1 without
discretizing the interval. For this purpose, we point out that $HK_{x}$,
$HS_{x}$ and $H\ell$ admit a closed-form representation for every $x\in(0,T)$,
$\ell\in\mathcal{L}$. Hence, given the k-th iterate
$u_{k}\in\operatorname{cone}(\mathcal{A}_{k})+\mathcal{L}$, the measurements
$Hu_{k}$, the corresponding derivative

$\displaystyle\nabla
f(u_{k})(x)=\sum^{M}_{j=1}\operatorname{Re}\big{(}(Hu_{k})_{j}-m^{d}_{j}\big{)}\cos(\zeta_{j}x)-\sum^{M}_{j=1}\operatorname{Im}\big{(}(Hu_{k})_{j}-m^{d}_{j}\big{)}\sin(\zeta_{j}x).$

as well as dual variables $p_{k},P_{k}$, see (4.3), can be computed without
numerical approximation. Every iteration of Algorithm 1 then requires the
solution of two subproblems. First, we have to determine global extrema of
$p_{k}$ and $P_{k}$ in step 3. This is done by computing solutions of
$p^{\prime}_{k}(x)=0$ and $P^{\prime}_{k}(x)=0$ using a Newton method starting
at equally spaced points $x^{j}_{0}=j\cdot 0.1$, $j=1,\dots,99$. Then
$\hat{x}^{S}_{k},\leavevmode\nobreak\ \hat{x}^{K}_{k}\in(0,T)$ are chosen from
the set of computed solutions by comparing the corresponding function values.
Second, step 1 and 6, require the solution of the finite dimensional convex
Problem $(\mathcal{P}(\mathcal{A}^{+}_{k}))$. For this, we rely on a
semismooth Newton method for the ”normal map” reformulation of its first order
sufficient optimality conditions. In each iteration the method is warmstarted
using the current iterate to construct a good starting point. Moreover we
further enhance its practical performance by incorporating a heuristic
globalization strategy based on damped Newton steps. The method is run for a
maximum of $100$ iterations or until the constraint violation

$\displaystyle\Psi(u_{k})=\frac{\|m^{d}\|^{2}_{\mathbb{C}^{8}}}{2}\big{(}\max\left\\{\|p_{k}\|_{C}/\alpha,\|P_{k}\|_{C}/\beta\right\\}-1\big{)}$

satisfies $\Psi(u_{\bar{k}})\leq 10^{-10}$ for some $\bar{k}\leq 100$. Note
that, since (P) is convex, we also have

$\displaystyle
J(u_{\bar{k}})-\min_{u\in\mathrm{BV}(0,T)}J(u)\leq\widehat{r}_{J}(u_{\bar{k}})\leq\Psi(u_{\bar{k}})\leq
10^{-10}$

in virtue of Theorem 9. All of the following computations were carried out on
Matlab 2019 on a notebook with $32$ GB RAM and an Intel®Core™ i7-10870H
<EMAIL_ADDRESS>GHz.

###  5.2 Qualitative features of the reconstruction

Starting from $\mathcal{A}_{0}=\\{S_{7.5}\\}$ and $u_{0}=S_{7.5}$, the method
stops after $\bar{k}=50$ iterations since $\Psi(u_{\bar{k}})\leq 10^{-10}$. In
Figure 2(a) we plot the computed function $\bar{u}=u_{\bar{k}}$ alongside the
ground truth $u^{\dagger}$. We point out that $\bar{u}$ is piecewise affine
linear and its kinks and jumps closely approximate those of $u^{\dagger}$. At
a first glance, it seems that both $\bar{u}$ and $u^{\dagger}$ share the same
number of jumps/kinks. Upon a closer inspection, though, we observe that the
kink at approximately $7.8$ is approximated by two kinks of equal sign in
$\bar{u}$. We assume that this “clustering” behavior is a consequence of
numerical rounding errors since the positions of both jumps/kinks only differ
by a magnitude of order $10^{-7}$. Moreover, replacing both jumps/kinks by a
single one of the combined magnitude at either of both candidate locations
only introduces a relative error of $10^{-16}$ in the objective functional
value. In any case, the combined number of kinks and jumps in $\bar{u}$ is
considerably smaller than the theoretical upper bound of $2M-2=14$ predicted
by Proposition 12. Next, the reconstruction of the coefficients is
investigated. For a better visualization, we plot a Dirac delta with weight
$\bar{\mu}_{j}$, $j=1,\dots,4$, at the position of the corresponding kink/jump
(dashed lines for kinks, solid line for jumps) in Figure 2(b). The recovered
function is treated analogously with the exception of merging the
aforementioned clustering kinks into one of combined magnitude.

(a) Ground truth $u^{\dagger}$ and reconstruction $\bar{u}$.

(b) Reference (blue) and computed (orange) coefficients.

Figure 2: Ground truth vs. reconstructions

Observe that by solving (P) we successfully reconstruct the sign of every
$\bar{\mu}_{j}$ and provide decent estimates of its magnitude (after
clustering). We also point out that, with the exception of the leftmost kink,
the recovered coefficient is smaller than the reference. A possible
explanation of this behavior can be found in Theorem 5 which states that the
absolute values of the recovered coefficients are given by the solution to a
minimization problem with an $\ell_{1}$-type regularization term. For this
type of problem, underestimation bias is a well-established phenomenon.

###  5.3 Optimality conditions and performance of Algorithm 1

We take the opportunity and verify the structural properties of $\bar{u}$
derived in Theorem 5. For this purpose, the dual variables $\bar{p}$ and
$\bar{P}$ are plotted in Figures 3(a) and 3(b). Function values that
correspond to the positions of jumps in $\bar{u}$ are marked by orange dots in
Figure 3(a). The same is done for function values corresponding to jumps in
Figure 3(b).

(a) First primitive $\bar{p}$.

(b) Second primitive $\bar{P}$.

Figure 3: Dual variables.

First, note that $\bar{u}$ is nonzero. Hence, Theorem 4 implies that
$\|\bar{p}\|_{C}=\alpha$, $\|\bar{P}\|_{C}=\beta$. This is readily verified
from the plots. Furthermore, the set of global extremas for each function
consists of finitely many points. Consequently, the positions of jumps and
kinks of $\bar{u}$ align with minimizers/maximizers of $\bar{p}$ and
$\bar{P}$, respectively, as predicted by Theorem 5. Moreover the sign of the
recovered coefficients for every jump/kink coincides with $\bar{p}/\alpha$ and
$\bar{P}/\beta$, respectively, as expected.

(a) $\widehat{r}_{J}(u_{k})/\Psi(u_{k})$ vs. $k$.

(b) $\\#\mathcal{A}_{k}$ vs. $k$.

Figure 4: Evolution of relevant quantities.

Finally, we plot the convergence of the constraint violation $\Psi(u_{k})$ as
well as of the residual

$\displaystyle\widehat{r}_{J}(u_{k})=f(u_{k})+\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-\min_{u\in\mathrm{BV}(0,T)}J(u)\approx
f(u_{k})+\sum^{N_{k}}_{j=1}\lambda^{k}_{j}-f(u_{\bar{k}})+\sum^{N_{\bar{k}}}_{j=1}\lambda^{\bar{k}}_{j}.$

This approximation is justified by $\widehat{r}_{J}(u_{\bar{k}})\leq
10^{-10}$. The resulting graphs can be found in Figure 4(a). Clearly, these
computations suggest a linear rate of convergence for both quantities which is
vastly better than the $\mathcal{O}(1/k^{1/2})$ and $\mathcal{O}(1/k)$
behavior predicted by Theorem 8 and 9, respectively. Alongside, in Figure
4(b), we plot the evolution of the active set size. Most remarkably,
$\\#\mathcal{A}_{k}$ does not exceed $8$ throughout the iterations. This
highlights the importance of the point removal step in Algorithm 1. Moreover,
keeping $\\#\mathcal{A}_{k}$ small in combination with a warm-started
semismooth Newton method leads to a fast resolution of the subproblems
$(\mathcal{P}(\mathcal{A}^{+}_{k}))$. In fact, the overall computation time of
Algorithm 1 for the present example is merely $4.5$ s. In summary, these
observations show the practical efficiency of methods in the spirit of
Algorithm 1 for TGV-regularization. Of course, they also spark the demand of
further research concerning e.g. an improved quantitative convergence analysis
of Algorithm 1. However, since the focus of the present manuscript lies on the
characterization of the extremal points and immediate consequences thereof,
thorough investigations are postponed to a follow-up work.

##  Appendix A A counterexample

In this appendix we finally give the counterexample announced in Remark 4.
More in detail, a set $\mathcal{A}=\\{u_{j}\\}^{N}_{j=1}$ in
$\operatorname{Ext}B$ as well as a convex and smooth function $f\colon
L^{2}(0,T)\to\mathbb{R}$ with
$\min\eqref{eq:altsubprob}<\min\eqref{def:subprob}$ are constructed. For this
purpose, choose $T=10$ and $\alpha,\beta>0$ with $\beta/\alpha=1/2$. Moreover
set $\bar{x}_{1}=6$, $\bar{x}_{2}=6.25$ and fix
$\bar{\lambda}_{1},\bar{\lambda}_{2}>0$ such that

$\displaystyle|\bar{\lambda}_{2}-\bar{\lambda}_{1}|<0.25,\leavevmode\nobreak\
3.75<\bar{\lambda}_{1}+\bar{\lambda}_{2}.$

Under this prerequisites, the function
$\bar{u}=\bar{\lambda}_{1}u_{1}+\bar{\lambda}_{2}u_{2}$ with
$u_{1}=K_{\bar{x}_{1}}/\beta$ and $u_{2}=-K_{\bar{x}_{2}}/\beta$ satisfies
$\operatorname{TGV}(\bar{u})<\bar{\lambda}_{1}+\bar{\lambda}_{2}$, see Remark
3. The following proposition provides an outline for the construction of a
counterexample.

######  Proposition 13.

Assume that there is $\bar{\varphi}\in L^{2}(0,T)$ such that

$\displaystyle(u_{j},\bar{\varphi})_{L^{2}}+1=0\quad\text{for
all}\leavevmode\nobreak\ j=1,2,\leavevmode\nobreak\
(\ell,\bar{\varphi})_{L^{2}}=0\quad\text{for all}\leavevmode\nobreak\
\ell\in\mathcal{L}.$ (A.1)

Then
$(\bar{\lambda}_{1},\bar{\lambda}_{2},0)\in\mathbb{R}^{2}_{+}\times\mathcal{L}$
is a minimizer of

$\displaystyle\min_{\lambda\in\mathbb{R}^{2}_{+},\ell\in\mathcal{L}}\left[\frac{1}{2}\int^{10}_{0}\Big{|}\sum^{2}_{j=1}\lambda_{j}u_{j}(x)-u_{d}(x)\Big{|}^{2}\leavevmode\nobreak\
\mathrm{d}x+\sum^{2}_{j=1}\lambda_{j}\right]$ ($\mathfrak{P}$)

for $u_{d}=\bar{u}-\bar{\varphi}$.

###### Proof.

First, note that the objective functional of ($\mathfrak{P}$) is convex in
$(\lambda_{1},\lambda_{2},\ell)$. Calculating its partial derivatives at
$(\bar{\lambda}_{1},\bar{\lambda}_{2},0)$ reveals

$\displaystyle(u_{j},\bar{u}-u_{d})_{L^{2}}+1=(u_{j},\bar{\varphi})_{L^{2}}+1=0\quad\text{for
all}\leavevmode\nobreak\ j=1,2$

as well as

$\displaystyle(\ell,\bar{u}-f)_{L^{2}}=(\ell,\bar{\varphi})_{L^{2}}=0\quad\text{for
all}\leavevmode\nobreak\ \ell\in\mathcal{L}.$ (A.2)

Consequently, $(\bar{\lambda}_{1},\bar{\lambda}_{2},0)$ is a stationary point
of ($\mathfrak{P}$) and thus a minimizer. ∎

In particular, if $\bar{\varphi}$ exists we have

$\displaystyle\min_{\lambda\in\mathbb{R}^{2}_{+},\ell\in\mathcal{L}}\left[\frac{1}{2}\int^{10}_{0}\Big{|}\sum^{2}_{j=1}\lambda_{j}u_{j}(x)-u_{d}(x)\Big{|}^{2}\leavevmode\nobreak\
\mathrm{d}x+\operatorname{TGV}\left(\sum^{2}_{j=1}\lambda_{j}u_{j}\right)\right]<\min\eqref{probcounter}$

due to $\operatorname{TGV}(\bar{u})<\bar{\lambda}_{1}+\bar{\lambda}_{2}$. In
order to construct such a function, define

$\displaystyle w_{1}(x)=\begin{cases}1&\bar{x}_{1}\leq x\leq\bar{x}_{2}\\\
0&\text{else}\end{cases},\leavevmode\nobreak\
w_{2}(x)=\begin{cases}1-\frac{3}{8}K_{\bar{x}_{1}}(x)&\bar{x}_{1}\leq
x\leq\bar{x}_{2}\\\ 0&\text{else}\end{cases},\leavevmode\nobreak\
\ell_{1}(x)=1,\leavevmode\nobreak\ \ell_{2}(x)=x-5.$

Note that

$\displaystyle(u_{1},w_{1})_{L^{2}}\neq 0,\leavevmode\nobreak\
(u_{1},w_{2})_{L^{2}}=0,\leavevmode\nobreak\ (u_{2},w_{2})_{L^{2}}\neq
0,\leavevmode\nobreak\ (u_{2},w_{1})_{L^{2}}=0$

as well as

$\displaystyle(\ell_{1},\ell_{2})_{L^{2}}=0,\leavevmode\nobreak\
\operatorname{span}\\{\ell_{1},\ell_{2}\\}=\mathcal{L}.$

Now, make the ansatz

$\displaystyle\varphi(\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4})\coloneqq\gamma_{1}w_{1}+\gamma_{2}w_{2}+\gamma_{3}\ell_{1}+\gamma_{4}\ell_{4}.$
(A.3)

The following proposition yields the desired counterexample.

######  Proposition 14.

There is
$(\bar{\gamma}_{1},\bar{\gamma}_{2},\bar{\gamma}_{3},\bar{\gamma}_{4})$ such
that
$\bar{\varphi}\coloneqq\varphi(\bar{\gamma}_{1},\bar{\gamma}_{2},\bar{\gamma}_{3},\bar{\gamma}_{4})$
satisfies (A.1).

###### Proof.

Inserting the ansatz (A.3) into (A.1) yields the linear system

$\displaystyle\begin{pmatrix}(u_{1},w_{1})_{L^{2}}&0&(u_{1},\ell_{1})_{L^{2}}&(u_{1},\ell_{2})_{L^{2}}\\\
0&(u_{2},w_{2})_{L^{2}}&(u_{2},\ell_{1})_{L^{2}}&(u_{2},\ell_{2})_{L^{2}}\\\
(\ell_{1},w_{1})_{L^{2}}&(\ell_{1},w_{2})_{L^{2}}&(\ell_{1},\ell_{1})_{L^{2}}&0\\\
(\ell_{2},w_{1})_{L^{2}}&(\ell_{2},w_{2})_{L^{2}}&0&(\ell_{2},\ell_{2})_{L^{2}}\end{pmatrix}\begin{pmatrix}\gamma_{1}\\\
\gamma_{2}\\\ \gamma_{3}\\\ \gamma_{4}\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\
0\\\ 0\end{pmatrix}$

Explicitly calculating the entries of this matrix reveals its invertibility
and thus the existence of a solution
$(\bar{\gamma}_{1},\bar{\gamma}_{2},\bar{\gamma}_{3},\bar{\gamma}_{4})$. The
statement follows. ∎

## Acknowledgments

We wish to thank Kristian Bredies for very interesting discussions and
suggestions regarding the content of this work. The work of J.A.I. was
partially supported by the State of Upper Austria.

## References

  * [1] L. Ambrosio, N. Fusco, and D. Pallara.  Functions of bounded variation and free discontinuity problems.  Oxford Mathematical Monographs. Oxford University Press, New York, 2000\.
  * [2] C. Boyer, A. Chambolle, Y. De Castro, V. Duval, F. De Gournay, and P. Weiss.  On representer theorems and convex regularization.  SIAM J. Optim., 29(2):1260–1281, 2019.
  * [3] K. Bredies and M. Carioni.  Sparsity of solutions for variational inverse problems with finite-dimensional data.  Calc. Var. Partial Differential Equations, 59(1):14, 2020.
  * [4] K. Bredies, M. Carioni, S. Fanzon, and D. Walter.  Linear convergence of accelerated generalized conditional gradient methods.  Preprint arXiv:2110.06756 [math.OC], 2021.
  * [5] K. Bredies and M. Holler.  Regularization of linear inverse problems with total generalized variation.  J. Inverse Ill-Posed Probl., 22(6):871–913, 2014.
  * [6] K. Bredies and M. Holler.  Higher-order total variation approaches and generalisations.  Inverse Probl., 36(12):123001, 128, 2020.
  * [7] K. Bredies, K. Kunisch, and T. Pock.  Total generalized variation.  SIAM J. Imaging Sci., 3(3):492–526, 2010.
  * [8] K. Bredies, K. Kunisch, and T. Valkonen.  Properties of $L^{1}$-${\rm TGV}^{2}$: the one-dimensional case.  J. Math. Anal. Appl., 398(1):438–454, 2013.
  * [9] K. Bredies and T. Valkonen.  Inverse problems with second-order total generalized variation constraints.  In Proceedings of the 9th International Conference on Sampling Theory and Applications (SampTA), Singapore, 2011.  arXiv:2005.09725.
  * [10] E. Casas, C. Clason, and K. Kunisch.  Parabolic control problems in measure spaces with sparse solutions.  SIAM J. Control Optim., 51(1):28–63, 2013.
  * [11] A. Chambolle and T. Pock.  A first-order primal-dual algorithm for convex problems with applications to imaging.  J. Math. Imaging Vision, 40(1):120–145, 2011.
  * [12] J. C. De los Reyes and E. Loayza-Romero.  Total generalized variation regularization in data assimilation for Burgers’ equation.  Inverse Probl. Imaging, 13(4):755–786, 2019.
  * [13] Y. Dong, T. Görner, and S. Kunis.  An algorithm for total variation regularized photoacoustic imaging.  Adv. Comput. Math., 41(2):423–438, 2015.
  * [14] J. C. Dunn.  Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals.  SIAM J. Control Optim., 17(2):187–211, 1979.
  * [15] V. Duval, J.-F. Aujol, and Y. Gousseau.  The TVL1 model: a geometric point of view.  Multiscale Model. Simul., 8(1):154–189, 2009.
  * [16] M. Fabian, P. Habala, P. Hájek, V. Montesinos Santalucía, J. Pelant, and V. Zizler.  Functional analysis and infinite-dimensional geometry, volume 8 of CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC.  Springer-Verlag, New York, 2001.
  * [17] M. Freiberger, C. Clason, and M. Scharfetter.  Total variation regularization for nonlinear fluorescence tomography with an augmented lagrangian splitting approach.  Appl. Opt., 49(19):3741–3747, 2010.
  * [18] D. Kitahara, L. Condat, and A. Hirabayashi.  One-dimensional edge-preserving spline smoothing for estimation of piecewise smooth functions.  In ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5611–5615, 2019.
  * [19] H. Kuroda, M. Yamagishi, and I. Yamada.  Exploiting sparsity in tight-dimensional spaces for piecewise continuous signal recovery.  IEEE Trans. Signal Process., 66(24):6363–6376, 2018.
  * [20] S. Lacoste-Julien.  Convergence rate of Frank-Wolfe for non-convex objectives.  Preprint arXiv:1607.00345 [math.OC], 2016.
  * [21] Y. Nesterov.  Introductory lectures on convex optimization, volume 87 of Applied Optimization.  Kluwer Academic Publishers, Boston, MA, 2004.
  * [22] G. Ongie and M. Jacob.  Recovery of discontinuous signals using group sparse higher degree total variation.  IEEE Signal Process. Lett., 22(9):1414–1418, 2015.
  * [23] K. Papafitsoros and K. Bredies.  A study of the one dimensional total generalised variation regularisation problem.  Inverse Probl. Imaging, 9(2):511–550, 2015.
  * [24] K. Papafitsoros and T. Valkonen.  Asymptotic behaviour of total generalised variation.  In Scale space and variational methods in computer vision, volume 9087 of Lecture Notes in Comput. Sci., pages 720–714. Springer, 2015\.
  * [25] C. Pöschl and O. Scherzer.  Exact solutions of one-dimensional total generalized variation.  Commun. Math. Sci., 13(1):171–202, 2015.
  * [26] L. I. Rudin, S. Osher, and E. Fatemi.  Nonlinear total variation based noise removal algorithms.  Phys. D, 60(1-4):259–268, 1992.
  * [27] I. W. Selesnick.  Generalized total variation: Tying the knots.  IEEE Signal Process. Lett., 22(11):2009–2013, 2015.
  * [28] T. Valkonen.  The jump set under geometric regularisation. Part 2: Higher-order approaches.  J. Math. Anal. Appl., 453(2):1044–1085, 2017.