{"id":"a2f68d4b-010c-4c0d-be81-23dcf01cfc21","arxiv_id":"2412.01574","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The de-biasing coefficients of rotationally-invariant AMP are uniquely determined by a trace-free condition, and equal a polynomial in the divergence matrix with free-cumulant coefficients; two new AMP variants follow from the same template.","lead":"This paper gives a unified recipe for constructing Approximate Message Passing (AMP) algorithms on rotationally-invariant random matrices by rewriting them as orthogonal AMP algorithms and requiring certain matrix polynomials to have zero mean. The recipe rederives a known algorithm, explains its Onsager terms through free cumulants, and yields two new variants, one of which extends a recent Bayes-optimal algorithm to non-polynomial matrix functions.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The asserted convergence of the empirical divergence matrix \\hat Φ_t to its deterministic limit Φ_t is load-bearing and unproved; the inductive argument in Appendix C.3 is not closed.","rationale":"The reader identified the convergence of the empirical divergence matrix to its deterministic limit as the weakest assumption; my stress-test concurs. The algebraic reduction in Lemma 3 is rigorous, and Lemma 2's trace-free construction is well argued, but the passage from the random \\hat Φ_t to the deterministic Φ_t is the hinge on which the Gaussianity claim turns. Without a closed induction proving \\hat Φ_t → Φ_t, the OAMP state evolution cannot be applied to the random-coefficient denoisers defined in (46). I see no more load-bearing concern: Lemma 4 and the omitted state evolution for RI-AMP-MP are gaps in the generalized claims, but the paper's central 'any such algorithm has asymptotically Gaussian iterates' statement rests on Theorem 2, whose proof has the divergence-convergence gap. The paper's other contributions — the free-cumulant recursion in Proposition 1 and the derivation of the de-biasing matrix in Lemma 2 — appear internally consistent, and the numerical experiments, while lacking error bars, are not the source of the concern. Since the reader's CONDITIONAL verdict already reflects this gap, I recommend no change.","tokens_in":44538,"tokens_out":7302,"duration_ms":68514,"concrete_test":"Attempt to close the induction for t=2 and t=3 explicitly under Assumption 2. In particular, (i) prove \\langle ∂_1 η_2(r_1)\\rangle \\xrightarrow{P} E[∂_1 η_2(R_1)] using the t=1 Gaussianity from the OAMP reduction; (ii) prove \\langle ∂_1 η_3(r_1,r_2)\\rangle \\xrightarrow{P} E[∂_1 η_3(R_1,R_2)] using the joint Gaussianity of (r_1,r_2) from Theorem 2 at t=2; (iii) verify the operator-norm bound in Eq. (121) with the resulting rates. If the induction requires additional regularity beyond Assumption 2 — e.g., η_{t+1} ∈ C^2 with bounded second derivatives, or quantitative control on the W_2 convergence of derivatives — then Theorem 2 needs a strengthened hypothesis or a new proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central reduction replaces the random divergence matrix \\hat Φ_t by its deterministic limit Φ_t so that the matrix denoisers \\hat P_{t,i}(λ) can be treated as deterministic and trace-free in the OAMP state evolution. Appendix C.3 dispatches the required convergence with the single sentence 'the above limit holds by an inductive argument' and never supplies the induction. This matters because \\hat Φ_t is built from derivatives of the W-dependent iterates r_1,...,r_{t-1}; its concentration is not a consequence of the algebraic reduction in Lemma 3, and the state evolution covariance in Theorem 2 is only valid if \\hat P_{t,i}(W) is asymptotically close to the deterministic P_{t,i}(W). The step that would close the induction — showing that \\hat Φ_{t+1} → Φ_{t+1} using the Gaussianity of (r_1,...,r_{t+1}) obtained from the OAMP reduction with deterministic coefficients — is exactly the step that requires a proof but is omitted. If \\hat Φ_t fails to concentrate for some admissible Lipschitz denoisers (for example, if the Gaussian approximation of the iterates is not strong enough to control empirical averages of their derivatives), then the asymptotic Gaussianity claim in Theorem 2, and hence the central reduction of the paper, is unsupported. The standard conditioning arguments of [21,47,51] are not reproduced or adapted to the random-coefficient setting here.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a unified framework for constructing approximate message passing (AMP) algorithms for rotationally-invariant matrix models. Starting from a generic first-order method template, the authors reduce the algorithm to a long-memory orthogonal AMP (OAMP) recursion by imposing a trace-free condition on the polynomial coefficient matrices in the iterate representation. This leads to a unique de-biasing matrix B_t expressed as a polynomial of the divergence matrix D_t, with coefficients identified as free cumulants of the limiting spectral measure. The authors derive the state evolution of the resulting RI-AMP, prove consistency with the state evolution of Fan [21], and introduce two new variants: RI-AMP-DF with a different Onsager term, and RI-AMP-MP with nonlinear matrix processing. The framework is applied to spiked matrix models, yielding a non-polynomial generalization of BAMP, and numerical experiments illustrate accuracy of the state evolution predictions.","tokens_in":44779,"tokens_out":3446,"duration_ms":35509,"significance":"If the main claims hold, the paper provides a genuinely unified and arguably more transparent derivation of the Onsager terms for rotationally-invariant AMP, with the free cumulants emerging from a recursive centering operation rather than from asymptotic integral evaluations. The recursive characterization of free cumulants in Proposition 1 and the explicit derivation of B_t = sum_i κ_i D_t^{i-1} in Lemma 2 are elegant and proved in detail; the equivalence result in Proposition 3 is a substantive cross-check. The two proposed variants, especially RI-AMP-MP with non-polynomial matrix processing, are plausible new algorithmic tools and are supported by preliminary numerical evidence. However, the rigorous status of the central state evolution theorem is weakened by an unproved convergence step for the empirical divergence matrix, and several supporting lemmas/theorems are stated without proofs. These gaps are local in the sense that they appear fixable, but they are load-bearing for the main claims.","major_comments":[{"comment":"The convergence of the empirical divergence matrix \\hat Φ_t to a deterministic limit Φ_t is asserted with the parenthetical 'the above limit holds by an inductive argument', but the induction is never given. This step is load-bearing: the reduction to OAMP replaces the random polynomials \\hat P_{t,i}(W) by deterministic P_{t,i}(W), and the trace-free condition E[P_t(Λ)] = 0 used in the state evolution depends on this replacement. To close the argument, the authors must show that, conditional on the Gaussian limit obtained at time t, the empirical averages \\langle ∂_i η_j(r_1,...,r_{j-1}) \\rangle concentrate on E[∂_i η_j(R_1,...,R_{j-1})], and then propagate this to time t+1. The standard conditioning arguments of Bayati-Montanari, Fan, or Takeuchi are not adapted to the random-coefficient setting here, so the proof of Theorem 2 is incomplete.","section":"Appendix C.3, around Eq. (118)-(121)"},{"comment":"Lemma 4 is a central result for the RI-AMP-MP variant: it states the reformulation (62), the existence and uniqueness of the de-biasing matrix E_t solving (63), and the recursive structure of the resulting functions. Its proof is omitted with the sentence 'Its proof is similar to that of Lemma 1 and Lemma 2, and thus omitted.' For a lemma that underlies Theorem 4 and the claimed non-polynomial generalization of BAMP, this is not sufficient. The uniqueness of E_t is not obvious because diag{f_1(λ),...,f_t(λ)} does not commute with \\hat Φ_t, and the representation (70b) is essential for the state evolution. The proof should be supplied, or the lemma should be replaced by a precise statement with a complete reference.","section":"Section 5.2, Lemma 4"},{"comment":"The state evolution statements for RI-AMP-DF and RI-AMP-MP, Theorem 3(2) and Theorem 4(2), are both dismissed with 'similar to that of Theorem 2' or 'omitted'. Since Theorem 2 itself rests on the unproved convergence of \\hat Φ_t identified above, these variants inherit that gap. In addition, Theorem 4 replaces W by Y = (θ/N)x_*x_*^T + W, and the reduction must address the fact that the matrix processing functions f_t are now applied to Y rather than to the noise matrix W; the covariance formulas (71c)-(71e) require a separate verification that the OAMP state evolution for spiked models applies to the random-coefficient reduction. This is not merely a cosmetic repetition of earlier arguments.","section":"Theorems 3 and 4"},{"comment":"Assumption 2 only requires the denoisers η_t to be Lipschitz continuous, but the RI-AMP iteration in Definition 4 uses empirical partial derivatives ⟨∂_i u_t⟩, and the OAMP state evolution invoked in Theorem 1 (and proved in Appendix B) assumes that the corresponding functions are continuously differentiable with bounded derivatives. A Lipschitz function may fail to be differentiable on a set of positive measure, and the Stein-lemma argument used in Proposition 2 and in the covariance computation requires control of the derivatives of the limiting denoisers. Either Assumption 2 must be strengthened to, say, continuously differentiable denoisers with Lipschitz derivatives, or a rigorous justification must be given that the weak derivatives of Lipschitz functions suffice for the empirical-divergence limits used here.","section":"Assumption 2(3) and Definition 4"}],"minor_comments":[{"comment":"The heading 'Monte Carlo Estimator of Free Cumulants' contains a typo: 'Onager' should be 'Onsager'.","section":"Section 2.3 heading"},{"comment":"The reference list contains a duplicate entry: '[49, 49]' appears in the first paragraph of Section 1.1.","section":"Introduction, references"},{"comment":"In the proof of Lemma 3, the sentence 'The second equality in the above equation is due to the recursive characterization of free cumulants in Lemma 1' appears to refer to the wrong result; the identification of the coefficients with free cumulants is Proposition 1, not Lemma 1.","section":"Lemma 3 proof"},{"comment":"The caption says 'The empirical results are average over 50 independent runs'; this should read 'averaged over 50 independent runs'.","section":"Figure 2 caption"},{"comment":"In Corollary 1 and Algorithm 1, the initialization α_{n,-1}=0 is used for all n, but the recursion for n=1 is not explicitly separated; adding a one-line verification for n=1 would improve readability.","section":"Notation, Section 2.2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Both the reader and I converge on the same verdict. Let me state my own take. The paper's real contribution is the reduction template: start with a FOM, impose trace-free polynomial matrices, read off Onsager terms as free cumulants. The derivation of B_t through the recursion in Lemma 2 is clean, and the recursive characterization of free cumulants in Prop 1 is genuinely new as far as I can tell. The two variants, especially RI-AMP-MP with non-polynomial f, go beyond Opper et al. and Fan and give the paper teeth. This is not a 're-derivation only' paper.\n\nWhat is less solid is the proof of the central asymptotic claim. Theorem 2's proof in Appendix C.3 depends on replacing the random empirical divergence matrix \\hat Φ_t with its deterministic limit Φ_t. The paper says this holds 'by an inductive argument' and never gives the induction. The stress-test note is right: this is load-bearing, because the trace-free condition that activates OAMP state evolution is only exact in the limit, and \\hat Φ_t is built from W-dependent iterates. I can believe it is true; the standard conditioning arguments in Fan and Takeuchi probably adapt. But as submitted, the central theorem has a hole at exactly the point where the reduction meets the asymptotics. The same applies to Lemma 4, where the reduction of RI-AMP-MP is stated without proof and no state evolution is given. These are not cosmetic omissions; they are the key steps for the two novel variants.\n\nThe rest of the paper is in better shape. The algebra in Lemma 1 and Lemma 2 is carefully done. The consistency check with Fan's state evolution (Prop 3) is useful. The numerics are encouraging but show no error bars; given 50 runs, adding them is trivial and should be demanded.\n\nCitation pattern looks honest. The orthogonal-decomposition idea is credited to Dudeja et al., and the RI-AMP itself to Opper and Fan. Self-citations are to the authors' own concurrent work, which is fine.\n\nSo: this paper deserves a serious referee. It is not desk-reject material. But it needs a heavy revision: close the induction in C.3, prove or fully reference Lemma 4, and supply the RI-AMP-MP state evolution. I'd recommend send to peer review and insist on those fixes. The framework is useful enough that I'd probably cite it once the gaps close.","headline":"A useful reduction template for building RI-AMP algorithms, with the main theorem's proof resting on a convergence claim that is asserted but not proved; worth refereeing carefully.","tokens_in":45356,"tokens_out":1732,"would_cite":true,"duration_ms":16554,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B20","62F12","46L54"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that AMP algorithms for rotationally-invariant random matrices are pinned down by a single formula: the de-biasing matrix must be built from free cumulants of the spectral law, and with that choice the iterates become…","keywords":["approximate message passing","rotationally-invariant random matrices","free cumulants","orthogonal AMP","state evolution","Onsager correction","spiked matrix models","high-dimensional estimation"],"falsifier":"A concrete check: choose a rotationally-invariant $W$ with a known limiting spectrum and a smooth denoiser for which the empirical average-derivative matrix $\\hat{\\Phi}_t$ does not converge in probability (for example, one whose derivative oscillates on a scale shrinking with $N$), run the RI-AMP iteration, and test whether the empirical distribution of $(r_1,\\dots,r_t)$ converges to the zero-mean Gaussian with covariance $\\Sigma_t$ in Theorem 2. Any limiting mismatch would refute the claim that the de-biasing formula works for the full Lipschitz class.","tokens_in":44292,"feed_emoji":"🧮","tokens_out":11808,"duration_ms":94567,"temperature":0.7,"pith_summary":"Approximate message passing (AMP) for rotationally-invariant random matrices has previously been derived case by case, with the Onsager correction terms emerging from lengthy calculations. This paper claims a single mechanism behind all such algorithms: any first-order iteration of the form $r_t = W u_t - \\sum_{i=1}^t b_{t,i} u_i$ with $u_{t+1} = \\eta_{t+1}(r_1,\\dots,r_t)$ can be unfolded by orthogonal decomposition into an orthogonal AMP iteration, and the coefficients $b_{t,i}$ needed to make that unfolding work are uniquely determined. The required de-biasing matrix is $B_t = \\sum_{i=1}^t \\kappa_i D_t^{i-1}$, where $\\kappa_i$ are the free cumulants of the limiting spectral law and $D_t$ collects the average derivatives of the denoisers. With this choice the iterates are asymptotically Gaussian and their covariance is given by a closed-form state evolution. The same recipe rederives the known RI-AMP algorithm and produces new variants, including one that allows a non-polynomial nonlinear matrix-processing step.","feed_headline":"Free cumulants set message-passing corrections","feed_subtitle":"The unique de-biasing rule, built from free cumulants, makes every first-order iteration an orthogonal AMP with Gaussian iterates.","key_machinery":"The load-bearing device is a recursive orthogonal decomposition of the iterates combined with matrix centering. One defines residual vectors $\\bar{u}_t$ by subtracting from $u_t$ the projection onto the past $r_i$'s, with projection coefficients given by average derivatives, so that $\\bar{u}_t$ is asymptotically orthogonal to all previous $r_i$. Unfolding the first-order method then expresses $(r_1,\\dots,r_t)$ as a lower-triangular block matrix $P_t(W)$ acting on $(\\bar{u}_1,\\dots,\\bar{u}_t)$, where $P_t(\\lambda) = (I_t - \\lambda D_t + B_t D_t)^{-1}(\\lambda I_t - B_t)$. The trace-free condition $E[P_t(\\Lambda)] = 0$ singles out a unique $B_t$; solving it introduces the polynomials $Q_n$ defined by $Q_n(\\lambda) = \\lambda Q_{n-1}(\\lambda) - \\sum_{i=1}^n E[\\Lambda Q_{i-1}(\\Lambda)] Q_{n-i}(\\lambda)$, whose coefficients are exactly the free cumulants $\\kappa_n = E[\\Lambda Q_{n-1}(\\Lambda)]$. This centering converts the iteration into an OAMP with trace-free matrix denoisers and divergence-free iterate denoisers, and the OAMP state evolution then transfers to the original iterates.","core_discovery":"The central claim, stated on the paper's own terms, is that the Onsager or de-biasing coefficients of AMP for rotationally-invariant models are not free parameters but are forced by the requirement that the iterates be asymptotically Gaussian. Starting from the first-order method, the paper represents the iterates as $\\mathbf{r}_t = \\sum_{i=1}^t P_{t,i}(W)\\bar{u}_i$ in terms of orthogonal residuals $\\bar{u}_i$, with $P_t(\\lambda) = (I_t - \\lambda D_t + B_t D_t)^{-1}(\\lambda I_t - B_t)$. Enforcing the trace-free condition $E[P_t(\\Lambda)] = 0$ for $\\Lambda$ distributed as the limiting spectrum has a unique solution in $B_t$, namely $B_t = \\sum_{i=1}^t \\kappa_i D_t^{i-1}$ with $\\kappa_i$ the free cumulants of $\\mu$. Under this choice the unfolded iteration is an orthogonal AMP algorithm, and the OAMP state evolution implies that $(r_1,\\dots,r_t)$ converges in empirical distribution to a zero-mean Gaussian vector with covariance $\\Sigma_t = E[P_t(\\Lambda)\\bar{\\Delta}_t P_t(\\Lambda)^T]$.","pith_inferences":["If the reduction is as general as stated, the design of AMP-type algorithms reduces to choosing the denoisers and the matrix-processing function; the Onsager terms are then automatic, which suggests the same recursive centering could be applied to other iterative high-dimensional algorithms beyond AMP.","The recursive free-cumulant characterization and the Monte Carlo estimator in Algorithm 2 point to a practical way to implement RI-AMP when the spectrum is unknown, using only matrix-vector products; the paper does not develop convergence guarantees for this estimator.","The equivalence between RI-AMP-DF and generalized first-order methods suggests that optimality results for spiked models might extend to non-polynomial matrix processing, a question beyond what the paper proves.","In spectra where the higher free cumulants vanish (such as the GOE), the de-biasing matrix collapses to the divergence matrix and the algorithm shortens to standard memory AMP; this makes spectral shape alone the determinant of memory length."],"forward_implications":["For any first-order method with a fixed denoiser sequence, Lemma 2 pins down the Onsager terms uniquely: no other de-biasing matrix makes the relevant polynomial matrices asymptotically trace-free.","The iterates $r_t$ of RI-AMP are asymptotically zero-mean Gaussian with covariance given by Theorem 2, so error metrics such as mean squared error can be computed by a closed-form state evolution instead of by simulation.","The framework rederives the RI-AMP algorithm of [21] and gives an alternative state evolution that Proposition 3 shows is equivalent to the earlier one.","The RI-AMP-DF variant is equivalent to generalized first-order methods up to a change of variables, so the derivation covers a broader class of iterative algorithms than the original RI-AMP.","The RI-AMP-MP variant extends the BAMP algorithm of [3] to non-polynomial matrix-processing functions, and Theorem 4 provides the associated state evolution, with numerical experiments matching the prediction."],"supporting_citations":[{"why":"Defines the RI-AMP algorithm and its state evolution, which this paper rederives through the OAMP reduction; supplies the partial-moments formulation of free cumulants.","marker":"[21]"},{"why":"Introduced the rotationally-invariant AMP algorithm via dynamical functional theory; this is the algorithm the unified derivation reproduces.","marker":"[43]"},{"why":"Source of the orthogonal-decomposition idea and of the OAMP state evolution theorem used as the reduction target.","marker":"[19]"},{"why":"Established the long-memory OAMP framework with multivariate denoisers that the paper reduces to.","marker":"[52]"},{"why":"Defined the original orthogonal AMP algorithm, whose trace-free and divergence-free design is the template for the reduction.","marker":"[30]"},{"why":"Provided a rigorous state evolution for vector AMP that underlies the OAMP asymptotics invoked in Theorem 1.","marker":"[47]"},{"why":"Introduced the BAMP algorithm and matrix-processing idea that RI-AMP-MP generalizes to non-polynomial functions.","marker":"[3]"},{"why":"Supplies the OAMP state evolution for spiked matrix models used in the application of the framework.","marker":"[18]"}],"fun_headline_variants":["Free cumulants force AMP corrections","Gaussian iterates force unique Onsager terms","A centering condition sets free cumulants","De-biasing rule derived from free cumulants"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof needs the random, data-dependent average derivatives of the denoisers to converge in probability to fixed limits as the dimension grows; if that concentration fails for some admissible smooth denoiser, the reduction to OAMP and the Gaussian state evolution are not established.","fun_headline_variants_meta":{"raw":{"variants":["Free cumulants force AMP corrections","Gaussian iterates force unique Onsager terms","A centering condition sets free cumulants","De-biasing rule derived from free cumulants"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000301,"raw_usage":{"total_tokens":1720,"prompt_tokens":917,"completion_tokens":803,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":533,"completion_tokens_details":{"reasoning_tokens":747}},"tokens_in":533,"tokens_out":803,"duration_ms":7336,"temperature":1.0,"reasoning_tokens":747,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T04:18:03.196250+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete check: choose a rotationally-invariant $W$ with a known limiting spectrum and a smooth denoiser for which the empirical average-derivative matrix $\\hat{\\Phi}_t$ does not converge in probability (for example, one whose derivative oscillates on a scale shrinking with $N$), run the RI-AMP iteration, and test whether the empirical distribution of $(r_1,\\dots,r_t)$ converges to the zero-mean Gaussian with covariance $\\Sigma_t$ in Theorem 2. Any limiting mismatch would refute the claim that the de-biasing formula works for the full Lipschitz class.","supporting_citations":[{"cited_title":"Approximate message passing algorithms for rotationally invariant matrices","cited_arxiv_id":null,"evidence_quote":"Defines the RI-AMP algorithm and its state evolution, which this paper rederives through the OAMP reduction; supplies the partial-moments formulation of free cumulants."},{"cited_title":"A theory of solving TAP equations for Ising models with general invariant random matrices","cited_arxiv_id":null,"evidence_quote":"Introduced the rotationally-invariant AMP algorithm via dynamical functional theory; this is the algorithm the unified derivation reproduces."},{"cited_title":"Spectral universality in regularized linear regression with nearly deterministic sensing matrices","cited_arxiv_id":null,"evidence_quote":"Source of the orthogonal-decomposition idea and of the OAMP state evolution theorem used as the reduction target."},{"cited_title":"A unified framework of state evolution for message-passing algorithms","cited_arxiv_id":null,"evidence_quote":"Established the long-memory OAMP framework with multivariate denoisers that the paper reduces to."},{"cited_title":"Orthogonal AMP","cited_arxiv_id":null,"evidence_quote":"Defined the original orthogonal AMP algorithm, whose trace-free and divergence-free design is the template for the reduction."},{"cited_title":"Fundamental limits in structured principal component analysis and how to reach them","cited_arxiv_id":null,"evidence_quote":"Introduced the BAMP algorithm and matrix-processing idea that RI-AMP-MP generalizes to non-polynomial functions."},{"cited_title":"Optimality of Approximate Message Passing Algorithms for Spiked Matrix Models with Rotationally Invariant Noise","cited_arxiv_id":"2405.18081","evidence_quote":"Supplies the OAMP state evolution for spiked matrix models used in the application of the framework."}],"review_version":1}