编码衍射模型的 Nesterov 加速算法
考虑相位恢复问题:
$$ \min_z \;\; f(z):=\displaystyle\frac{1}{2}\displaystyle\sum_{j=(1,1)}^{(n,L)} \left(|\bar{a}_j^\top z|^2-b_j\right)^2, $$
其中 为采样向量。在到编码衍射模型中,则为
为一系列已知的采样信号,
为原始信号,
是观测的模长。
目标函数的 Wirtinger 导数为:
利用 Wirtinger 导数构造梯度下降算法求解相位恢复问题。迭代格式为: $
目录
初始化和迭代准备
输入信息:迭代初始点 ,观测模长
,采样信号
,原始数据
和停机准则 stop_cri 。 输出信息: 迭代得到的解
(其为真实信号
的恢复),包含迭代信息的结构体 info 。
- info.eff:每一步迭代的相对误差
- info.time:每一步迭代的 cpu 时间
- info.prod:矩阵向量积的次数
- info.ite:总迭代次数
- info.state:标记是否收敛
function [ z, info ] = Nes_C( z0, y, A, x, stop_cri, varargin)
参数设定,默认最大迭代次数 1500 次。 和 mumax 为步长相关的参数。
T=cputime; if nargin == 6 ite_max = varargin{1}; else ite_max=1500; end tau0=330; mumax=0.2;
将向量化的采集信号 转化为
的矩阵。
[n,L]=size(A); y=reshape(y,n,L);
为 Nesterov 加速法中的下降方向。
d=zeros(n,1);
计算信号 的在衍射变换下的结果:
(初始点处,取
)。 注意到 MATLAB 函数 fft 对于矩阵输入,对其每一列计算一维的离散傅里叶变换。
rsd=fft(conj(A).*(z0*ones(1,L))); l=norm(z0,2)^2; ite=0; z=z0;
相对误差 的计算方式:
其中 表示
与
之间的夹角。当
时,该相对误差为
。
relerr=norm(x-exp(-1i*angle(trace(x'*z)))*z,'fro')/norm(x,'fro');
初始化输出信息。
info.err=relerr; info.time=[0]; info.prod=[1]; prod=1;
迭代主循环
达到收敛条件:相对误差 小于阈值 stop_cri,或者迭代次数超过最大迭代次数 ite_max 限制,停止迭代。
while relerr>stop_cri && ite<ite_max
第 步的步长选取为
, 这里
。
mu=min(1-exp(-(ite+1)/tau0),mumax); alpha=mu/l;
由 Wirtinger 导数,有
计算矩阵 t,其 元素为
其中
为 Nesterov 加速梯度法的外推步。
t=(abs(rsd).^2-y).*rsd;
计算梯度 。
D=mean(A.*ifft(t),2);
Nesterov 加速梯度法。$d^{k}=\beta d^{k-1}+\nabla f(z^k)$ 为第 步的下降方向。
beta=0.7; d=beta*d+D; z=z-alpha*d;
迭代步数加一,更新残差的傅里叶变换 rsd 和相对误差 ,注意到在 Nesterov 加速法中, rsd 更新不在
处,而是在
处。
ite=ite+1; rsd=fft(conj(A).*((z-alpha*beta*d)*ones(1,L))); relerr=norm(x-exp(-1i*angle(trace(x'*z)))*z,'fro')/norm(x,'fro');
更新迭代信息,记录当前步的相对误差、cpu 时间、矩阵向量积次数。
info.err=[info.err,relerr];
info.time=[info.time,cputime-T];
prod=prod+2;
info.prod=[info.prod,prod];
end
当迭代退出时,记录总迭代步。并以 info.state 记录退出原因(是否达到收敛而退出迭代)。
info.ite=ite; if ite==ite_max info.state=0; else info.state=1; end
end
参考页面
我们在页面 实例:编码衍射模型 中展示该算法的一个应用,并将其与其它算法进行比较。
此页面的源代码请见: Nes_C.m。
版权声明
此页面为《最优化:建模、算法与理论》、《最优化计算方法》配套代码。 代码作者:文再文、刘浩洋、户将,代码整理与页面制作:杨昊桐。
著作权所有 (C) 2020 文再文、刘浩洋、户将