Module message_passing

Expand description

Message-passing detection of large MIMO systems: LAMA (complex Bayesian AMP) and orthogonal AMP (OAMP), with their state evolution.

Both algorithms solve the linear model $y = H x + w$ ($H$ of $M$ rows and $N$ columns, $w$ of variance $\sigma^{2}$ per entry, i.i.d. entries $x_{j}$ of a known prior) by alternating a linear step on the whole vector and a scalar MMSE denoiser on every entry. In the large-system limit the input of the denoiser behaves as the transmitted symbol in Gaussian noise of a variance that a scalar recursion, the state evolution, predicts: the MIMO system decouples into parallel AWGN channels.

§Denoiser

With $r = x + n$, $n$ of variance $\tau$ (circularly-symmetric complex, or real), the posterior mean and variance of $x$,

$$ F(r, \tau) = \mathbb{E}[X \mid r], \qquad G(r, \tau) = \mathrm{Var}[X \mid r], $$

for a discrete alphabet $F = \sum_{a} w_{a} a$ with $w_{a} \propto p_{a} e^{-|r - a|^{2}/\tau}$ (Jeon et al., eqs. 20 and 21), or for the Bernoulli-Gaussian prior $(1 - \rho)\, \delta(x) + \rho\, \mathcal{N}(0, 1/\rho)$ of sparse recovery (Ma & Ping, eq. 43). The MSE and variance functions of the state evolution are

$$ \Psi(\sigma^{2}, \gamma^{2}) = \mathbb{E}\left|F(S + \sigma Z, \gamma^{2}) - S\right|^{2}, \qquad \Phi(\sigma^{2}, \gamma^{2}) = \mathbb{E}\, G(S + \sigma Z, \gamma^{2}), $$

computed by Gauss–Hermite quadrature (Prior::mse); a separable square QAM reduces to its real PAM, $\Psi(\sigma^{2}, \gamma^{2}) = 2 \Psi_{R}(\sigma^{2}/2, \gamma^{2}/2)$ (Jeon et al., Lemma 8).

§LAMA

With the columns of $H$ normalised to a unit norm and $\beta = N/M$, from $\hat{s} = \mathbb{E}[S]$, $\gamma = \sigma^{2} + \beta \mathrm{Var}[S]$ and $r = y - H \hat{s}$ (Jeon et al., Algorithm 2),

$$ z = \hat{s} + H^{H} r, \quad \hat{s}’ = F(z, \gamma), \quad \gamma’ = \sigma^{2} + \beta \langle G(z, \gamma) \rangle, \quad r’ = y - H \hat{s}’ + \frac{\beta \langle G(z, \gamma) \rangle}{\gamma}\, r , $$

the last term being the Onsager correction. Its state evolution (Theorem 1, Corollary 2) is $\sigma^{2}{t+1} = \sigma^{2} + \beta \Psi(\sigma^{2}{t}, \sigma^{2}_{t})$ (amp_state_evolution), whose fixed points give the minimum and exact recovery thresholds of Table II (amp_thresholds). Amp normalises the columns of any channel itself.

§OAMP

With the SVD $H = U \Lambda V^{H}$, a de-correlated linear estimator and a divergence-free denoiser (Ma & Ping, eqs. 19, 14 and 38):

$$ r = s + W (y - H s), \quad W = \frac{N}{\mathrm{tr}(\hat{W} H)} \hat{W}, \quad s’ = C \left(F(r, \tau^{2}) - \frac{\overline{G}}{\tau^{2}} r\right), \quad C = \frac{\tau^{2}}{\tau^{2} - \overline{G}}, $$

with $\hat{W}$ the matched filter $H^{H}$, the pseudo-inverse or the LMMSE filter $v^{2} H^{H} (v^{2} H H^{H} + \sigma^{2} I)^{-1}$, $v^{2}$ estimated from the residual (eq. 30) and $\tau^{2}$ from the traces (eq. 31). The last iteration outputs $F(r, \tau^{2})$. oamp_state_evolution is the empirical state evolution of eq. 32 with the optimal denoiser (eq. 39b).

§Examples

use comnum_mimo::message_passing::{amp_thresholds, Domain, Prior};
use comnum_mapping::constellation::Constellation;
// QPSK: LAMA is optimal at any SNR below β = 1.475 and recovers the noiseless
// signal below β = 2.086 (Jeon et al., Table II)
let qpsk = Prior::uniform(&Constellation::qam(4)?.normalized());
let t = amp_thresholds(&qpsk, Domain::Complex);
assert!((t.beta_min - 1.475).abs() < 2e-3 && (t.beta_max - 2.086).abs() < 2e-3);

§References

C. Jeon, R. Ghods, A. Maleki and C. Studer, “Optimal data detection in large MIMO,” arXiv:1811.01917, 2018.
J. Ma and L. Ping, “Orthogonal AMP,” IEEE Access, 5, 2020–2033, 2017 (arXiv:1602.06509).

Structs§

Amp: The MIMO detector of LAMA: the hard decisions of the decoupled channel, its bit LLRs, and its estimates $z$ with the variance of the decoupled noise.
AmpThresholds: The thresholds of LAMA for a prior (Jeon et al., Definitions 6 to 9, Table II).
MessagePassing: The configuration shared by lama, oamp and their state evolutions: the prior of every entry of $x$, the domain of the model and the number of iterations.
Oamp: The MIMO detector of OAMP with the LMMSE estimator (the outputs of Amp).
StateEvolutionStep: One iteration of a state evolution.
Trace: The iterations of a message-passing detector.

Enums§

AmpVariance: How LAMA estimates the variance of the decoupled channel.
Domain: The number domain of the model: complex (circularly-symmetric noise) or real.
OampLinear: The linear estimator $\hat{W}$ of OAMP (Ma & Ping, eq. 15).
Prior: The prior of every entry of $x$.

Functions§

amp_state_evolution: The state evolution of LAMA without noise mismatch (Jeon et al., Corollary 2): $\sigma^{2}{1} = \sigma^{2} + \beta \mathrm{Var}[S]$, $\sigma^{2}{t+1} = \sigma^{2} + \beta \Psi(\sigma^{2}{t}, \sigma^{2}{t})$, for the iterations, prior and domain of config, with $\beta = N/M$ and the columns of $H$ of unit norm.
amp_thresholds: The minimum and exact recovery thresholds of LAMA and the critical noise variances (Jeon et al., eqs. 33 and 34, Definitions 8 and 9): $\beta_{\max} = \min_{\sigma^{2}} \sigma^{2} / \Psi(\sigma^{2}, \sigma^{2})$, $\beta_{\min} = \min_{\sigma^{2}} 1/\Psi’(\sigma^{2})$; the noise variances are $\sigma^{2} - \beta \Psi(\sigma^{2})$ where $\beta \Psi’(\sigma^{2}) = 1$.
lama: LAMA (Jeon et al., Algorithm 2) on $y = H x + w$, $w$ of variance noise_var per entry, with the prior, domain and iterations of config and the variance estimate variance: the columns of $H$ are first scaled to a unit mean norm (with $y$ and the noise variance), which leaves the problem unchanged.
oamp: OAMP (Ma & Ping, eqs. 19, 25 and 38, Lemma 1) on $y = H x + w$, $w$ of variance noise_var per entry, with the prior, domain and iterations of config, the linear estimator linear and the optimal divergence-free denoiser.
oamp_state_evolution: The empirical state evolution of OAMP with the optimal denoiser (Ma & Ping, eqs. 32 and 39): for the singular_values of $H$ ($N$ columns), from $v^{2}{0} = \mathrm{Var}[S]$, $\tau^{2}{t} = \Phi_{t}(v^{2}{t})$ (eq. 32), the MSE of $F$ is $\mathrm{mmse}{B}(\tau^{2}{t})$ and $v^{2}{t+1} = (1/\mathrm{mmse}{B} - 1/\tau^{2}{t})^{-1}$, for the prior, domain and iterations of config and the linear estimator linear.