rambo

Soft、Hard thresholding and Structured group thresholding

优化问题描述,参见机器学习中的正则化初探[一]

min_{\alpha\in R^{p}} \frac{1}{2} \lVert x-D\alpha\rVert _{2}^{2} \quad s.t.\lVert \alpha\rVert_{0} \leq k                           1)

D=[d_{1},...,d_{p}]为一组正交小波基即D^{T}D=I

等价形式:min_{\alpha\in R^{p}} \frac{1}{2} \lVert D^{T}x-\alpha \rVert _{2}^{2} \quad s.t.\lVert \alpha\rVert_{0} \leq k           2)

定义向量\beta\doteq D^{T}x \in R_{p},所以x= D\beta 因为D是一个正交阵。为了获得最佳的稀疏近似,取k个最大的系数\{\lvert \beta[1]\rvert,...,\lvert \beta[p]\rvert\}的值。

hard-thresholding

式1)的解\alpha^{ht} 可以通过下式得到,称为"hard-thresholding":

QQ截图20150511184905

其中1_{\lvert\beta[i]\rvert \ge \mu}是一个指示函数,当\lvert\beta[i]\rvert\ge \mu时为1,否则为0。

当图像x被高斯噪声污染时,通过选择\mu值大小,估计得到D\alpha^{ht}可以很好地还原始图像。

soft-thresholding

所谓"soft thresholding"是由Donoho and Johnstone在《Ideal spatial adaptation by wavelet shrinkage》中引入的。QQ截图20150511184918

\alpha^{st}实际上是下述稀疏重构问题的解。

min_{\alpha\in R^{p}} \frac{1}{2} \lVert x-D\alpha\rVert _{2}^{2} +\lambda \lVert \alpha\rVert_{1}                           3)

在Michael Elad 的论文《On the Role of Sparse and Redundant Representations in Image Processing》有一段话:the optimization decouples into a set of independent scalar problems of the form min_{\alpha\in R^{p}} \frac{1}{2} \lVert x-D\alpha\rVert _{2}^{2} +\lambda \lVert \alpha\rVert_{p}^{p} , which have particularly simple closed-form solutions in the two notable cases p=0 and p=1, called hard- and soft-thresholding, respectively.

形象的图示如下:

QQ截图20150511192027

Structured group thresholding

补充:小波变换是将原始图像与小波基函数以及尺度函数进行内积运算,基于小波变换的数据压缩目的就是希望经小波分解后得到的三个方向的细节分量具有高度的局部相关性,而整体相关性能最大限度的消除。

小波基元素d_{i}是其他基元素的放大和平移。It is for instance possible to define neighborhood relationships for wavelets whose spatial supports are close to each other,or hierarchical relationships between wavelets with same or similar localization
but with different scales.

对于一维信号,小波系数可由如下的小波树表示:

QQ截图20150511200542

 

利用小波基之间的相邻关系来定义group of coefficients,形成对于\{1,...,p\}的划分G。对于G中的每一组g

QQ截图20150511201435

这个算子,可以将一组相邻系数共同置0当其l_{2}-norm\quad ball低于阈值\lambda时,其实\alpha^{gt}with \beta=D^{T}x是下列优化方程的解。

min_{\alpha\in R^{p}} \frac{1}{2} \lVert x-D\alpha\rVert _{2}^{2} +\lambda\sum{g\in G}\lVert \alpha[g]\rVert_{2}^{2}                           4)

QQ截图20150511203032