splitbregman_分裂Bregman学习笔记资源-CSDN文库

需积分: 20 28 浏览量 2017-12-11 09:29:13 上传评论 2 收藏 1.66MB PDF 举报

### 分裂布雷格曼方法在L1正则化问题中的应用 #### 一、引言与背景近年来，L1正则化优化问题因其在压缩感知领域的突破性进展而备受关注。压缩感知技术允许从有限的数据量中重建图像和信号，这极大地推动了信号处理和图像恢复等领域的发展。然而，尽管压缩感知技术取得了显著成果，许多L1正则化问题仍然难以解决或需要非常特定的技术来应对。本文讨论的分裂布雷格曼（Split Bregman）方法是一种通用且高效的算法框架，可以应用于广泛的L1正则化问题中。该方法基于Bregman迭代的概念，并通过引入“分裂”思想，使得该方法能够灵活地处理多种约束优化问题。文中重点介绍了该方法在图像去噪（特别是鲁丁-奥斯赫-法特米函数）和压缩感知问题（如磁共振成像）中的应用。 #### 二、L1正则化问题的基本形式 L1正则化问题的一般形式可表示为： \[ \text{min}_{u} \left|\Phi(u)\right| + H(u) \] 其中，\(\left|\cdot\right|\) 表示L1范数，\(\left|\Phi(u)\right|\) 和 \(H(u)\) 都是凸函数。这种形式的问题在工程学、计算机科学以及图像科学等多个领域中都有重要的应用。 #### 三、具体应用实例 - **TV/ROF去噪**：鲁丁-奥斯赫-法特米（ROF）函数式，用于图像去噪： \[ \text{min}_{u} \left\|u\right\|_{BV} + \frac{\mu}{2}\left\|u - f\right\|^2_2 \] 其中，\(\left\|u\right\|_{BV}\) 表示图像\(u\)的总变分（Total Variation, TV），\(\left\|u - f\right\|^2_2\) 表示图像\(u\)与原始图像\(f\)之间的差值的平方和，\(\mu\) 是正则化参数。 - **基础追踪/压缩感知**：基础追踪问题或压缩感知问题的形式为： \[ \text{min}_{u} J(u) + \frac{\mu}{2}\left\|Au - f\right\|^2_2 \] 其中，\(J(u)\) 通常采用总变分（BV）或贝索夫范数的形式作为正则化项，\(A\) 是观测矩阵，\(f\) 是观测数据。 #### 四、分裂布雷格曼方法原理分裂布雷格曼方法的核心在于将原问题分解为两个子问题，每个子问题都可以更高效地解决。该方法的关键步骤包括： 1. **初始化**：设置初始条件。 2. **分裂**：将原始问题分解为两个子问题，一个涉及\(u\)的更新，另一个涉及辅助变量\(d\)的更新。 3. **交替迭代**：对\(u\)和\(d\)进行交替迭代更新，直至收敛。 4. **收敛判据**：定义收敛条件，当满足时停止迭代。 #### 五、分裂布雷格曼方法的应用 - **图像去噪**：分裂布雷格曼方法可以有效地应用于鲁丁-奥斯赫-法特米模型中，通过对图像进行去噪处理，保留边缘细节的同时去除噪声。 - **压缩感知**：在磁共振成像等场景下，该方法可以利用少量的观测数据来重构高质量的图像。 #### 六、总结分裂布雷格曼方法提供了一种灵活且强大的工具，用于解决各种L1正则化问题。通过将复杂问题分解为简单的子问题，该方法不仅简化了解决方案的设计，还提高了计算效率。尤其是在图像处理和信号恢复领域，该方法展现出了广泛的应用前景和实际价值。随着研究的不断深入和技术的进步，预计分裂布雷格曼方法将在更多领域得到推广和应用。

资源推荐

资源详情

资源评论

SIAM J. IMAGING SCIENCES



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

Downloaded 10/15/15 to 202.206.245.13. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

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”

Downloaded 10/15/15 to 202.206.245.13. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

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.

Downloaded 10/15/15 to 202.206.245.13. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

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

Downloaded 10/15/15 to 202.206.245.13. Redistribution subject to SIAM license or copyright; see http://www.siam.org/journals/ojsa.php

剩余20页未读，继续阅读

评论收藏

内容反馈

qq_26401205

粉丝: 2
资源: 2

split bregman

最新资源

split bregman

基于Split_Bregman迭代算法的PICCS图像重建算法matlab仿真+代码操作视频

splitting Bregman

Split-Bregman.zip

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

SplitBregman去噪（TV模型）

傅里叶反变换matlab代码-Split-Bregman-Total-Variation-Jacobian-Matrix:使用SplitBre

Split bregman 算法MATLAB源代码

分裂Bregman算法的源代码1

Bregman算法

splitting_bregman

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

split

基于Split Bregman的稀疏图像重建算法.zip

split Bregman入门礼包.zip

toolbox_optim.zip_Bregman_DEMO_split bregman_split bregman_spli

全变差TV去噪(split bregman) opencv

2009-SIAM--SplitBregman_Framelet.zip_split bregman_split-bregman

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

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

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

图像重建基于matlab布雷格曼迭代算法集合ART算法CT图像重建【含Matlab源码 1905期】.zip

bregman信号恢复算法

data_split.c

5_6210913715248693442_split_

split_knockoffs

Sql in split

split_string

最新资源