硬阈值追踪算法(Hard Thresholding Pursuit HTP)是由SIMON FOUCART提出来的,该算法结合了子空间追踪算法(Subspace Pursuit SP)算法和IHT算法的优势,一方面具备更强的理论保证,另一方面也表现出良好的实证效果。
与IHT算法不同的是,HTP算法在每次迭代中采用了SP算法中用最小二乘更新稀疏系数的方法,最小二乘是一种无偏估计方法,这使得更新结果更加精确,从而可以减少迭代次数。
与SP算法不同的是,SP算法在每次迭代中是采用测量矩阵与残差的内积(即\({{{\bf{A}}^T}({\bf{y}} - {\bf{Ax}})}\))的大小来挑选最大的 \(S\) 个支撑位置,而HTP算法则是像IHT算法一样采用 \({{\bf{x}}{\rm{ + }}{{\bf{A}}^T}({\bf{y}} - {\bf{Ax}})}\) 来挑选支撑,后者无疑比前者包含更多的信息,因此相对于SP算法,HTP算法能更快的找到支撑位置,从而减少迭代次数。
总的说来,HTP算法是结合了IHT算法和SP算法的优势,因此其表现也更好。HTP算法原理较为简单,在此不详细介绍,对SP算法的介绍在后续贪婪类算法中一并总结。
下面是HTP算法的伪代码:
HTP算法的程序如下:
function [hat_x] = cs_htp(y,A,K,itermax,error) % Emial: zhangyanfeng527@gmail.com % Reference: Foucart S. HARD THRESHOLDING PURSUIT: AN ALGORITHM FOR COMPRESSIVE SENSING[J]. % Siam Journal on Numerical Analysis, 2011, 49(6):2543-2563. % y: measurement (observe) vector % A: measurement (sensing) matrix % k: sparsity level x0 = .2 * ones(size(A,2),1) ; % initialization with the size of original u = 1 ; % stpesize=1 for times = 1 : itermax x_increase = A' * (y - A * x0); hat_x = x0 + u * x_increase ; [~,pos] = sort(abs(hat_x),'descend'); gamma = pos(1:K) ; z = A(:,gamma) \ y ; hat_x = zeros(size(A,2),1) ; hat_x(gamma) = z ; if norm(y - A * hat_x) < error || norm(hat_x-x0)/norm(hat_x) < error break; else x0 = hat_x ; end end end 5. 仿真以下对上述四种算法进行重构效果比较,测试程序如下:
%% CS reconstruction test % Emial: zhangyanfeng527@gmail.com clear clc close all M = 64 ; %观测值个数 N = 256 ; %信号x的长度 K = 10 ; %信号x的稀疏度 Index_K = randperm(N) ; x = zeros(N,1) ; x(Index_K(1:K)) = 5 * randn(K,1); % x为K稀疏的,且位置是随机的 Psi = eye(N); % x本身是稀疏的,定义稀疏矩阵为单位阵x=Psi*theta Phi = randn(M,N); %测量矩阵为高斯矩阵 Phi = orth(Phi')'; A = Phi * Psi; %传感矩阵 % sigma = 0.005; % e = sigma*randn(M,1); % y = Phi * x + e;%得到观测向量y y = Phi * x ; %得到观测向量y %% 恢复重构信号x tic theta = cs_iht(y,A,K); x_r = Psi * theta;% x=Psi * theta toc %% 绘图 figure; plot(x_r,'k.-');%绘出x的恢复信号 hold on; plot(x,'r');%绘出原信号x hold off; legend('Recovery','Original') fprintf('\n恢复残差:'); norm(x_r-x)%恢复残差上述测试脚本只提供了简单的实验设置,对算法重构成功率、算法迭代次数与误差的关系(收敛速度)、重构时间、鲁棒性等测试可以自由发挥。
参考文献[1] Blumensath, Thomas, and Mike E. Davies. "Iterative hard thresholding for compressed sensing." Applied and computational harmonic analysis 27.3 (2009): 265-274.
[2] Blumensath, Thomas, and Mike E. Davies. "Normalized iterative hard thresholding: Guaranteed stability and performance." IEEE Journal of selected topics in signal processing 4.2 (2010): 298-309.
[3] Blanchard, Jeffrey D., Jared Tanner, and Ke Wei. "CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion." Information and Inference: A Journal of the IMA 4.4 (2015): 289-327.
[4] Foucart, Simon. "Hard thresholding pursuit: an algorithm for compressive sensing." SIAM Journal on Numerical Analysis 49.6 (2011): 2543-2563.