初期网站开发费会计分录,wordpress媒体库分类,深圳网站维护seo,南宁网站设L1正则化降噪#xff0c;对偶函数的构造#xff0c;求解含L1正则项的优化问题#xff0c;梯度投影法 本文主要实现L1正则化降噪#xff0c;L2 正则化降噪的文章在#xff1a; https://blog.csdn.net/IYXUAN/article/details/121565229 原创文章#xff01;转载需注明来源…L1正则化降噪对偶函数的构造求解含L1正则项的优化问题梯度投影法 本文主要实现L1正则化降噪L2 正则化降噪的文章在 https://blog.csdn.net/IYXUAN/article/details/121565229 原创文章转载需注明来源©️ Sylvan Ding’s Blog ❤️ 实验目的
学会使用L1正则化项求解降噪问题构造原问题的对偶问题以求解含L1正则项的优化问题使用梯度投影法求解带约束的优化问题在降噪过程中注意对比L1和L2正则化的区别并分析使用L1正则项在此降噪问题中的优势。
实验环境
MATLAB R2021a
实验内容
L2正则化 本文主要实现L1正则化降噪L2 正则化降噪的文章在 https://blog.csdn.net/IYXUAN/article/details/121565229 假设有一段被噪声污染的信号即 yxw,x,w,y∈Rnyxw,\ x,w,y\in \mathbb{R}^nyxw, x,w,y∈Rn . 其中 xxx 是不含噪声的源信号www 是一未知噪声yyy 是观察到的含噪信号。
目标是从观察到的信号 yyy 还原出源信号 xxx . 在实验一中我们假设最初的信号是一段光滑的曲线选用二次惩罚Quadratic Penalty作为正则化项则有
x∗argminx∥x−y∥2λ∥Lx∥2,λ0x^* \arg \min \limits_{x} \Vert x-y \Vert ^2\lambda \Vert Lx \Vert ^2, \lambda0x∗argxmin∥x−y∥2λ∥Lx∥2,λ0
其中x∗x^*x∗ 是所求得的最优解L∈R(n−1)×nL\in \mathbb{R}^{(n-1)\times n}L∈R(n−1)×n
L[1−100⋯0001−10⋯00001−1⋯00⋮⋮⋮⋮⋮⋮0000⋯1−1]L \begin{bmatrix} 1 -1 0 0 \cdots 0 0 \\ 0 1 -1 0 \cdots 0 0\\ 0 0 1 -1 \cdots 0 0\\ \vdots \vdots \vdots \vdots \vdots \vdots \\ 0 0 0 0 \cdots 1 -1 \end{bmatrix}L⎣⎢⎢⎢⎢⎢⎡100⋮0−110⋮00−11⋮000−1⋮0⋯⋯⋯⋯000⋮1000⋮−1⎦⎥⎥⎥⎥⎥⎤
利用最小二乘法可以解得 x∗(λ)(IλLTL)−1yx^*(\lambda) \left ( I\lambda L^T L \right )^{-1}yx∗(λ)(IλLTL)−1y .
L1正则化
然而这种使用二次惩罚作为正则项接着使用最小二乘求解的方法具有一定的局限性在某些情况下无论正则化参数 λ\lambdaλ 如何设置都不能得到理想的解。事实上对于存在断点的信号比如脉冲信号来说由于惩罚项 ∥Lx∥2\Vert Lx \Vert ^2∥Lx∥2 是二次的断点会导致惩罚项的值急剧增大。因此这种二次惩罚项会让有噪信号的间断点处更加平滑但这种间断点处的平滑并不是我们希望得到的。
为了缓解这一问题削弱信号在跳跃处的惩罚项值增大的幅度我们使用 L1 范数形式的惩罚项而非二次惩罚那么优化问题变为P
minx∥x−y∥2λ∥Lx∥1\min \limits_{x} \Vert x-y \Vert ^2\lambda \Vert Lx \Vert _1xmin∥x−y∥2λ∥Lx∥1 .
算法描述
构造对偶问题
优化问题P等价于如下问题
minx,z∥x−y∥2λ∥z∥1s.t.zLx\begin{array}{l} \min \limits _{x,z} \Vert x-y \Vert ^2 \lambda \Vert z \Vert _1 \\ \mathrm{s.t.} zLx \end{array}x,zmins.t.∥x−y∥2λ∥z∥1zLx
那么拉格朗日函数 LLL 为
L(x,z,μ)∥x−y∥2λ∥z∥1μT(Lx−z)∥x−y∥2(LTμ)Txλ∥z∥1−μTz\begin{array}{l} L(x,z,\mu) \Vert x-y \Vert ^2 \lambda \Vert z \Vert _1 \mu ^T (Lx-z) \\ \Vert x-y \Vert ^2 (L^T \mu)^Tx \lambda \Vert z \Vert _1 - \mu ^Tz \end{array}L(x,z,μ)∥x−y∥2λ∥z∥1μT(Lx−z)∥x−y∥2(LTμ)Txλ∥z∥1−μTz
对偶目标函数Dual objective function为 q(μ)minx,zL(x,z,μ)q(\mu)\min \limits _{x,z} L(x,z,\mu)q(μ)x,zminL(x,z,μ).
观察 LLL 可以发现可分别求 xxx 和 zzz 的最优解即
q(μ)minx{∥x−y∥2(LTμ)Tx}minz{λ∥z∥1−μTz}q(\mu)\min \limits _{x} \left \{ \Vert x-y \Vert ^2 (L^T \mu)^Tx \right \} \min \limits _{z} \left \{ \lambda \Vert z \Vert _1 - \mu ^Tz \right \}q(μ)xmin{∥x−y∥2(LTμ)Tx}zmin{λ∥z∥1−μTz}.
q(μ)q(\mu)q(μ) 中关于 xxx 部分的最小值
对于 ∥x−y∥2(LTμ)Tx\Vert x-y \Vert ^2 (L^T \mu)^Tx∥x−y∥2(LTμ)Tx 求关于 xxx 的最小值显然这是一个二次函数在梯度消失时取得最小值即
2(x−y)LTμ02(x-y)L^T\mu 02(x−y)LTμ0
解得 x∗y−12LTμx^*y-\frac{1}{2}L^T\mux∗y−21LTμ 故
minx∥x−y∥2(LTμ)Tx−14μTLLTμμTLy.\min \limits _{x} \Vert x-y \Vert ^2 (L^T \mu)^Tx -\frac{1}{4}\mu ^T LL^T \mu \mu ^TLy.xmin∥x−y∥2(LTμ)Tx−41μTLLTμμTLy.
q(μ)q(\mu)q(μ) 中关于 zzz 部分的最小值
minzλ∥z∥1−μTz{0,∥μ∥∞≤λ−∞else.\min \limits _z \lambda \Vert z \Vert _1 - \mu ^Tz \left\{\begin{matrix} 0, \Vert \mu \Vert _\infty \le \lambda \\ - \infty else. \end{matrix}\right.zminλ∥z∥1−μTz{0,−∞∥μ∥∞≤λelse.
综上对偶目标函数为
q(μ)minx,zL(x,z,μ){−14μTLLTμμTLy,∥μ∥∞≤λ−∞else.q(\mu)\min \limits _{x,z} L(x,z,\mu) \left\{\begin{matrix} -\frac{1}{4}\mu ^T LL^T \mu \mu ^TLy, \Vert \mu \Vert _\infty \le \lambda \\ -\infty else. \end{matrix}\right.q(μ)x,zminL(x,z,μ){−41μTLLTμμTLy,−∞∥μ∥∞≤λelse.
那么对偶问题就为
max−14μTLLTμμTLys.t.∥μ∥∞≤λ.\begin{array}{l} \max -\frac{1}{4}\mu ^T LL^T \mu \mu ^TLy \\ \mathrm{s.t.} \Vert \mu \Vert _\infty \le \lambda. \end{array}maxs.t.−41μTLLTμμTLy∥μ∥∞≤λ.
使用梯度投影法求解对偶问题
投影的定义
约束域 C:{μ∈Rn−1:∥μ∥∞≤λ}C:\left \{ \mu \in \mathbb{R} ^{n-1}: \Vert \mu \Vert _\infty \le \lambda \right \}C:{μ∈Rn−1:∥μ∥∞≤λ} 是“盒状的”即
−λ≤μi≤λ,i1,2,…,n−1.-\lambda \le \mu _i \le \lambda, i1,2,\dots,n-1.−λ≤μi≤λ,i1,2,…,n−1.
那么μ\muμ 在 CCC 上的投影 PC(μ)∈Rn−1P_C(\mu ) \in \mathbb{R} ^{n-1}PC(μ)∈Rn−1 为
[PC(μ)]i:{−λ,μi≤−λμi,−λ≤μi≤λλ,λ≤μi\left [ P_C(\mu ) \right ] _i : \left\{\begin{matrix} -\lambda , \mu _i \le -\lambda \\ \mu _i , -\lambda \le \mu _i \le \lambda \\ \lambda , \lambda \le \mu _i \\ \end{matrix}\right.[PC(μ)]i:⎩⎨⎧−λ,μi,λ,μi≤−λ−λ≤μi≤λλ≤μi
其中i1,2,…,n−1i1,2,\dots,n-1i1,2,…,n−1. 特别的当 λ1\lambda 1λ1 时即 lambda1 有PcMulambda*mu./max(abs(mu),lambda); PcMu 是 μ\muμ 在 CCC 上的投影即 PC(μ)P_C(\mu )PC(μ).
求解梯度的Lipschitz常数
对偶目标函数 q(μ)q(\mu)q(μ) 中LLT∈R(n−1)×(n−1)LL^T\in \mathbb{R} ^{(n-1)\times (n-1)}LLT∈R(n−1)×(n−1) 是一个对称矩阵对 ∀μ≠0\forall \mu \ne 0∀μ0 有瑞利商Rayleigh Quotient
RLLT(μ)μTLLTμ∥μ∥2∥Lμ∥2∥μ∥2∑i1n−1(μi−μi1)2∥μ∥2≤2(∑i1n−1μi2∑i1n−1μi12)∥μ∥2≤4∥μ∥2∥μ∥24\begin{array}{l} R_{LL^T}(\mu ) \frac{\mu ^TLL^T\mu}{\Vert \mu \Vert ^2} \frac{\Vert L\mu \Vert ^2}{\Vert \mu \Vert ^2} \frac{\sum _{i1} ^{n-1} (\mu _i- \mu _{i1})^2}{\Vert \mu \Vert ^2} \\ \le \frac{2\left ( \sum _{i1} ^{n-1} \mu _i^2 \sum _{i1} ^{n-1} \mu _{i1}^2\right )}{\Vert \mu \Vert ^2} \le \frac{4\Vert \mu \Vert ^2}{{\Vert \mu \Vert ^2}} 4 \\ \end{array}RLLT(μ)∥μ∥2μTLLTμ∥μ∥2∥Lμ∥2∥μ∥2∑i1n−1(μi−μi1)2≤∥μ∥22(∑i1n−1μi2∑i1n−1μi12)≤∥μ∥24∥μ∥24
由 定理1.11 知RLLT(μ)≤λmax(LLT)R_{LL^T}(\mu ) \le \lambda_{\max} (LL^T)RLLT(μ)≤λmax(LLT) 即 λmax(LLT)≤4\lambda_{\max} (LL^T) \le 4λmax(LLT)≤4. λmax(LLT)\lambda_{\max} (LL^T)λmax(LLT) 是 LLTLL^TLLT 的最大特征值 LLTLL^TLLT 的诱导范数Induced norm是一个谱范数Spectral norm令 ALLTALL^TALLT 则有
∥A∥2,2λmax(ATA)λmax(A).\Vert A \Vert _{2,2} \sqrt{\lambda _{\max} \left ( A^TA\right )}\lambda _{\max}(A).∥A∥2,2λmax(ATA)λmax(A).
因此二次函数 −14μTLLTμμTLy-\frac{1}{4}\mu ^T LL^T \mu \mu ^TLy−41μTLLTμμTLy 的梯度Lipschitz常数为
L′2×∥14A∥2,212λmax(A)2.L2\times \Vert \frac{1}{4} A \Vert _{2,2}\frac{1}{2}\lambda _{\max}(A)2.L′2×∥41A∥2,221λmax(A)2.
综上可用梯度投影法求解 μ∗\mu ^*μ∗ 令 tktˉ1L′t_k\bar{t} \frac{1}{L}tktˉL′1则有
μk1PC(μk−14LLTμk12Ly).\mu _{k1}P_C \left ( \mu _k -\frac{1}{4} LL^T \mu _k \frac{1}{2}Ly \right ).μk1PC(μk−41LLTμk21Ly).
定理 9.16 和 9.18 保证了 μ∗\mu ^*μ∗ 的收敛性.
假设 μ∗\mu ^*μ∗ 为梯度投影法所得结果那么原问题的解为
x∗y−12LTμ∗.x^* y-\frac{1}{2}L^T\mu ^*.x∗y−21LTμ∗.
实验步骤
在L1正则化中设定 λ1\lambda 1λ1 梯度投影的迭代次数为 100010001000 次.
%% L2正则化
Lsparse(n-1,n);
for i1:n-1
L(i,i)1;
L(i,i1)-1;
end
lambda100;
xde(speye(n)lambda*L*L)\y;
figure(3)
plot(t,xde);
randn(seed,314);
xzeros(1000,1);
x(1:250)1;
x(251:500)3;
x(501:750)0;
x(751:1000)2;
figure(1)
plot(1:1000,x,.)
axis([0,1000,-1,4]);
yx0.05*randn(size(x));
figure(2)
plot(1:1000,y,.)%% L1正则化
lambda1;
muzeros(n-1,1);
for i1:1000
mumu-0.25*L*(L*mu)0.5*(L*y);
mulambda*mu./max(abs(mu),lambda);
xdey-0.5*L*mu;
end
figure(5)
plot(t,xde,.);
axis([0,1,-1,4])结果分析 Figure 12.4. True signal (top image) and noisy signal (bottom image). 使用 L2 惩罚项时不能正确处理函数图像的三个间断点。但是使用 L1 惩罚项时在间断点处比任何 λ\lambdaλ 时的 L2 惩罚项的表现情况都要好。This result is much better than any of the quadratic regularization reconstructions, and it captures the breakpoints very well.
参考文献
INTRODUCTION TO NONELINEAR OPTIMIZATION. Amir Beck. 2014 : 12.3.10 DenoisingTHE GRADIENT PROJECTION ALGORITHM, https://sites.math.washington.edu/~burke/crs/408/notes/nlp/gpa.pdf 原创文章转载需注明来源©️ Sylvan Ding’s Blog ❤️
