Pith. sign in

REVIEW 2 major objections 3 minor 51 references

Memory AMP: Overflow Avoidance, Complexity Reduction, and Comparative Analysis

T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read GD-MAMP can be made overflow-free and one-third cheaper without losing convergence speed.

desk verdict A solid engineering paper on MAMP variants: the overflow fix is clean and the WS-CG-VAMP(r) reformulation is useful, but the 'no notable degradation' claim for CR-GD-MAMP is oversold for moderate N and large condition numbers. read the letter →

arxiv 2608.08513 v1 pith:ZDFOUYTR submitted 2026-08-09 cs.IT eess.SPmath.ITmath.STstat.TH

Shunqi Huang , Lei Liu , Brian M. Kurkoski This is my paper · ORCID
classification cs.ITeess.SPmath.ITmath.STstat.TH
keywords approximatemessagepassingmemoryAMPgradientdescentMAMPoverflowavoidancecatastrophiccancellationwarm-startedconjugateVAMPmatrix-vectorcomplexitystateevolution
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper argues that the practical obstacles to using gradient-descent memory approximate message passing (GD-MAMP) for large ill-conditioned linear systems are removable, and that a fair comparison with its main competitor changes which algorithm wins. It first shows that GD-MAMP can overflow because intermediate quantities $w_t = \frac{1}{N}\operatorname{tr}\{A^H B^t A\}$ grow exponentially with the iteration count, and it constructs an equivalent overflow-avoiding form, OA-GD-MAMP. It then reduces the per-iteration matrix-vector products from three to two (CR-GD-MAMP), introduces a partial-memory variant that cuts storage, and shows empirically that convergence speed is barely affected. Finally, it embeds MAMP design in a general gradient-based formulation, recovers WS-CG-VAMP as the conjugate-gradient special case, and identifies catastrophic cancellation in the orthogonalization parameters as the reason WS-CG-VAMP diverges in double precision. If these claims hold, large-scale signal recovery on poorly conditioned matrices becomes cheaper and numerically stable, and algorithm choice should depend on condition number.

What carries the argument

The machinery is a gradient-based MAMP template: each outer iteration solves a strongly convex quadratic $F_t(u)$ whose minimizer is $W_t^{-1} z_t$, with inner iterations governed by coefficients $\eta_t^{(i)},\beta_t^{(i)},\theta_t^{(i)},\alpha_t^{(i)}$; specializing them reproduces GD, NAG, or CG. The load-bearing identities are the product pairing $\vartheta_{t,i} w_{t-i} = \operatorname{sgn}(\cdot)e^{\log|\cdot|} \chi_{t-i}$ with $\chi_k=\theta_0^k w_k$ bounded by $\delta(\lambda^\dagger+\theta_0^{-1})$, the finite-$N$ covariance estimate in Lemma 6, and the cancellation factor $C_{t,k}$ that turns the floating-point roundoff bound into $(J_{t,k}+1)u_{\mathrm{fp}} C_{t,k}$. These identities turn an overflow-prone, three-product algorithm into a stable two-product one, and turn an unexplained double-precision divergence into a quantified error.

What would settle it

Run CR-GD-MAMP on a right-unitarily invariant matrix with $N=4096$, $M=2048$, a Bernoulli-Gaussian prior, SNR 35 dB, and condition number 500, and compare terminal MSE with GD-MAMP and the Bayesian optimum; the paper's Fig. 4 predicts a visible gap. Alternatively, compute the cancellation factor $C_{t,k}$ for WS-CG-VAMP at $\kappa=500$ under IEEE double precision; if $(J_{t,k}+1)u_{\mathrm{fp}}C_{t,k}\ll 1$ for all $t,k$, then catastrophic cancellation cannot be the cause of divergence.

Watch

Extended reading notes

Core claim

The central discovery is that the apparent numerical and complexity barriers of GD-MAMP are structural, not fundamental. The overflow comes from computing $w_k$ and the weights $\vartheta_{t,i}$ separately, when only their product $\vartheta_{t,i} w_{t-i}$ is needed; by computing the bounded quantity $\chi_k = \theta_0^k w_k$ in the log domain, OA-GD-MAMP stays equivalent to GD-MAMP yet never overflows. On complexity, the covariance matrix $\mathbf{V}_t^{\phi}$ of past estimates can be replaced by a single variance term plus a real-part estimate $\Re(v^\gamma_{t,i}) = \frac{1}{2}(v^\gamma_{t,t}+v^\gamma_{i,i}-\|r_t-r_i\|^2/N)$, which removes one matrix-vector product per iteration and yields CR-GD-MAMP. The paper also establishes that every gradient-based MAMP algorithm has Krylov-type polynomial representations of its iterates, that WS-CG-VAMP is precisely the CG instance, and that the orthogonalization parameters are sums of large positive and negative terms; the cancellation factor $C_{t,k}$ in Lemma 10 bounds the relative roundoff error, explaining why finite-precision WS-CG-VAMP diverges. The reformulation WS-CG-VAMP(r) eliminates redundant products, reducing $2I+4$ to $2I+1$ per outer iteration.

Load-bearing premise

For CR-GD-MAMP the load-bearing premise is that the variance estimate $\Re(v^\gamma_{t,i}) \approx \frac{1}{2}(v^\gamma_{t,t}+v^\gamma_{i,i}-\|r_t-r_i\|^2/N)$ and the damping vector built from it stay accurate at finite $N$; the paper's Fig. 4 shows this assumption can fail when $N=4096$ and the condition number exceeds about 300.

Editorial extensions

If this is right

  • Ill-conditioned systems with condition numbers around 1000 can be recovered with GD-MAMP in double precision without crashing, a regime where the original algorithm overflows.
  • CR-GD-MAMP reaches the same MSE with about one-third fewer matrix-vector products (from $3T$ to $2T$, or $5T$ to $3T$ when eigenvalues are unknown), so large-scale AMP-type recovery becomes cheaper.
  • A partial-memory variant needs to store only about 40–50% of the memory terms, cutting storage by 50–60% while retaining the same convergence for well-chosen $l$.
  • WS-CG-VAMP falls inside the MAMP family, its double-precision divergence is explained by catastrophic cancellation, and the equivalent WS-CG-VAMP(r) uses up to 50% fewer matrix-vector products, though large condition numbers still demand high-precision arithmetic.
  • Algorithm choice becomes condition-number-dependent: GD-MAMP wins for small $\kappa$, while WS-CG-VAMP(r) wins for large $\kappa$ only under high precision.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Beyond the paper, the finite-$N$ failure in Fig. 4 suggests a testable design rule: switch CR-GD-MAMP's real-part damping to the heuristic $\zeta_t^{\mathrm{he}}$ when $N$ is below a few thousand and $\kappa$ is large, and map the threshold empirically.
  • The general gradient formulation opens a design space beyond GD and CG; choosing Nesterov-style coefficients inside the MAMP template could yield algorithms with intermediate convergence and precision behavior, though the paper does not test this.
  • Because the overflow fix works by keeping products bounded in the log domain, the same technique may apply to other message-passing or moment-based recursions where exponentially growing intermediates appear.
  • A head-to-head comparison of GD-MAMP and the rotationally-invariant AMP variants of [37] with optimized damping enabled would test whether the reported slower convergence of GD-MAMP is an artifact of disabled damping.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies GD-MAMP, an AMP-type algorithm for right-unitarily invariant linear systems, and makes four contributions. First, it diagnoses an overflow failure caused by intermediate quantities w_t growing exponentially when the conditioning is poor, and it proposes OA-GD-MAMP, which computes the relevant products without forming w_t explicitly; with known eigenvalues this is algebraic and is claimed to be equivalent to GD-MAMP. Second, it proposes two reduced-complexity variants: a partial-memory GD-MAMP that reduces storage, and CR-GD-MAMP that reduces the number of matrix-vector products per iteration from three to two; the paper claims neither degrades convergence speed notably. Third, it develops a general gradient-based formulation for MAMP algorithms that recovers GD, NAG, and WS-CG-VAMP as special cases, with polynomial coefficient recurrences in Lemma 9. Fourth, it analyzes finite-precision instability of WS-CG-VAMP through a cancellation factor and a relative roundoff bound (Lemma 10), and proposes an equivalent reformulation WS-CG-VAMP(r) using 2I+1 matrix-vector products instead of 2I+4. The claims are supported by algebraic proofs for the OA reformulation and the roundoff bound, and by simulations for the complexity-reduced variants.

Significance. If the algebraic claims hold, the paper provides a genuinely useful fix: OA-GD-MAMP removes an overflow mode that crashes GD-MAMP on large condition numbers while preserving the algorithm's iterate trajectory. The roundoff-error analysis in Section V-B, and especially the cancellation-factor bound in Lemma 10, is a valuable explanation of the known instability of WS-CG-VAMP. The general gradient-based MAMP formulation in Section V-A is also a useful organizational framework, and the WS-CG-VAMP(r) reformulation is a concrete complexity reduction. The main weakness is that the headline no-degradation claim for CR-GD-MAMP is not backed by a finite-N guarantee and is contradicted by the paper's own Fig. 4 in a regime the abstract does not exclude. The OA-GD-MAMP equivalence and the two-MVP reformulation themselves appear internally sound; the principal gap is in the scope of the convergence-claim wording.

major comments (2)
  1. [Abstract and Section IV-A, Eq. (50), Fig. 4] The claim that CR-GD-MAMP 'does not degrade the convergence speed notably' is stated without a finite-N or condition-number qualification, but the only mechanism preserving its convergence speed is the heuristic damping in Eq. (50) built from the empirical covariances of Lemma 6. No state-evolution or finite-N guarantee is given that this estimated damping is close to the optimal damping, and the paper's own Fig. 4 shows that for N=4096 and κ>300 CR-GD-MAMP no longer reaches the Bayesian optimum while GD-MAMP does. Since this is one of the paper's headline contributions, the claim must be restricted to the regime actually supported or supplemented with a criterion for predicting when Eq. (50) is reliable.
  2. [Section IV-B, Eqs. (55)-(58), Fig. 2] The partial-memory variant's convergence claim is conditional on a suitable choice of the length parameter ℓ, but no principled selection procedure is given. The text suggests setting ℓ through state evolution or to 40%-50% of the maximum number of iterations, which requires knowing T in advance, and Fig. 2 shows that GD-MAMP-P diverges for ℓ<18 at κ=100. The storage-saving claim in the abstract ('one replaces full-length memory with partial memory ... Neither degrades the convergence speed notably') is therefore not supported as stated; the paper should state the dependence of the convergence behavior on ℓ and provide a practical rule that does not presuppose the final iteration count.
minor comments (3)
  1. [Section III-B, Eq. (31a)] Equation (31a) is difficult to parse as typeset: the element-wise exponent and log terms are not clearly delimited, and the notation e^{∘(...)} is used without being defined in Section II-D. Please rewrite the formula with unambiguous element-wise operations.
  2. [Appendix A, Algorithm 1, line 22] The pseudocode for the damping vector contains unbalanced parentheses and missing delimiters: the expression for ζ_{t+1} should be written as (V^{-1} 1) / (1^T V^{-1} 1) with explicit parentheses.
  3. [Section VI-B, Fig. 4] The figure legend appears to contain two identical 'CR-GD-MAMP' entries and does not explicitly show a GD-MAMP curve, even though the text says GD-MAMP reaches the Bayesian optimum in the failing regime. Please label the two marker sets by N and add the GD-MAMP curve or clarify the comparison in the caption.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the new equivalences, roundoff bound, and reformulations are derived from the stated update rules and floating-point model, not from fitted values or self-citation.

full rationale

The paper's central new results are self-contained derivations. OA-GD-MAMP's equivalence to GD-MAMP follows algebraically from Lemma 3 and the identities chi_k = theta_0^k w_k and vartheta_{t,i} w_{t-i} = sgn(...) exp(...) chi_{...}; Lemmas 4 and 5 supply bounds and estimates without invoking the target conclusion. The CR-GD-MAMP damping in Eq. (50) is explicitly labeled heuristic ('we replace it with a heuristically selected parameter', Eq. (45); 'this replacement is an approximation' for complex systems), and its finite-N limitation is disclosed in Fig. 4, so the no-degradation claim is an empirical claim with stated scope, not a fitted-input prediction. The roundoff bound in Lemma 10 follows from the standard floating-point model and the cancellation factor C_{t,k}. The recovery of WS-CG-VAMP as a CG specialization of the general gradient formulation is a mathematical identification, not a renaming of a known result. Self-citations to [24], [32], [47], and [48] supply the prior GD-MAMP/MAMP framework, a variance-estimation technique, and damping inspiration; none of the paper's new predictions or equivalences reduces to those citations. The main weakness is a correctness and finite-N scope gap for CR-GD-MAMP at N=4096 and kappa>300, which is a validity concern rather than circularity.

Assumptions & free parameters 3 free parameters · 6 assumptions · 0 invented entities

The ledger is clean: the paper introduces no unexplained physical or structural entities and no constants fitted to a target result. The main hand-set values are algorithmic hyperparameters L, l, and tau. All theorems assume the standard right-unitary MAMP setting.

free parameters (3)
  • Maximum damping length L = 3 (paper says L=2 or L=3)
    Used in all simulations; controls convergence robustness and affects all variants, but no criterion fixes its value.
  • Partial-memory length l (via l_t = max(1,t-l+1)) = 22 for kappa=100, 120 for kappa=1000
    Selected from the same convergence curves in Fig. 2 to preserve GD-MAMP convergence; the proposed 40-50% of T rule is a heuristic based on two observed settings.
  • Moment order tau for lambda_up_max estimate = tau <= 20 (small constant)
    Balances tightness of the upper bound on lambda_max against added matrix-vector products; no principled selection rule is provided.
assumptions (6)
  • domain assumption Assumption 1: IID zero-mean unit-variance signal x with finite (2+i)-th moments.
    Needed for state evolution and MSE analysis; stated at the start of Section II-A.
  • domain assumption Assumption 2: proportional-growth large-system limit and right-unitary invariance of A.
    Core setting inherited from MAMP [24]; all theorems use it.
  • domain assumption Known extremal eigenvalues and moments of AA^H, or approximation via (4)-(6).
    OA-GD-MAMP with known eigenvalues uses them directly; the unknown case relies on stochastic approximations with no finite-N guarantee.
  • domain assumption Asymptotic Gaussianity (Lemma 1) from [19], [23].
    Used to justify covariance tracking and state evolution; taken from prior work, not re-proved.
  • standard math Standard floating-point arithmetic model with unit roundoff u_fp.
    Used in Lemma 10 for the catastrophic-cancellation bound.
  • domain assumption Invertibility and conditioning assumptions on covariance matrices in Sections II-C and IV-A.
    Damping and orthogonalization require invertible V or Re(V); the paper adds diagonal loading or back-off if violated.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Memory AMP: Overflow Avoidance, Complexity Reduction, and Comparative Analysis." pith.science (2026). https://pith.science/paper/ZDFOUYTR

@misc{pith2026260808513,
  author       = {Pith},
  title        = {Pith review of: Memory AMP: Overflow Avoidance, Complexity Reduction, and Comparative Analysis},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZDFOUYTR}},
  note         = {Machine review of arXiv:2608.08513}
}
abstract

Approximate message passing (AMP)-type algorithms are widely used for signal recovery in high-dimensional noisy linear systems. Recently, a framework called memory AMP (MAMP) was introduced, offering a new approach to incorporating memory terms within AMP algorithms. Building on this, a low-complexity gradient descent MAMP (GD-MAMP) was proposed for right-unitarily invariant matrices. In this paper, we first address an overflow problem in GD-MAMP caused by intermediate variables exceeding the floating-point range, which typically occurs when the condition number is large. Second, we propose two low-complexity variants of GD-MAMP: one replaces full-length memory with partial memory, while the other reduces the number of matrix-vector products per iteration by $1/3$ (from three to two). Neither degrades the convergence speed notably. Third, we develop a general gradient-based formulation for designing MAMP algorithms. This formulation recovers warm-started conjugate gradient VAMP (WS-CG-VAMP) as a special case. Furthermore, we show that the computation of the orthogonalization parameters in this formulation can suffer from catastrophic cancellation, which explains the finite-precision instability of WS-CG-VAMP. Finally, we derive an equivalent reformulation, termed WS-CG-VAMP(r), which reduces the number of matrix-vector products by up to $50\%$. Measured by matrix-vector products, GD-MAMP converges faster for small condition numbers, whereas WS-CG-VAMP(r) converges faster for large ones under high-precision arithmetic but may diverge in IEEE double precision due to catastrophic cancellation.

Figures

Figures reproduced from arXiv: 2608.08513 by the authors.

Figure 1
Figure 1. In (a), |wk| exceeds the maximum value of FP64 numbers when k is large, leading to the overflow of GD-MAMP in (b). In contrast, OA-GD-MAMP avoids this overflow problem and works well. M = 8192, N = 16384, µ = 0.1, SNR = 35 dB, κ = 1000, L = 3. (approximately 1.8 × 10308), leading to the overflow problem. This explains the crash of GD￾MAMP at t = 137 in [PITH_FULL_IMAGE:figures/full_fig_p031_1.png] view at source ↗
Figure 2
Figure 2. If ℓ is suitable (e.g. ℓ = 22 in (a) and ℓ = 120 in (b)), GD-MAMP-P saves the storage of (T − ℓ)N floating numbers while keeping the same convergence as GD-MAMP. M = 8192, N = 16384, µ = 0.1, SNR = 35 dB, L = 3. 0 200 400 600 800 1000 Number of matrix-vector products 10-4 10-3 10-2 10-1 100 MSE GD-MAMP CR-GD-MAMP 10-3 10-2 10-1 100 Runtime (s) 10-4 10-3 10-2 10-1 100 MSE AMP GD-MAMP CR-GD-MAMP IID Gaussian matrix = … view at source ↗
Figure 3
Figure 3. In (a), CR-GD-MAMP saves nearly 1/3 matrix-vector products while keeping the similar convergence as GD-MAMP. In (b), the runtime of CR-GD-MAMP is the same as that of AMP (for IID Gaussian A), and only 2/3 the runtime of GD-MAMP. M = 0.5N, µ = 0.1, SNR = 35 dB, L = 3. same point as GD-MAMP with about 2/3 the number of matrix-vector products, supporting our analysis in Section IV-A [PITH_FULL_IMAGE:figures/full_fig_p… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: When κ is large and N is not large enough, CR-GD-MAMP may not converge to the same performance as GD-MAMP. N ∈ {4096, 16384}, M = 0.5N, µ = 0.1, SNR = 35 dB, L = 3. 0 10 20 30 40 50 60 70 80 90 Number of matrix-vector products 10-4 10-3 10-2 10-1 100 MSE GD-MAMP WS-CG …
Figure 5
Figure 5. Figure 5: WS-CG(r) is the short of reformulated WS-CG-VAMP. In (a), GD-MAMP converges faster than WS-CG(r) when [PITH_FULL_IMAGE:figures/full_fig_p033_5.png]
Figure 6
Figure 6. Figure 6: WS-CG(vpa)/(app) denotes WS-CG-VAMP with high-precision arithmetic and the approximation method in [32], [PITH_FULL_IMAGE:figures/full_fig_p034_6.png]
Figure 7
Figure 7. Figure 7: WS-CG(vpa) denotes WS-CG-VAMP with high-precision arithmetic. The practical time cost of WS-CG(vpa) is much [PITH_FULL_IMAGE:figures/full_fig_p034_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

51 extracted references · 48 canonical work pages

  1. [1]

    Overflow-avoiding memory AMP,

    S. Huang, L. Liu, and B. M. Kurkoski, “Overflow-avoiding memory AMP,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2024, pp. 3516–3521

    work page 2024

  2. [2]

    Optimum multiuser signal detection (Ph.D. Abstr.),

    S. Verd ´u, “Optimum multiuser signal detection (Ph.D. Abstr.),”IEEE Trans. Inf. Theory, vol. 31, no. 4, p. 557, Jul. 1985

    work page 1985

  3. [3]

    The hardness of the closest vector problem with preprocessing,

    D. Micciancio, “The hardness of the closest vector problem with preprocessing,”IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 1212–1215, Mar. 2001

    work page 2001

  4. [4]

    Message-passing algorithms for compressed sensing,

    D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,”Proc. Natl. Acad. Sci. U.S.A., vol. 106, no. 45, pp. 18 914–18 919, Nov. 2009

    work page 2009

  5. [5]

    The dynamics of message passing on dense graphs, with applications to compressed sensing,

    M. Bayati and A. Montanari, “The dynamics of message passing on dense graphs, with applications to compressed sensing,” IEEE Trans. Inf. Theory, vol. 57, no. 2, pp. 764–785, Feb. 2011

    2011

  6. [6]

    The replica-symmetric prediction for random linear estimation with Gaussian matrices is exact,

    G. Reeves and H. D. Pfister, “The replica-symmetric prediction for random linear estimation with Gaussian matrices is exact,”IEEE Trans. Inf. Theory, vol. 65, no. 4, pp. 2252–2283, Apr. 2019. 42

    work page 2019

  7. [7]

    Mutual information and optimality of approximate message-passing in random linear estimation,

    J. Barbier, N. Macris, M. Dia, and F. Krzakala, “Mutual information and optimality of approximate message-passing in random linear estimation,”IEEE Trans. Inf. Theory, vol. 66, no. 7, pp. 4270–4303, Jul. 2020

    work page 2020

  8. [8]

    Capacity optimality of AMP in coded systems,

    L. Liu, C. Liang, J. Ma, and L. Ping, “Capacity optimality of AMP in coded systems,”IEEE Trans. Inf. Theory, vol. 67, no. 7, pp. 4429–4445, Jul. 2021

    work page 2021

Show all 51 references
  1. [9]

    Sparse estimation with the swept approximated message-passing algorithm,

    A. Manoel, F. Krzakala, E. W. Tramel, and L. Zdeborov ´a, “Sparse estimation with the swept approximated message-passing algorithm,”arXiv preprint arXiv:1406.4311, 2014

    2014 arXiv

  2. [10]

    Adaptive damping and mean removal for the generalized approximate message passing algorithm,

    J. Vila, P. Schniter, S. Rangan, F. Krzakala, and L. Zdeborov ´a, “Adaptive damping and mean removal for the generalized approximate message passing algorithm,” inProc. IEEE Int. Conf. Acoust., Speech Signal Process. (ICASSP), Apr. 2015, pp. 2021–2025

    2015

  3. [11]

    Inference for generalized linear models via alternating directions and Bethe free energy minimization,

    S. Rangan, A. K. Fletcher, P. Schniter, and U. S. Kamilov, “Inference for generalized linear models via alternating directions and Bethe free energy minimization,”IEEE Trans. Inf. Theory, vol. 63, no. 1, pp. 676–697, Jan. 2017

    2017

  4. [12]

    Orthogonal AMP,

    J. Ma and L. Ping, “Orthogonal AMP,”IEEE Access, vol. 5, pp. 2020–2033, Jan. 2017

    2020

  5. [13]

    Vector approximate message passing,

    S. Rangan, P. Schniter, and A. K. Fletcher, “Vector approximate message passing,”IEEE Trans. Inf. Theory, vol. 65, no. 10, pp. 6664–6684, Oct. 2019

    2019

  6. [14]

    Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariant measurements,

    K. Takeuchi, “Rigorous dynamics of expectation-propagation-based signal recovery from unitarily invariant measurements,” IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 368–386, Jan. 2020

    2020

  7. [15]

    The mutual information in random linear estimation beyond i.i.d. matrices,

    J. Barbier, N. Macris, A. Maillard, and F. Krzakala, “The mutual information in random linear estimation beyond i.i.d. matrices,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2018, pp. 1390–1394

    2018

  8. [16]

    Random linear estimation with rotationally-invariant designs: Asymptotics at high temperature,

    Y . Li, Z. Fan, S. Sen, and Y . Wu, “Random linear estimation with rotationally-invariant designs: Asymptotics at high temperature,”IEEE Trans. Inf. Theory, vol. 70, no. 3, pp. 2118–2153, Mar. 2024

    2024

  9. [17]

    On capacity optimality of OAMP: Beyond IID sensing matrices and Gaussian signaling,

    L. Liu, S. Liang, and L. Ping, “On capacity optimality of OAMP: Beyond IID sensing matrices and Gaussian signaling,” IEEE Trans. Commun., vol. 72, no. 5, pp. 2519–2535, May 2024

    2024

  10. [18]

    On OAMP: Impact of the orthogonal principle,

    L. Liu, Y . Cheng, S. Liang, J. H. Manton, and L. Ping, “On OAMP: Impact of the orthogonal principle,”IEEE Trans. Commun., vol. 71, no. 5, pp. 2992–3007, May 2023

    2023

  11. [19]

    A unified framework of state evolution for message-passing algorithms,

    K. Takeuchi, “A unified framework of state evolution for message-passing algorithms,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2019, pp. 151–155

    2019

  12. [20]

    Expectation propagation for approximate Bayesian inference,

    T. P. Minka, “Expectation propagation for approximate Bayesian inference,” inProc. 17th Conf. Uncertainty Artif. Intell. (UAI), Aug. 2001, pp. 362–369

    2001

  13. [21]

    Expectation consistent approximate inference,

    M. Opper and O. Winther, “Expectation consistent approximate inference,”J. Mach. Learn. Res., vol. 6, pp. 2177–2204, Dec. 2005

    2005

  14. [22]

    Expectation propagation for approximate inference: Free probability framework,

    B. C ¸ akmak and M. Opper, “Expectation propagation for approximate inference: Free probability framework,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2018, pp. 1276–1280

    2018

  15. [23]

    Bayes-optimal convolutional AMP,

    K. Takeuchi, “Bayes-optimal convolutional AMP,”IEEE Trans. Inf. Theory, vol. 67, no. 7, pp. 4405–4428, Jul. 2021

    2021

  16. [24]

    Memory AMP,

    L. Liu, S. Huang, and B. M. Kurkoski, “Memory AMP,”IEEE Trans. Inf. Theory, vol. 68, no. 12, pp. 8015–8039, Dec. 2022

    2022

  17. [25]

    Low-complexity memory AMP detector for high-mobility MIMO-OTFS SCMA systems,

    Y . Ge, L. Liu, S. Huang, Y . L. Guan, and Z. Ding, “Low-complexity memory AMP detector for high-mobility MIMO-OTFS SCMA systems,” inProc. IEEE Int. Conf. Commun. Workshops (ICC Workshops), May 2023, pp. 807–812

    2023

  18. [26]

    Joint activity-delay detection and channel estimation for asynchronous massive random access,

    X. Bian, Y . Mao, and J. Zhang, “Joint activity-delay detection and channel estimation for asynchronous massive random access,” inProc. IEEE Global Commun. Conf. (GLOBECOM), Dec. 2023, pp. 4939–4944

    2023

  19. [27]

    Interleave frequency division multiplexing,

    Y . Chi, L. Liu, Y . Ge, X. Chen, Y . Li, and Z. Zhang, “Interleave frequency division multiplexing,”IEEE Wirel. Commun. Lett., vol. 13, no. 7, pp. 1963–1967, Jul. 2024. 43

    1963

  20. [28]

    MAMP detector for AFDM under doubly dispersive channels,

    Y . Qi, H. Yin, Y . Tang, X. Y . Fu, and L. Liu, “MAMP detector for AFDM under doubly dispersive channels,” inProc. IEEE/CIC Int. Conf. Commun. China (ICCC Workshops), Aug. 2025, pp. 1–6

    2025

  21. [29]

    Random multiplexing,

    L. Liu, Y . Chi, S. Huang, and Z. Zhang, “Random multiplexing,”IEEE Trans. Inf. Theory, vol. 72, no. 4, pp. 2277–2306, Apr. 2026

    2026

  22. [30]

    Channel estimation in massive MIMO systems with orthogonal delay-Doppler division multiplexing,

    D. Wang, C. Huang, X. Yuan, S. Muhaidat, L. Liu, X. Chen, Z. Zhang, C. Yuen, and M. Debbah, “Channel estimation in massive MIMO systems with orthogonal delay-Doppler division multiplexing,”IEEE Trans. Wirel. Commun., vol. 25, pp. 4293–4308, 2026

    2026

  23. [31]

    Achievable rate and coding principle for MIMO multicarrier systems with cross-domain MAMP receiver over doubly selective channels,

    Y . Chi, Z. Peng, L. Liu, Y . Li, Y . Ge, and C. Yuen, “Achievable rate and coding principle for MIMO multicarrier systems with cross-domain MAMP receiver over doubly selective channels,”IEEE Trans. Wirel. Commun., vol. 25, pp. 10 354– 10 370, 2026

    2026

  24. [32]

    Compressed sensing with upscaled vector approximate message passing,

    N. Skuratovs and M. E. Davies, “Compressed sensing with upscaled vector approximate message passing,”IEEE Trans. Inf. Theory, vol. 68, no. 7, pp. 4818–4836, Jul. 2022

    2022

  25. [33]

    Warm-starting in message passing algorithms,

    ——, “Warm-starting in message passing algorithms,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), 2022, pp. 1187–1192

    2022

  26. [34]

    Approximate message passing algorithms for rotationally invariant matrices,

    Z. Fan, “Approximate message passing algorithms for rotationally invariant matrices,”Ann. Statist., vol. 50, no. 1, pp. 197–224, Feb. 2022

    2022

  27. [35]

    Estimation in rotationally invariant generalized linear models via approximate message passing,

    R. Venkataramanan, K. K ¨ogler, and M. Mondelli, “Estimation in rotationally invariant generalized linear models via approximate message passing,” inProc. 39th Int. Conf. Mach. Learn. (ICML), ser. Proc. Mach. Learn. Res., vol. 162. PMLR, Jul. 2022, pp. 22 120–22 144

    2022

  28. [36]

    Unifying AMP algorithms for rotationally-invariant models,

    S. Liu and J. Ma, “Unifying AMP algorithms for rotationally-invariant models,”arXiv preprint arXiv:2412.01574, 2024

    2024 arXiv

  29. [37]

    Rotationally-invariant AMP for compressed sensing with multiple measurement vectors,

    S. Luo, S. Liu, J. Ma, C. Xu, and X. Wang, “Rotationally-invariant AMP for compressed sensing with multiple measurement vectors,” inProc. IEEE Int. Conf. Acoust., Speech Signal Process. (ICASSP), May 2026, pp. 306–310

    2026

  30. [38]

    S. M. Kay,Fundamentals of Statistical Signal Processing, Vol. I: Estimation Theory. Upper Saddle River, NJ, USA: Prentice-Hall, 1993

    1993

  31. [39]

    Generalized approximate message-passing for compressed sensing with sublinear sparsity,

    K. Takeuchi, “Generalized approximate message-passing for compressed sensing with sublinear sparsity,”IEEE Trans. Inf. Theory, vol. 71, no. 6, pp. 4602–4636, Jun. 2025

    2025

  32. [40]

    Generalized orthogonal approximate message-passing for sublinear sparsity,

    ——, “Generalized orthogonal approximate message-passing for sublinear sparsity,”arXiv preprint arXiv:2512.03326, 2025

    2025 arXiv

  33. [41]

    Direct and converse theorems in estimating signals with sublinear sparsity,

    ——, “Direct and converse theorems in estimating signals with sublinear sparsity,”arXiv preprint arXiv:2601.14621, 2026

    2026 arXiv

  34. [42]

    Algebra of L-banded matrices,

    S. Huang, L. Liu, and B. M. Kurkoski, “Algebra of L-banded matrices,”IEEE Access, vol. 11, pp. 17 658–17 664, 2023

    2023

  35. [43]

    L-matrices with lacunary coefficients,

    L. Bouthat and J. Mashreghi, “L-matrices with lacunary coefficients,”Oper. Matrices, vol. 15, no. 3, pp. 1045–1053, 2021

    2021

  36. [44]

    The Hilbert L-matrix,

    F. ˇStampach, “The Hilbert L-matrix,”J. Funct. Anal., vol. 282, no. 8, p. 109401, 2022

    2022

  37. [45]

    Asymptotic spectral properties of the Hilbert L-matrix,

    ——, “Asymptotic spectral properties of the Hilbert L-matrix,”SIAM J. Matrix Anal. Appl., vol. 43, no. 4, pp. 1658–1679, 2022

    2022

  38. [46]

    On the convergence of orthogonal/vector AMP: Long-memory message-passing strategy,

    K. Takeuchi, “On the convergence of orthogonal/vector AMP: Long-memory message-passing strategy,”IEEE Trans. Inf. Theory, vol. 68, no. 12, pp. 8121–8138, Dec. 2022

    2022

  39. [47]

    Sufficient statistic memory approximate message passing,

    L. Liu, S. Huang, and B. M. Kurkoski, “Sufficient statistic memory approximate message passing,” inProc. IEEE Int. Symp. Inf. Theory (ISIT), Jun./Jul. 2022, pp. 1378–1383

    2022

  40. [48]

    Sufficient-statistic memory AMP,

    L. Liu, S. Huang, Y . Yang, Z. Zhang, and B. M. Kurkoski, “Sufficient-statistic memory AMP,”arXiv preprint arXiv:2112.15327, 2021

    2021 arXiv

  41. [49]

    Rigorous dynamics of expectation-propagation signal detection via the conjugate gradient method,

    K. Takeuchi and C.-K. Wen, “Rigorous dynamics of expectation-propagation signal detection via the conjugate gradient method,” inProc. IEEE Int. Workshop Signal Process. Adv. Wireless Commun. (SPAWC), Jul. 2017, pp. 1–5. 44

    2017

  42. [50]

    Spectral universality in regularized linear regression with nearly deterministic sensing matrices,

    R. Dudeja, S. Sen, and Y . M. Lu, “Spectral universality in regularized linear regression with nearly deterministic sensing matrices,”IEEE Trans. Inf. Theory, vol. 70, no. 11, pp. 7923–7951, Nov. 2024

    2024

  43. [51]

    Universality of approximate message passing algorithms and tensor networks,

    T. Wang, X. Zhong, and Z. Fan, “Universality of approximate message passing algorithms and tensor networks,”Ann. Appl. Probab., vol. 34, no. 4, pp. 3943–3994, Aug. 2024

    2024

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.