L1正则化问题的分裂Bregman方法.pdf_分裂Bregman学习笔记资源-CSDN文库

需积分: 48 131 浏览量 2019-12-27 15:06:53 上传评论 1 收藏 1.64MB PDF 举报

Bregman迭代算法是一种用于求解优化问题的方法，尤其是在图像处理领域中具有重要意义。其核心思想是通过将复杂的优化问题转换为一系列简单子问题的迭代求解，以提高求解效率和稳定性。下面详细介绍与Bregman迭代算法以及L1正则化相关的一些核心知识点。 L1正则化是指在目标函数中引入L1范数作为正则项。L1范数是指向量元素绝对值的和。在优化问题中，L1正则化有两大作用：一是通过惩罚系数的绝对值，强制使得部分系数为零，从而起到特征选择的作用，这在处理稀疏数据或进行特征提取时尤为有用；二是增强模型的鲁棒性，因为L1范数对大的系数同样具有惩罚效果，这有助于减少模型对噪声的敏感度。关于Bregman迭代算法，它是一种针对凸优化问题的迭代求解技术。该方法的核心思想是引入Bregman距离来度量迭代过程中解的变化。Bregman距离不是真正的距离（因为它可能不满足对称性和三角不等式），但它能够提供优化迭代过程中的额外信息，特别是在处理带约束的优化问题时。通过最小化由凸函数生成的Bregman距离，Bregman迭代可以被用来迭代求解多种凸优化问题。在上述提到的“Split Bregman”方法中，通过将复杂的L1正则化问题分解为多个简单子问题来迭代求解。例如，在图像去噪领域中，Rudin-Osher-Fatemi（ROF）模型常用于图像恢复。该模型是一个典型的L1正则化问题，它将图像去噪转化为一个带约束的最优化问题。Split Bregman方法通过将这个问题分解为一系列简单的子问题来求解，这包括一个关于图像的总变分最小化问题以及一个关于数据保真度的二次最小化问题。这样，原本复杂的优化问题就可以通过迭代的方式有效地解决。压缩感知是另一种利用L1正则化的优势来处理信号和图像的方法。压缩感知理论指出，如果一个信号是稀疏的，那么可以利用远少于Nyquist采样定理所要求的采样点数来恢复出原信号。这一理论在医学成像领域尤其重要，例如磁共振成像（MRI）中的快速成像技术。在这些应用中，Bregman迭代算法可以应用于求解由压缩感知理论所引导出的L1正则化问题，帮助从较少的数据中重构出高质量的图像。在理解和应用Bregman迭代算法和L1正则化问题时，有几个关键技术点需要掌握： 1. 凸优化理论：理解什么是凸集、凸函数以及凸优化问题，这是掌握Bregman迭代算法的基础。 2. Bregman距离：了解Bregman距离的定义及其性质，它是Bregman迭代算法中连接迭代子问题的桥梁。 3. 分裂技术：理解如何将复杂的优化问题分解为易于处理的子问题，并能正确地使用分裂技术。 4. 算法实现：掌握如何将Bregman迭代算法应用于具体的优化问题中，并能够使用适当的数值方法实现算法。 5. 应用领域：了解Bregman迭代算法在图像处理、信号处理、压缩感知等多个领域的应用，并能分析其在这些领域中的优势和局限性。 Bregman迭代算法与L1正则化在图像处理、信号处理等领域具有广阔的应用前景。通过不断的研究与实践，人们正逐步加深对这些算法的理解，并将它们广泛应用于解决实际问题。

资源推荐

资源详情

资源评论

SIAM J. I

MAGING

CIENCES



2009 Society for Industrial and Applied Mathematics

Vol. 2, No. 2, pp. 323–343

The Split Bregman Method for L1-Regularized Problems

∗

Tom Goldstein

†

and

Stanley Osher

†

Abstract. The class of L1-regularized optimization problems has received much attention recently because of

the introduction of “compressed sensing,” which allows images and signals to be reconstructed from

small amounts of data. Despite this recent attention, many L1-regularized problems still remain

diﬃcult to solve, or require techniques that are very problem-speciﬁc. In this paper, we show that

Bregman iteration can be used to solve a wide variety of constrained optimization problems. Using

this technique, we propose a “split Bregman” method, which can solve a very broad class of L1-

regularized problems. We apply this technique to the Rudin–Osher–Fatemi functional for image

denoising and to a compressed sensing problem that arises in magnetic resonance imaging.

Key words. constrained optimization, L1-regularization, compressed sensing, total variation denoising

AMS subject classiﬁcation. 65K05

DOI. 10.1137/080725891

1. Introduction. The category of L1-regularized problems includes many important prob-

lems in engineering, computer science, and imaging science. The general form for such prob-

lems is

(1.1) min

|Φ(u)| + H(u),

where |·| denotes the L1-norm and both |Φ(u)| and H(u) are convex functions. Many im-

portant problems in imaging science (and other computational areas) can be posed as L1-

regularized optimization problems. Some common examples of this include the following:

“TV/ROF denoising”: min

u

u − f

,(1.2)

“basis pursuit/compressed sensing”: min

J(u)+

Au − f

,(1.3)

where J(u) is some regularizing functional, usually in the form of a bounded variation (BV)

or Besov norm.

The Rudin–Osher–Fatemi (ROF) functional (1.2), despite its simple form, has proved to

be very diﬃcult to minimize by conventional methods. Total variation (TV) based image

restoration was ﬁrst introduced in [23]. In that paper, the authors proposed minimizing this

energy using a gradient projection method. While this approach is simple, the nonlinearity and

∗

Received by the editors June 2, 2008; accepted for publication (in revised form) November 4, 2008; published

electronically April 1, 2009. This research was supported by the National Science Foundation’s GRFP program, as

w ell as by ONR grant N000140710810 and the Department of Defense.

http://www.siam.org/journals/siims/2-2/72589.html

†

Department of Mathematics, University of California at Los Angeles, Los Angeles, CA 90095 (tomgoldstein1@

gmail.com, sjo@math.ucla.edu).

323

324 TOM GOLDSTEIN AND STANLEY OSHER

poor conditioning of the problem make this approach very slow. Several authors have proposed

improved time-stepping schemes that result in better performance, such as those presented

in [26, 16]. A more eﬃcient class of solvers are those based on Newton’s method. One such

algorithm was presented in [9], in which the preconditioned conjugate gradient method was

used to invert the Hessian at each step. A somewhat more eﬃcient implementation of a second-

order method was proposed by Vogel in [25], where an algebraic multigrid preconditioner was

used to accelerate the method.

Still, the most eﬃcient solver for the ROF problem was proposed by Darbon and Sigelle

in [10]. In this work, the ROF functional was approximated using an anisotropic BV norm.

It was shown that, using this formulation, the resulting problem could be solved very quickly

using graph cuts [3].

Problems of the form (1.3) have received a lot of attention recently because of the intro-

duction of compressed sensing (CS) techniques, which allow high resolution images and signals

to be reconstructed from a small amount of data [7, 6, 11]. This formulation has been shown

to be useful in many areas, including medical imaging [17, 18], radar [1], and other signal

processing applications. CS is based on the idea that a signal can be reconstructed from a

very small number of measurements, provided that these measurements are obtained in the

correct basis. The particular application of CS which we will focus on is magnetic resonance

imaging (MRI). The goal of sparse MRI is to solve

min

J(u) such that Fu − f 

=0.

Here, f represents the so-called CS data, which consists of samples of the Fourier transform

of the unknown image. F comprises a subset of the rows of a Fourier matrix, u represents the

unknown image that we wish to reconstruct, and J(·) is a properly chosen L1-regularization

term. The unconstrained formulation for this problem was introduced in [14], where a Breg-

man iterative approach [4] was used to obtain solutions to “denoising” problems of the form

(1.4) min

J(u) such that Fu− f 

<σ.

Because of the presence of an L1-regularization term, optimization problems of the form (1.4)

are still very diﬃcult to solve. Several authors have applied classical optimization schemes,

such as interior point methods, to problems of this form. In [15], CS problems were refor-

mulated as quadratic programming problems which were then solved using the code “l1 ls,”

which is claimed to be one of the most eﬃcient solvers for general CS problems. Another

notable interior point approach is the code “l1-magic,” which formulates a CS problem as

a second-order cone program and enforces inequality constraints using a logarithmic barrier

potential [7].

In the special case where the CS problem can be written in the form

(1.5) min

|u| such that Au − f 

<σ,

one can use a relatively new class of methods that reduce the CS problem to a set of simpler

problems using linearization. The ﬁrst of these methods is the “ﬁxed point continuation”

A FAST METHOD FOR L1-REGULARIZED PROBLEMS 325

(FPC) method introduced in [13] by Hale, Yin, and Zhang. This method solves the uncon-

strained problem

(1.6) min

|u| +

Au − f

by iteratively performing gradient descent steps.

By applying the Bregman iteration scheme in [22, 14], it is also possible to solve the

constrained problem (1.5) using FPC/Bregman. This is done by iteratively solving the un-

constrained problem (1.6) and then modifying the value of f used in the next iteration.

Rather than solving the unconstrained problem and then performing a Bregman update

separately, these two steps were elegantly combined in the linearized Bregman algorithm [30].

Linearized Bregman solves the problem (1.5) by iteratively solving

k+1

= v

+ A

(f − Au

k+1

= δ ∗ shrink (v

k+1

, 1/μ)

for k =1, 2,...,n. The algorithm is terminated when the denoising constraint in (1.5)is

met. It was shown in [5, 21]thatu

will be a suitable approximation to the solution of (1.5)

provided that appropriate values are chosen for the parameters μ and δ.

While the FPC and linearized Bregman algorithms are extremely eﬃcient, they can solve

only problems which can be put into the form (1.6). Because the gradient operator is not

invertible, these algorithms cannot be used to solve problems involving the BV norm. Also,

these schemes cannot solve optimization problems involving multiple L1-regularization terms.

For these reasons, it is diﬃcult to apply the FPC and linearized Bregman methods to image

processing problems. For example, it has been noted by many authors [17, 24] that optimal

MRI reconstruction is obtained using a combination of the BV norm and the Besov norm,

1,1

. In this case, this problem can be written as

min

u

+ u

Fu − f

where ·

= ∇u

is the BV norm and u

= Hu

denotes the Besov norm with

respect to the Haar wavelet transform. We will later address this particular form of the CS

problem.

In this paper, we will present a general technique that can be used to solve most common

L1-regularized problems eﬃciently. Furthermore, the optimization scheme we employ can be

generalized to solve a very broad range of equality-constrained optimization problems, some

of which may be diﬃcult to solve by existing techniques.

The contents of this paper are organized as follows: We begin with a brief discussion of

constrained optimization problems and classical penalty function methods. We then review

the concept of Bregman iteration and use it to derive a general principle for solving constrained

optimization problems. We will then deﬁne the “split Bregman” method and show how it can

be used to solve the general L1-regularized optimization problem (1.1). Finally, we will apply

the split Bregman technique to TV denoising and CS problems to demonstrate its eﬃciency.

The latter may involve BV, Besov, or multiple regularizers.

326 TOM GOLDSTEIN AND STANLEY OSHER

1.1. Constrained optimization problems. Consider a convex energy functional, E,and

some linear function, A : R

→ R

. We wish to solve the generalized constrained optimization

problem

(1.7) min

E(u) such that Au = b.

This problem can be very diﬃcult to solve directly if E is nondiﬀerentiable.

In order to make (1.7) simpler to solve, we wish to convert it into an unconstrained

optimization problem. One common method for doing this it to use a penalty function/

continuation method, which approximates (1.7) by a problem of the form

(1.8) min

E(u)+

Au − b

where λ

<λ

< ··· <λ

is an increasing sequence of penalty function weights [2, 20]. In

order to enforce that H(u) ≈ 0, we must choose λ

to be extremely large.

Unfortunately, for many problems, choosing a large value for λ makes (1.8)extremely

diﬃcult to solve numerically. We often wish to solve (1.8) by a Newton-type method, which

requires us to invert the Hessian of the objective function. However, as λ

→∞, the condition

number of the Hessian approaches inﬁnity, making it impractical to use fast iterative methods

(such as conjugate gradient or Gauss–Seidel methods) [2, 20]. Also, for many applications, λ

must be increased in very small steps, making the method less eﬃcient.

In the next section, we will show that Bregman iteration can be used to reduce (1.7)toa

short sequence of unconstrained problems. In this sense, Bregman iteration is an alternative

to conventional penalty function methods.

2. Bregman iteration. Bregman iteration is a concept that originated in functional anal-

ysis for ﬁnding extrema of convex functionals [4]. Bregman iteration was ﬁrst used in image

processing by Osher et al. in [22], where it was applied to the ROF model for TV denoising.

Bregman iteration has also been applied to solve the basis pursuit problem in [30, 5, 21], and

was subsequently applied to medical imaging problems in [14]. Rather than focus on speciﬁc

applications, we will present here a general formulation of this technique.

We begin with the concept of “Bregman distance.” The Bregman distance associated with

a convex function E at the point v is

(u, v)=E(u) − E(v) −p, u − v,

where p is in the subgradient of E at v. Clearly, this is not a distance in the usual sense

because it is not in general symmetric. However, it does measure closeness in the sense that

(u, v) ≥ 0, and D

(u, v) ≥ D

(w, v)forw on the line segment between u and v.

Again, consider two convex energy functionals, E and H, deﬁned over R

with min

u∈R

H(u)

= 0. The associated unconstrained minimization problem is

(2.1) min

E(u)+λH(u).

We can modify this problem by iteratively solving

剩余20页未读，继续阅读

评论收藏

内容反馈

ptx824

粉丝: 8
资源: 42

L1正则化问题的分裂Bregman方法.pdf

Bregman算法

split bregman

偏微分图像去噪中的经典算法分裂Bregman算法的源代码.zip

求解L1_正则项优化问题的两种算法_朱红

分裂Bregman算法的源代码1

偏微分图像去噪中的经典算法分裂Bregman算法的源代码matlab.zip

基于全局优化凸模型和分裂布雷格曼算法的快速边缘检测方法

分裂bregman算法C++程序，用于图像去燥

分裂BregmanTV全变分各向同性各向异性去噪.zip

Split-Bregman.zip

Split Bregman linear inverse with total variant norm：使用 Tom Goldstein 提出的 split bregman 方法求解一个全变分正则化线性逆问题-matlab开发

L1正则化机器学习问题求解分析.pdf

基于分裂Bregman方法的非局部变分双正则化图像复原新模型

不适定问题的正则化方法及应用__刘继军著_北京：科学出版社_2005.09.pdf

【图像去噪】基于分裂Bregman算法实现图像去噪matlab代码.zip

The-split-bregman-method.zip_The Split Bregman_The-split-bregman

偏微分图像去噪中的经典算法_分裂Bregman代码_Bregman_图像去噪_图像、微分、Bergman_

基于Split Bregman算法的正则化图像复原

BregmanCookbook.zip_Bregman_Bregmancookbook_split bregman_迭代_迭代算

splitting_bregman分裂算法用于求解最优化问题.zip

全变差TV去噪(split bregman) opencv

分裂等式公共不动点问题的一般替代正则化方法

研究论文-基于小波框架的有限角度CT重建算法.pdf

Split Bregman method for Total Variation Denoising：实现split Bregman method for Total Variation Denoising-matlab开发

混合TV-L1噪声消除模型及其分裂Bregman算法

Split Bregman - Globally Convex Segmentation：SB-GCS，L1 正则化快速、凸、水平集分割技术-matlab开发

splitting_bregman

最新资源