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.

### Like this:

Like Loading...

*Related*