# 正交匹配追赶法¶

$Ax = b.$

$\underset{x}{\min}\ \| x \|_0$

$$k \coloneqq \| x \|_0$$$$x$$ 的稀疏度。因为 $$x$$ 尽可能稀疏，故 $$A$$ 中少量元素对 $$b$$ 有较大贡献。刻画 $$A$$ 中元素对 $$b$$ 贡献的方式可以通过投影计算。设 $$A = [a_1, a_2, \ldots, a_m]$$，由余弦定理可知

$\cos(a_i, b) = \frac{\langle a_1, b \rangle}{|a_i||b|}$

$|b|\cos(a_i, b) = \frac{\langle a_1, b \rangle}{|a_i|}$

$$a_i$$ 为单位向量，即对 $$A$$ 的列向量进行归一化，则上式进一步简化为

$x_i \coloneqq |b|\cos(a_i, b) = \langle a_1, b \rangle$

% https://zhuanlan.zhihu.com/p/322180659
function [x] = OMP(A,b,sparsity)
%Step 1
index = []; k = 1; [Am, An] = size(A); r = b; x=zeros(An,1);
cor = A'*r;
while k <= sparsity
%Step 2
[Rm,ind] = max(abs(cor));
index = [index ind];
%Step 3
P = A(:,index)*inv(A(:,index)'*A(:,index))*A(:,index)';
r = (eye(Am)-P)*b; cor=A'*r;
k=k+1;
end
%Step 5
xind = inv(A(:,index)'*A(:,index))*A(:,index)'*b;
x(index) = xind;
end

1. Orthogonal Matching Pursuit Algorithm: A brief introduction. Andersen Ang. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada. https://angms.science