# Algorithm Power Hour: Approximate Message Passing (AMP)

This algorithm power hour is devoted to Approximate Message Passing (AMP), presented in the paper: D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,” Proc. National Academy of the Sciences, vol. 106, no. 45, pp. 18914-18919, Nov. 2009.

Given an $$s$$-sparse vector $$\vx \in \mathcal{R}^N$$,
we sense it by a matrix $$\mathbf{\Phi} \in \mathcal{R}^{m\times N}$$ with $$N > m$$,
which produces the measurement vector $$\vu = \mathbf{\Phi}\vx$$.
Define the index of the columns of $$\mathbf{\Phi}$$ as $$\Omega = \{1, 2, \ldots, N\}$$.
AMP proceeds as iterative thresholding, but with a critical difference in how it defines the residual.
Given the solution at iteration $$k$$ $$\vx_k$$,
and a thresholding function $$T_1(\vy; \tau)$$ with the threshold $$\tau \ge 0$$,
AMP defines the $$k$$-order residual $$\vr_k$$
$$\vr_k = \vu – \mathbf{\Phi}\vx_k + \frac{1}{\delta} \vr_{k-1} \frac{1}{N} \mathbf{1}^T T’\left ( \vx_{k-1} + \mathbf{\Phi}^* \vr_{k-1} ; \tau_{k-1} \right )$$
where $$T'(s) = dT(s)/ds$$ is the derivative of the thresholding function $$T(s)$$ with respect to its argument, and $$\delta$$ is the problem indeterminacy, or undersampling $$\delta = m/N$$. (Thank you Ulugbek for making this clear!)
AMP refines $$\vx_k$$ according to
$$\vx_{k+1} = T\left ( \vx_k + \mathbf{\Phi}^* \vr_k ; \tau_k \right )$$
As an example, if we use soft thresholding with threshold parameter $$\tau > 0$$, then $$T'(s)$$ is one everywhere except for zero in $$s \in [-\tau,\tau]$$
AMP repeats the procedure above until some stopping condition,
for instance, $$||\vr_k||_2/||\vx|| < 10^{-5}$$.
Here is the code I am using.

And with that, I must take my leave for the day.