{"id":"2c263240-a5b7-48d9-9763-c363c60bef08","arxiv_id":"2608.08513","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Overflow-avoiding and reduced-complexity variants of memory AMP are derived, and the finite-precision divergence of warm-started CG-VAMP is traced to catastrophic cancellation in orthogonalization parameters.","lead":"This paper fixes overflow crashes in a message-passing signal recovery algorithm, cutting its per-iteration cost by a third. It also explains why a faster variant falls apart in ordinary computer arithmetic.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The no-degradation claim for CR-GD-MAMP is only asymptotic and empirical: the Section IV-A heuristic damping built on Lemma 6 and Eq. (50) has no finite-N guarantee, and the paper's own Fig. 4 contradicts it for N=4096, κ>300.","rationale":"The most load-bearing claim in the paper is the two-MVP CR-GD-MAMP variant, because the abstract promises no notable degradation in convergence speed. The weakest point is exactly the finite-N reliability of the variance/damping estimates: Lemma 6 provides a limit identity, but CR-GD-MAMP uses it as an online estimator, and Eq. (50) inverts the resulting noisy matrix ℜ(V^γ_t). The paper's own Fig. 4 shows a clear failure for N=4096 and κ>300, which is not a negligible corner case. This is a scope limitation, not an algebraic error; I checked the other main contributions: the χ_k/log-domain rewrites in Appendix A are algebraically consistent with the original c_t,i definitions, Lemma 4 bounds χ_k, Lemma 3 follows from the cyclic trace identity, the WS-CG-VAMP(r) recurrence in Eqs. (86)-(87) is an exact elimination of redundant matrix-vector products, and Lemma 10 is a standard forward roundoff bound. None of those parts has an internal inconsistency that I could identify. However, the abstract's no-degradation claim is broader than what is proven or shown, and the reader's weakest assumption correctly identifies this. I therefore agree with the CONDITIONAL verdict and see no reason to change it; the concern is real but does not invalidate the paper's more narrowly scoped contributions.","tokens_in":28033,"tokens_out":18711,"duration_ms":197726,"concrete_test":"Reproduce Fig. 4 with a parameter sweep: fix M=0.5N, μ=0.1, SNR=35 dB, L=3, and for each N in {2048, 4096, 8192, 16384} and κ in {200, 400, 600, 800}, run at least 20 independent realizations of CR-GD-MAMP and GD-MAMP, recording the final MSE. If CR-GD-MAMP's MSE gap to GD-MAMP decays with N at fixed κ, the failure is attributable to finite-N estimator noise in Lemma 6, and the no-degradation claim should be qualified with an explicit N/κ condition. Additionally, at N=4096 and κ=500, replace the online Lemma 6 estimates in Eq. (50) with the true ℜ(V^γ_t) obtained from long-run averages or state evolution; if the performance gap disappears, this isolates estimator variance as the cause of the degradation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's headline promise, stated in the Abstract and Section IV-A, is that CR-GD-MAMP reduces matrix-vector products from three to two per iteration 'without degrading the convergence speed notably.' This claim rests entirely on the quality of the MLE damping vector ζ̃_t = [ℜ(V^γ_t)]^{-1}1 / (1^T [ℜ(V^γ_t)]^{-1}1) in Eq. (50). That vector is built from Lemma 6's empirical estimator ℜ(v^γ_{t,i}) ≈ (v^γ_{t,t} + v^γ_{i,i} − ∥r_t − r_i∥²/N)/2. CR-GD-MAMP has discarded the full V^φ_t and the optimized ξ_t from Eq. (21), replacing it with the heuristic ξ̂_t in Eq. (45), so the damping quality is the sole mechanism preserving convergence speed. Unlike GD-MAMP, which has an SE-based convergence guarantee, CR-GD-MAMP has no finite-N or even asymptotic proof that this estimated damping is close enough to the true optimal damping. The paper itself documents the failure mode: Fig. 4 shows that for N=4096 and κ>300, CR-GD-MAMP no longer reaches the Bayesian optimum, while GD-MAMP does. The text's stated mitigation, ζ_t^he in Eq. (53), is recommended only for N<1000 and does not cover N=4096. Therefore, the unqualified 'neither degrades convergence speed notably' is not supported in a regime the abstract does not exclude. This is a scope and guarantee gap rather than an internal algebraic error; the OA-GD-MAMP equivalence and the two-MVP reformulation themselves appear internally consistent.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":28308,"tokens_out":5279,"duration_ms":57154,"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":[{"comment":"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.","section":"Abstract and Section IV-A, Eq. (50), Fig. 4"},{"comment":"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.","section":"Section IV-B, Eqs. (55)-(58), Fig. 2"}],"minor_comments":[{"comment":"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.","section":"Section III-B, Eq. (31a)"},{"comment":"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.","section":"Appendix A, Algorithm 1, line 22"},{"comment":"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.","section":"Section VI-B, Fig. 4"}],"recommendation":"major_revision","confidential_remarks":"The OA-GD-MAMP equivalence and the roundoff-bound analysis are sound and valuable, but the abstract's unqualified no-degradation claim for CR-GD-MAMP is contradicted by Fig. 4 at N=4096 and κ>300. The revision should require the authors to scope the claim explicitly and to address the finite-N reliability of Eq. (50). The partial-memory variant's parameter selection issue should also be resolved before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know: this paper fixes a real overflow bug in GD-MAMP and gives a cleaner two-matrix-vector-product variant. The algebraic core is sound. But the headline claim that CR-GD-MAMP does not degrade convergence speed is empirical and fails in a regime the abstract does not exclude.\n\nWhat is genuinely new: the overflow-avoiding reformulation (Lemmas 3-5) is elegant and correct, keeping intermediate variables bounded without changing the algorithm; the partial-memory variant is a useful storage trade-off; and the general gradient-based formulation is a nice unifying frame that recovers WS-CG-VAMP. The cancellation-factor analysis (Section V-B) is the most interesting part: it gives a quantitative mechanism for the finite-precision instability, and the reformulated WS-CG-VAMP(r) reduces matrix-vector products while keeping the same iteration count. That is real, reproducible mathematics.\n\nWhere it is soft: the no-degradation claim for CR-GD-MAMP rests on a heuristic damping built from Lemma 6, and there is no finite-N guarantee that the estimated real-part covariance is close enough to optimal. The paper itself shows the failure: Fig. 4, N=4096, kappa>300, CR-GD-MAMP no longer reaches the Bayesian optimum while GD-MAMP does. The suggested heuristic zeta_he in Eq. (53) is recommended only for N<1000, so it does not cover the demonstrated failure. The abstract and Section IV-A say 'neither degrades the convergence speed notably' without this caveat. That is an overstatement, not an internal error. Also, the partial-memory length l and damping length L are hand-chosen and partly fitted to the curves; no code or data is provided, so reproducing Figs. 1-7 takes effort.\n\nOverall: the OA-GD-MAMP equivalence and the WS-CG-VAMP(r) reformulation are sturdy, and the roundoff bound is a genuine contribution. The CR-GD-MAMP story is more of a heuristic with a documented edge case. A serious referee should ask for the abstract to be qualified, the failure regime disclosed, and ideally the code released.\n\nWho is this for: anyone working on AMP-type receivers or low-complexity linear estimation for ill-conditioned systems. It deserves a serious referee; accept for peer review.","headline":"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.","tokens_in":28959,"tokens_out":1320,"would_cite":false,"duration_ms":15137,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"GD-MAMP can be made overflow-free and one-third cheaper without losing convergence speed.","keywords":["approximate message passing","memory AMP","gradient descent MAMP","overflow avoidance","catastrophic cancellation","warm-started conjugate gradient VAMP","matrix-vector complexity","state evolution"],"falsifier":"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.","tokens_in":27710,"feed_emoji":"🧮","tokens_out":11684,"duration_ms":105776,"temperature":0.7,"pith_summary":"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.","feed_headline":"Memory AMP's overflow fixed, cost cut by a third","feed_subtitle":"A stable reformulation keeps convergence speed, and a rival's double-precision crashes get a cause.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the MAMP framework and the GD-MAMP algorithm that the paper modifies, simplifies, and compares against.","marker":"[24]"},{"why":"Introduces WS-CG-VAMP, the competing algorithm that the paper recovers as the CG special case and reformulates as WS-CG-VAMP(r).","marker":"[32]"},{"why":"Earlier conference version that first establishes the overflow-avoiding construction of OA-GD-MAMP.","marker":"[1]"},{"why":"Supplies the L-matrix damping structure and the variance-damping techniques that CR-GD-MAMP adapts to the MLE side.","marker":"[48]"},{"why":"Provides the recent RI-AMP/RIAMP-DF comparison that motivates the fair, damping-enabled convergence comparison for GD-MAMP.","marker":"[37]"},{"why":"Supports the spectral universality class used to generate the non-unitarily-invariant simulation matrix in the experiments.","marker":"[50]"}],"fun_headline_variants":["MAMP overflow fixed via log-domain, cost cut","Stable MAMP: partial memory and fewer products","Why WS-CG-VAMP fails in double precision, and the fix","MAMP matrix products from three to two, no slowdown","Overflow-free MAMP: two products per iteration"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["MAMP overflow fixed via log-domain, cost cut","Stable MAMP: partial memory and fewer products","Why WS-CG-VAMP fails in double precision, and the fix","MAMP matrix products from three to two, no slowdown","Overflow-free MAMP: two products per iteration"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001211,"raw_usage":{"total_tokens":5079,"prompt_tokens":1130,"completion_tokens":3949,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":746,"completion_tokens_details":{"reasoning_tokens":3868}},"tokens_in":746,"tokens_out":3949,"duration_ms":29913,"temperature":1.0,"reasoning_tokens":3868,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:33:37.863445+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Memory AMP,","cited_arxiv_id":null,"evidence_quote":"Defines the MAMP framework and the GD-MAMP algorithm that the paper modifies, simplifies, and compares against."},{"cited_title":"Compressed sensing with upscaled vector approximate message passing,","cited_arxiv_id":null,"evidence_quote":"Introduces WS-CG-VAMP, the competing algorithm that the paper recovers as the CG special case and reformulates as WS-CG-VAMP(r)."},{"cited_title":"Overflow-avoiding memory AMP,","cited_arxiv_id":null,"evidence_quote":"Earlier conference version that first establishes the overflow-avoiding construction of OA-GD-MAMP."},{"cited_title":"Sufficient-Statistic Memory AMP","cited_arxiv_id":"2112.15327","evidence_quote":"Supplies the L-matrix damping structure and the variance-damping techniques that CR-GD-MAMP adapts to the MLE side."},{"cited_title":"Rotationally-invariant AMP for compressed sensing with multiple measurement vectors,","cited_arxiv_id":null,"evidence_quote":"Provides the recent RI-AMP/RIAMP-DF comparison that motivates the fair, damping-enabled convergence comparison for GD-MAMP."},{"cited_title":"Spectral universality in regularized linear regression with nearly deterministic sensing matrices,","cited_arxiv_id":null,"evidence_quote":"Supports the spectral universality class used to generate the non-unitarily-invariant simulation matrix in the experiments."}],"review_version":1}