BREGMAN ITERATIONS FOR `
1
-MINIMIZATION
5
26, 51]. In [25] Darbon and Osher also study an algorithm obtained by replacing μT V (u) in (2.7) by its
Bregman distance (see Subsection 2.2 below) and proved that if H(u) = 0.5kAu − fk
2
then {u
k
} converges
to the solution of min
u
{T V (u) : Au = f}. Their algorithm and results are described in Section 5.3. In the
next subsection, we give an introduction to Bregman iterative regularization.
2.2. Bregman Iterative Regularization. Bregman iterative regularization was introduced by Osher,
Burger, Goldfarb, Xu, and Yin [71] in the context of image processing; it was then extended to wavelet-based
denoising [93], nonlinear inverse scale space in [10, 11], and compressed sensing in MR imaging [57]. The
authors of [71] extend the Rudin-Osher-Fatemi [79] model
(2.8) min
u
μ
Z
|∇u| +
1
2
ku −bk
2
where u is an unknown image, b is typically an input noisy measurement of a clean image ˉu, and μ is a
tuning parameter, into an iterative regularization model by using the Bregman distance (2.10) below based
on the total variation functional:
(2.9) J(u) = μ T V (u) = μ
Z
|∇u|.
Specifically, the Bregman distance [9] based on a convex functional J(∙) between points u and v is defined as
(2.10) D
p
J
(u, v) = J(u) − J(v) −hp, u −vi
where p ∈ ∂J(v) is some subgradient in the subdifferential of J at the point v. Because D
p
J
(u, v) 6= D
p
J
(v, u)
in general, D
p
J
(u, v) is not a distance in the usual sense. However, it measures the closeness between u and
v in the sense that D
p
J
(u, v) ≥ 0 and D
p
J
(u, v) ≥ D
p
J
(w, v) for all points w on the line segment connecting u
and v.
Instead of solving (2.8) once, the Bregman iterative regularization procedure of Osher et. al. [71] solves
a sequence of convex problems
(2.11) u
k+1
← min
u
D
p
k
J
(u, u
k
) +
1
2
ku −bk
2
for k = 0, 1, . . . starting with u
0
= 0 and p
0
= 0 (hence, for k = 0, one solves the original problem (2.8).)
Since μTV (u) is not differentiable everywhere, the subdifferential of μT V (u) may contain more than one
element. However, from the optimality of u
k+1
in (2.11), it follows that 0 ∈ ∂J(u
k+1
) −p
k
+ u
k+1
−b; hence,
they set
p
k+1
:= p
k
+ b − u
k+1
,
The difference between (2.8) and (2.11) is in the use of regularization. While (2.8) regularizes u by directly
minimizing its total variation, (2.11) does the same by minimizing the total variation-based Bregman distance
of u to a previous solution u
k
.
In [71] two key results for the sequence {u
k
} generated by (2.11) were proved. First, ku
k
−bk converges
to 0 monotonically; second, u
k
also monotonically gets closer to ˉu, the unknown noiseless image, in terms of
the Bregman distance D
p
k
T V
(ˉu, u
k
), at least while ku
k
−bk ≥ kˉu − bk. Numerical results in [71] demonstrate
that for μ sufficiently large, this simple iterative procedure remarkably improves denoising quality over the