Exercises

$\mathbf{A}$ is RRI iff $\mathbf{V}$ is Haar-distributed on the unitary group, independently of $\mathbf{U}$ and $\boldsymbol{\Lambda}$.

Inside RRI: (i) i.i.d. Gaussian matrices; (ii) random sub-sampled DFT / Hadamard matrices. Outside RRI: a deterministic Vandermonde matrix with fixed nodes.

(1) $\mathrm{tr}(\mathbf{W}_t\mathbf{A}) = N$ makes the linear step unity-gain on $\mathbf{x}$. (2) Subtracting $\langle\eta'\rangle\mathbf{r}_t$ kills the input bias of $\eta_t$ (divergence-free denoiser). (3) $C_t = 1/(1 - \langle\eta'\rangle)$ restores unit gain on $\mathbf{x}$ after the subtraction.

$g_{\text{out}}(y,\hat{z},\tau_p)$ is determined by the per- element likelihood $p(y|z)$ and the current state $\tau_p$.

$g_{\text{out}}(y,\hat{z},\tau_p) = \frac{y-\hat{z}}{\sigma^2+\tau_p}$, a simple scaled residual.

$\mathbf{W}_t = \mathbf{A}^{\mathsf{H}}/L$, $\mathbf{S}_t = \mathbf{I} - \mathbf{A}^{\mathsf{H}}\mathbf{A}/L$, $\lambda_t = \lambda/L$, where $L$ is the Lipschitz constant of the gradient, $L = \|\mathbf{A}\|_2^2$.

The ISTA init is provably convergent and gives the network a meaningful starting point. Random init typically fails to recover any convergent behaviour even after long training — the loss landscape has many bad basins at random points.

$\mathbf{A}\mathbf{A}^{\mathsf{H}} = (N/M)\mathbf{S}\mathbf{F}\mathbf{F}^{\mathsf{H}}\mathbf{S}^{\mathsf{H}} = (N/M)\mathbf{S}(N\mathbf{I}_N)\mathbf{S}^{\mathsf{H}}/N$. Since $\mathbf{S}\mathbf{S}^{\mathsf{H}} = \mathbf{I}_M$ (rows are distinct standard basis vectors), this equals $(N/M)\mathbf{I}_M$.

$\hat{\mathbf{W}}_t = \mathbf{A}^{\mathsf{H}}((N/M)\mathbf{I}_M + (\sigma^2/v_t)\mathbf{I}_M)^{-1} = \alpha_t \mathbf{A}^{\mathsf{H}}$ with $\alpha_t = 1/((N/M)+\sigma^2/v_t)$.

$\mathrm{tr}(\hat{\mathbf{W}}_t\mathbf{A}) = \alpha_t\cdot M\cdot(N/M) = \alpha_t N$, so $C_t = N/(\alpha_t N) = 1/\alpha_t$ and $\mathbf{W}_t = \mathbf{A}^{\mathsf{H}}$ scaled to satisfy the trace constraint.

$(\mathbf{A}_1\otimes\mathbf{A}_2)\mathrm{vec}(\mathbf{X}) = \mathrm{vec}(\mathbf{A}_2\mathbf{X}\mathbf{A}_1^{\mathsf{T}})$. One direction: the $(i,j)$ entry of both sides coincides.

Reshape $\mathbf{x} = \mathrm{vec}(\mathbf{X})$. The linear step $\ntn{obs}-\mathbf{A}\hat{\mathbf{x}}_t$ becomes $\mathbf{Y} - \mathbf{A}_2\hat{\mathbf{X}}_t\mathbf{A}_1^{\mathsf{T}}$ (reshaped). The Kronecker LMMSE exploits the diagonal structure in the per-factor SVD bases.

$\mathbb{E}[\mathbf{z}^{\mathsf{T}}\mathbf{M}\mathbf{z}] = \sum_{i,j}M_{ij}\mathbb{E}[z_i z_j] = \sum_i M_{ii} = \mathrm{tr}(\mathbf{M})$.

For Rademacher $\mathbf{z}$, $\mathrm{Var}(\mathbf{z}^{\mathsf{T}}\mathbf{M}\mathbf{z}) = 2\sum_{i\ne j}M_{ij}^2 = 2(\|\mathbf{M}\|_F^2 - \sum_i M_{ii}^2)$. With $K$ probes, the estimator has variance $O(K^{-1}\|\mathbf{M}\|_F^2)$.

The non-zero squared singular values $\lambda_i^2$ of $\mathbf{A}$ concentrate on the MP support $[(1-\sqrt{\delta})^2, (1+\sqrt{\delta})^2]$ with $\delta = M/N$. In the large-$N$ limit the spectrum has fixed shape.

$\hat{\mathbf{W}}_t = \mathbf{A}^{H}(\mathbf{A}\mathbf{A}^{H} + (\sigma^2/v_t)\mathbf{I})^{-1}$. Diagonalizing in the SVD basis, each squared singular value is mapped to $\lambda_i/(\lambda_i^2+\sigma^2/v_t)$. For flat MP spectra this averages to a scalar, yielding $\mathbf{W}_t = c\cdot\mathbf{A}^{H}$.

Plugging this back and applying the trace-normalization $\mathrm{tr}(\mathbf{W}_t\mathbf{A}) = N$ gives exactly the AMP matched filter in the asymptotic limit.

$p(z|y,\hat{z},\tau_p) \propto \mathcal{N}(z;\hat{z},\tau_p)\Phi(y\cdot z/\sigma_w)$. This is a truncated-Gaussian with mean $\mathbb{E}[z|y] = \hat{z} + y\cdot\tau_p\phi(\hat{z}/s)/(s\Phi(y\hat{z}/s))$.

$g_{\text{out}}(y,\hat{z},\tau_p) = (\mathbb{E}[z|y] - \hat{z})/\tau_p = y\cdot\phi(\hat{z}/s)/(s\Phi(y\hat{z}/s))$. Bounded as $|\hat{z}|\to\infty$ (saturation), reflecting that a 1-bit measurement carries at most 1 bit of information.

At a VAMP fixed point the marginal means and variances $(\hat{\mathbf{x}}_k, \gamma_k)$ from the two factors agree: $\hat{\mathbf{x}}_1 = \hat{\mathbf{x}}_2$ and $\gamma_1 = \gamma_2$. The update recursions iterate toward this consistency.

The prior-factor update is the Onsager-free denoiser; the likelihood-factor update is the LMMSE step. Across the two factors the Onsager correction manifests as the extrinsic- information subtraction in message passing — identical to OAMP's divergence-free normalization.

For non-i.i.d. matrices the correct Onsager factor depends on the matrix spectrum in a complicated way. A learned scalar $b_t$ discovers the effective feedback gain from data, bypassing the analytical formula.

Trained on i.i.d. Gaussian data, $b_t$ converges to the AMP value $\delta^{-1}\langle\eta'\rangle$ and LAMP reduces to plain AMP with learned step sizes / denoiser parameters.

$\langle\tilde{\eta}_t(\mathbf{r})-\mathbf{x},\mathbf{r}-\mathbf{x}\rangle = \langle C_t\eta_t(\mathbf{r})-C_t\langle\eta_t'\rangle\mathbf{r}-\mathbf{x},\tau\mathbf{z}\rangle$.

Componentwise, $\mathbb{E}[z_i\eta_t(r_i)] = \tau\mathbb{E}[\eta_t'(r_i)]$. Similarly $\mathbb{E}[z_i r_i] = \tau$. Summing and dividing by $N$ gives $\tau[C_t\langle\eta_t'\rangle - C_t\langle\eta_t'\rangle] = 0$.

The subtraction of $\langle\eta_t'\rangle\mathbf{r}$ is exactly what cancels the first-order Stein term. Orthogonality holds independently of $C_t$ (which only affects gain).

Per coordinate, the posterior variance is $\lambda^2/(\lambda^2+\sigma^2/v_t)$. Averaging over $\mu$ gives $\eta^{-1}$-like integrals.

$\tau_t^2 = \frac{1}{\delta}\cdot\frac{v_t\cdot\eta(v_t/\sigma^2)}{1-\eta(v_t/\sigma^2)}$, closing the recursion with $v_{t+1} = \mathcal{E}(\tau_t^2;p_X)$.

Maximize $-\frac{(z-\hat{z})^2}{2\tau_p} - e^z + y z$ over $z$ to get $z^\star$ satisfying $e^{z^\star} = y - (z^\star-\hat{z})/\tau_p$. Solve iteratively; the second derivative gives the posterior variance.

$g_{\text{out}}(y,\hat{z},\tau_p) = (z^\star - \hat{z})/\tau_p$ with Jacobian $-\partial_z g_{\text{out}} = 1/(\tau_p + e^{-z^\star})$.

The denoiser's gradient $e^{z^\star}/(\text{something})$ can explode when $z^\star$ is large. Damping with $\beta\approx 0.5$ on the vector iterates $\hat{\mathbf{x}},\hat{\mathbf{s}}$ prevents the oscillations that would otherwise derail GAMP.

Set $\mathbf{W}_t = \alpha_t\mathbf{A}^{H}$, $\mathbf{S}_t = \mathbf{I}-\alpha_t\mathbf{A}^{H}\mathbf{A}$, $\lambda_t = \alpha_t\lambda$. This is ISTA with step $\alpha_t$.

Minimize the one-step contraction under the RIP bound to get $\alpha_t^\star = 1/(1+\delta_{2s})$ and $q^\star = 2\delta_{2s}/(1-\delta_{2s})<1$ when $\delta_{2s}<1/3$.

The full LISTA parameterization contains $\{\mathbf{W}_t,\mathbf{S}_t\}$ independent of $\alpha$, with many more degrees of freedom. Its training optimum thus dominates the scaled-ISTA bound, giving a strictly smaller contraction $q<q^\star$.

$\mathbf{A}^{H}\mathbf{A} = \mathbf{F}^H\mathbf{D}^H\mathbf{D}\mathbf{F} = \mathbf{F}^H\mathbf{F} = N\mathbf{I}_N$. The operator is an orthogonal $N\times N$ matrix up to scale.

$\hat{\mathbf{W}}_t = \mathbf{A}^{H}(\mathbf{A}\mathbf{A}^{H} + (\sigma^2/v_t)\mathbf{I})^{-1}$. But since $\mathbf{A}\mathbf{A}^{H} = N\mathbf{I}_M$, $\hat{\mathbf{W}}_t = \alpha_t\mathbf{A}^{H}$ with $\alpha_t = 1/(N+\sigma^2/v_t)$.

Per iteration: $\mathbf{A}\hat{\mathbf{x}}$ and $\mathbf{A}^{H}\mathbf{r}$ each cost $O(N\log N)$ (diagonal mod + FFT). Divergence-free normalization is scalar. Total: $O(N\log N)$ per iteration.

Run $T_{\text{learned}}$ LDVAMP layers, producing $\hat{\mathbf{x}}^{T_{\text{learned}}}$ and variance estimate $v^{T_{\text{learned}}}$. Initialize OAMP at this point and run $T_{\text{refine}}$ analytical iterations.

LDVAMP quickly reaches a low-MSE regime exploiting empirical priors and structured correlations. Within this regime OAMP's scalar state-evolution description applies, so the refinement pass enjoys predictable guarantees and removes residual bias due to training-set idiosyncrasies. The hybrid combines the adaptivity of learning with the robustness of analytical analysis.

One can bound the hybrid MSE by $\min(\mathrm{MSE}_{\text{LDVAMP}}, \mathcal{F}^{T_{\text{refine}}}(v^{T_{\text{learned}}}))$, showing the hybrid is no worse than either component up to constants that depend on the warm-start quality.