美食网站制作模板,长春seo培训,餐饮网站源码,项目外包和人力外包哪个好正则化实现降噪#xff0c;分别使用最小二乘、定步长梯度下降和回溯法的梯度下降求解最优解 原创文章#xff01;转载需注明来源#xff1a;️ Sylvan Ding’s Blog ❤️ 实验目的
参考 INTRODUCTION TO NONELINEAR OPTIMIZATION. Amir Beck. 2014 的 3.4 Denoising …正则化实现降噪分别使用最小二乘、定步长梯度下降和回溯法的梯度下降求解最优解 原创文章转载需注明来源©️ Sylvan Ding’s Blog ❤️ 实验目的
参考 INTRODUCTION TO NONELINEAR OPTIMIZATION. Amir Beck. 2014 的 3.4 Denoising 相关内容分别使用 最小二乘法、定步长的梯度下降constant和回溯法的梯度下降backtracking实现对 Example 3.4 中带有噪声信号的降噪过程对比分析采用不同方法的降噪效果。添加不同的噪声或以不同的方式添加噪声观察上述三种降噪方法的降噪效果并简要分析结果。了解并掌握最小二乘法和惩罚问题Penalized Problem学会使用MATLAB求解并分析相关问题。
实验环境
MATLAB R2021a
实验内容
考虑一段信号 x∈R300x\in \mathbb{R}^{300}x∈R300 在该信号上添加一段高斯加性噪声μ0,σ0.05\mu0, \sigma0.05μ0,σ0.05得到 bbb由下述MATLAB语句生成。要求使用正则化的最小二乘RLS、定步长的梯度下降、回溯法的梯度下降分别对加噪后对信号 bbb 进行降噪处理并分析各方法降噪效果的优劣。
tlinspace(0,4,300);
xsin(t)t.*(cos(t).^2);
randn(seed,314);
bx0.05*randn(300,1);真实信号与噪声信号的对比图
subplot(1,2,1);
plot(1:300,x,LineWidth,2);
subplot(1,2,2);
plot(1:300,b,LineWidth,2);算法描述
降噪问题的一般表述为给定含有噪声的信号 bbb找到一个“足够好”的估计值 x∗x^*x∗使得 x∗≈bx^*\approx bx∗≈b即 x∗argminx∥x−b∥2x^* \arg \min \limits_{x} \Vert x-b \Vert ^2x∗argxmin∥x−b∥2. 显然这个优化问题的解是 x∗bx^*bx∗b。然而这一最优解是没有意义的即产生了过拟合的解。
因此为了解决过拟合的问题我们需要向目标函数中添加正则化项。不妨假设最初的信号是一段光滑的曲线那么向量 xxx 相邻两元素间的的差值也应当尽可能的小接近于0但不等于0. 这样正则化项就应当选用二次惩罚Quadratic Penalty即 R(x)∑i1n−1(xi−xi1)2,n300R(x)\sum^{n-1}_{i1} (x_i-x_{i1})^2, n300R(x)∑i1n−1(xi−xi1)2,n300. 也可以用更加紧凑的向量形式表示R(x)∥Lx∥2,L∈R(n−1)×n,n300R(x)\Vert Lx \Vert ^2, L\in \mathbb{R}^{(n-1)\times n}, n300R(x)∥Lx∥2,L∈R(n−1)×n,n300,
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∗argminx∥x−b∥2λ∥Lx∥2,λ0x^* \arg \min \limits_{x} \Vert x-b \Vert ^2\lambda \Vert Lx \Vert ^2, \lambda0x∗argxmin∥x−b∥2λ∥Lx∥2,λ0. 其中λ\lambdaλ 为正则化参数又称惩罚系数λ\lambdaλ 越大惩罚力度越强x∗x^*x∗ 越“平滑”反之亦然。当 λ0\lambda0λ0 时问题转化为一般的最小二乘问题LS也就会产生上述无意义的最优解。
最小二乘解
x∗(λ)argminx{f(x)≡xT(IλLTL)x−2bTx∥b∥2}x^*(\lambda) \arg \min \limits_{x} \left \{ f(x) \equiv x^T \left ( I\lambda L^T L \right )x -2b^Tx \Vert b \Vert ^2 \right \}x∗(λ)argxmin{f(x)≡xT(IλLTL)x−2bTx∥b∥2}
显然目标函数 f(x)f(x)f(x) 是一个二次函数而且必然有 ∇2f(x)2(IλLTL)≻0\nabla ^2f(x) 2\left (I\lambda L^T L\right ) \succ0∇2f(x)2(IλLTL)≻0因此由定理 2.41 可知该函数的任何驻点都是全局最小点。驻点满足 ∇f(x)0\nabla f(x)0∇f(x)0即 (IλLTL)xb\left ( I\lambda L^T L \right )xb(IλLTL)xb所以最优解 x∗(λ)(IλLTL)−1bx^*(\lambda) \left ( I\lambda L^T L \right )^{-1}bx∗(λ)(IλLTL)−1b.
梯度下降
目标函数f(x)xT(IλLTL)x−2bTx∥b∥2f(x) x^T \left ( I\lambda L^T L \right )x -2b^Tx \Vert b \Vert ^2f(x)xT(IλLTL)x−2bTx∥b∥2
目标函数的梯度g(x)∇f(x)(IλLTL)x−bg(x)\nabla f(x)\left ( I\lambda L^T L \right )x-bg(x)∇f(x)(IλLTL)x−b 梯度下降算法描述 设定 ϵ\epsilonϵ 初始化 x00,x0∈Rn,n300x_00, x_0\in \mathbb{R}^n, n300x00,x0∈Rn,n300 FOR k 0, 1, 2, … 选取下降方向 dkg(xk)d_kg(x_k)dkg(xk)选取步长 tkt_ktk使得 f(xktkdk)f(xk)f(x_kt_kd_k)f(x_k)f(xktkdk)f(xk)设置 xk1xktkdkx_{k1}x_kt_kd_kxk1xktkdkIF ∥g(xk1)∥≤ϵ\Vert g(x_{k1}) \Vert \le \epsilon∥g(xk1)∥≤ϵ THEN STOP 在算法循环的 2. 步长选取中对于定步长的梯度下降来说tkt_ktk 为一常量即 tktˉt_k\bar{t}tktˉ. 而对于采用回溯法的非精确线搜索来说令步长的初值 tks,s0t_ks, s0tks,s0更新步长 tk←βtk,β∈(0,1)t_k \gets \beta t_k, \beta \in (0,1)tk←βtk,β∈(0,1)直到满足 f(xk)−f(xktkdk)≥−αtk∇f(xk)Tdk,α∈(0,1)f(x_k)-f(x_kt_kd_k)\ge -\alpha t_k\nabla f(x_k)^Td_k, \alpha \in (0,1)f(xk)−f(xktkdk)≥−αtk∇f(xk)Tdk,α∈(0,1)可以证明当 t∈[0,ϵ]t\in [0,\epsilon]t∈[0,ϵ]上述不等式总成立。
实验步骤
% 生成L
Lzeros(299,300);
for i1:299L(i,i)1;L(i,i1)-1;
endfunction draw_pic(x,b,optimum,lambda,pic_title)
% 绘图函数
% 输入
% x是不含噪声的源信号
% b是含有噪声的原信号
% optimum的每列是对原信号b降噪后的一个解
% lambda是选用的正则化惩罚因子
% pic_title是图片的标题
color_prismcolormap(prism);
plot(1:300,b,LineWidth,1,DisplayName,signal with noise,...Color,color_prism(1,:));
hold on
plot(1:300,x,LineWidth,0.7,DisplayName,signal without noise,...Color,b);
[~,sz]size(optimum);
for j1:szpplot(1:300,optimum(:,j),LineWidth,0.8,DisplayName,...[denoised signal with \lambda,num2str(lambda(j)),..., SSE,num2str(norm(optimum(:,j)-x)^2)],...Color,color_prism(2*j,:));p.Color(4)0.5; % set transparent
end
hold off
xlim([0 300])
ylim([-0.5 3.5])
legend(Location,northwest)
title(pic_title)最小二乘
lambda[1 10 100 1000];
x_rls[];
for llambdax_rls[x_rls,(eye(300)l*L*L)\b];
end
draw_pic(x,b,x_rls,lambda,RLS solutions)定步长梯度下降
lambda[0.5 5 50];
x0zeros(300,1);
t0.005;
eps5;
x_constgd[];
for llambdaf(x) x*(eye(300)l*L*L)*x-2*b*xnorm(b)^2;g(x) (eye(300)l*L*L)*x-b;[x_constgd_next,~]...gradient_method_constant(f,g,x0,t,eps);x_constgd[x_constgd,x_constgd_next];
end
draw_pic(x,b,x_constgd,lambda,[...GMC solutions, t,num2str(t),...x_0(0,0,\dots),... \epsilon,num2str(eps)])function [x,fun_val]gradient_method_constant(f,g,x0,t,epsilon)
% Gradient method with constant stepsize
%
% INPUT
%
% f ......... objective function
% g ......... gradient of the objective function
% x0......... initial point
% t ......... constant stepsize
% epsilon ... tolerance parameter
% OUTPUT
%
% x ......... optimal solution (up to a tolerance)
% of min f(x)
% fun_val ... optimal function value
xx0;
gradg(x);
iter0;
while (norm(grad)epsilon)iteriter1;xx-t*grad;fun_valf(x);gradg(x);fprintf(iter_number %3d norm_grad %2.6f fun_val %2.6f \n,...iter,norm(grad),fun_val);
end回溯法梯度下降
lambda[0.1 5 50];
x0zeros(300,1);
s0.1;
alpha0.5;
beta0.3;
eps0.7;
x_constgd[];
for llambdaf(x) x*(eye(300)l*L*L)*x-2*b*xnorm(b)^2;g(x) (eye(300)l*L*L)*x-b;[x_constgd_next,~]...gradient_method_backtracking(f,g,x0,s,alpha,beta,eps);x_constgd[x_constgd,x_constgd_next];
end
draw_pic(x,b,x_constgd,lambda,[...GMB solutions, s,num2str(s),... x_0(0,0,...),... \alpha,num2str(alpha),... \beta,num2str(beta),... \epsilon,num2str(eps)])function [x,fun_val]gradient_method_backtracking(f,g,x0,s,alpha,...
beta,epsilon)
% Gradient method with backtracking stepsize rule
%
% INPUT
%
% f ......... objective function
% g ......... gradient of the objective function
% x0......... initial point
% s ......... initial choice of stepsize
% alpha ..... tolerance parameter for the stepsize selection
% beta ...... the constant in which the stepsize is multiplied
% at each backtracking step (0beta1)
% epsilon ... tolerance parameter for stopping rule
% OUTPUT
%
% x ......... optimal solution (up to a tolerance)
% of min f(x)
% fun_val ... optimal function value
xx0;
gradg(x);
fun_valf(x);
iter0;
while (norm(grad)epsilon)iteriter1;ts;while (fun_val-f(x-t*grad)alpha*t*norm(grad)^2)tbeta*t;endxx-t*grad;fun_valf(x);gradg(x);fprintf(iter_number %3d norm_grad %2.6f fun_val %2.6f \n,...iter,norm(grad),fun_val);
end结果分析
对于降噪后结果的评估使用和方差SSE其计算公式为 SSE∥x∗−x∥2SSE\Vert x^*-x \Vert ^2SSE∥x∗−x∥2.
最小二乘RLS 结果表明当 λ\lambdaλ 取值越大时RLS的解变得越平滑。当 λ1\lambda1λ1 时RLS的解非常接近于有噪声的信号 bbb不够平滑。当 λ100\lambda100λ100 时我们得到了一条更加平滑的RLS信号但是相较于 λ10\lambda10λ10 的RLS结果来说精确度更低特别是在靠近边界的地方。RLS的解在 λ1000\lambda1000λ1000 时变得非常平滑但是也更加偏离真实信号。
定步长梯度下降GMC
x0(0,0,…),tˉ0.005,ϵ5x_0(0,0,\dots),\bar{t}0.005,\epsilon5x0(0,0,…),tˉ0.005,ϵ5
λ\lambdaλEpochs0.5370537050368定步长梯度下降的精度整体偏低其解严重偏离真实信号特别是在波峰处。在实验时发现定步长 tˉ\bar{t}tˉ 的选取不能过大否则目标函数发散函数值持续增长到正无穷梯度下降偏离下降中心相反若 tˉ\bar{t}tˉ 选取过小将导致收敛速度极慢。ϵ\epsilonϵ 选取过小导致目标函数不收敛ϵ\epsilonϵ 选取过大将造成上述结果不精确到情况。
回溯法梯度下降GMB
x0(0,0,…),s0.1,α0.5,β0.3,ϵ0.7x_0(0,0,\dots),s0.1, \alpha0.5, \beta0.3,\epsilon0.7x0(0,0,…),s0.1,α0.5,β0.3,ϵ0.7
λ\lambdaλEpochs0.13754150335回溯法的梯度下降精确度较高。在 λ\lambdaλ 较小时需要的迭代步数较少随着 λ\lambdaλ 增大迭代步数随之增加但GMB曲线也更加平滑。
总结
本次试验对比了最小二乘、定步长梯度下降和回溯法的梯度下降法对添加高斯加性噪声的信号的降噪情况通过添加正则项达到降噪的目的。最小二乘法的结果受惩罚系数 λ\lambdaλ 的影响较大但当 λ\lambdaλ 选取合适时将实现较好的降噪效果得到比较光滑且接近原信号的RLS解定步长梯度下降的降噪结果严重偏离真实信号且对 tˉ\bar{t}tˉ 和 ϵ\epsilonϵ 的选取要求较高目标函数易发散。回溯法的梯度下降所得降噪的结果不仅精度高而且可通过增大 λ\lambdaλ 提高降噪效果且不会使降噪后的信号严重偏离原信号。 原创文章转载需注明来源©️ Sylvan Ding’s Blog ❤️
