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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s