文档介绍：浅谈凸优化问题中的Bregman迭代算法
分类：图像处理 信号处理2013-06-08 17:59 "17人阅谡评论(3)收藏 举报 目录⑺[+] 对于搞图像处理的人而言，不懂变分法，基本上，就没法读懂图像 处理的一些经典文献。当然，这已经是10年之前的事情了。
现在，如果不懂得Bregman迭代算法，也就没法读懂最近几年以 来发表的图像处理的前沿论文了。国内的参考文献，基本上都是直接引用 Bregman迭代算法本身，而对于其原理基本上找不到较为详细的论述。本 文简要叙述当前流行的Bregman迭代算法的一些原理。
近年来，由于压缩感知的引入，L1正则化优化问题引起人们广泛 的关注。压缩感知，允许通过少量的数据就可以重建图像信号。L1正则化 问题是凸优化中的经典课题，用传统的方法难以求解。我们先从经典的图 像复原问题引入：
在图像复原中，一种通用的模型可以描述如下：
f = Au + e,
我们目标是从观测到的图像f,寻找未知的真实图像u, u是n维 向量空间中的元素，f是m维向量空间中的元素。f在压缩感知的术语叫 做测量信号。£是高斯白噪声其方差为sigma^o A是线性算子，例如 反卷积问题中的卷积算子，压缩感知中则是子采样测量算子。
上述方程中，我们仅仅知道f,其它变量都不知道的。而且这种问 题通常情况都是病态的，通过引入正则项可以使之成为良态的。正则化方 法假定对未知的参数U引入一个先验的假设，例如稀疏性，平滑性。正则 化问题的常见方法Tikhonov方法，它通过求解下面的优化问题：
min
（決『+扣归『）,
其中mu是一个大于零的标量，事先设定的常数，用于权衡观测图 像f和正则项之间的平衡。双绝对值符号是L2范数。
下面，为了引入Bregman迭代算法，需要对两个重要的概念进行
描述。
2. Bregman 距离
Definition Suppose J : X R is a convex fimction and u E X. An element p € X* is called a subgradient of J at u if Vu € X
J(u) — J(it) — ( — u) > 0.
The set of all subgradients of J at u is called the subdifferential of J at u. and it is denoted by dJ(u).
注意这个定义，它是对泛函J在u点的subgradient的定义，p 点是其对偶空间的中的某一点。subgradient可以翻译为次梯度，子梯度， 弱梯度等。等式左边最右边一项是内积运算。如果泛函J是简单的一元函 数，则就是两个实数相乘。次梯度有什么好处呢？对于一般的导数定义， 例如y=|x|在0点是不可导的，但是对于次梯度，它是存在的。
Definition Suppose J : X —> R is a convex function, it, v € X and p € dJ(v).
Then the Breginan Distance between points u and v is defined by
巧仏 u)=丿(")-u - M •
The Breginan distance has several nice properties that make it an efficient tool to solve h regularization problems
上面的这个定义就是Bregman距离的定义。对于凸函数两个点u, v 之间的Bregman距离，等于其函数值之差，再减去其次梯度点p与自变 量之差的内积。要注意的是这个距离不满足对称性，这和一般的泛函分析 中距离定义是不一样的。
3. Bregman迭代算法
Bregman迭代算法可以高效的求解下面的泛函的最小
inin{ J(u) + H(u. /)} , ()
u
where for a closed and convex set X both J : X —> R and H % t R are convex lionnegative functions with respect to u E X. for a fixed f. In addition H(u. f) is assumed to be differentiable. Recall f is the vector or matrix, depending on the problem, that u was encoded into.
上式中的第一项J,定义为从X到