acceptodds
Under review as a conference paper at ICLR 2027

Rigorous State Evolution for General-Core Asymmetric Multilinear AMP

Abstract

State evolution (SE) provides an asymptotically exact finite-dimensional characterization of approximate message passing (AMP) dynamics in many high-dimensional inference problems. For asymmetric multilinear AMP, however, reusing the same Gaussian tensor across mode contractions and iterations creates dependencies that complicate both the Onsager correction and rigorous SE analysis. Existing tensor-AMP results do not directly cover general-core rectangular models with empirical covariance inputs and Onsager reaction matrices. We derive core-induced matrix-valued maps that govern the signal contribution and Gaussian covariance and whose derivatives yield an exact finite-system factorization of the Onsager reaction. For fully observed Gaussian models of order at least three with a fixed known core and fixed, mode-dependent channel dimensions, we prove fixed-horizon SE for the joint empirical law of planted rows, factor-iterate histories, and effective-field histories within each mode. The theorem allows initialization correlated with the planted factors but independent of the Gaussian disorder. The closed SE recursion tracks signal and iterate overlaps separately and does not require Bayes matching. The proof combines a symmetric multi-species embedding and scalar-query serialization with Gaussian conditioning supported by quantitative bounds on the stacked-response covariance in an auxiliary regularized model. The joint law yields limits for representation statistics and simultaneous convergence of order-two pseudo-Lipschitz losses over fixed finite families of admissible recursions and independently fitted, frozen terminal readouts. Numerical experiments assess SE predictions for non-diagonal cores and covariance-dependent updates with unequal channel dimensions, and illustrate estimation gains from SE-calibrated terminal history readouts.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Approximate message passing, state evolution, tensor factorization, asymmetric tensor models, high-dimensional inference, Onsager correction

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_oVTgOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

For asymmetric Gaussian tensor inference with a general Tucker core, this paper derived the correct matrix-valued Onsager reaction term for AMP as the derivative of the covariance map and rigorously proved that the entire fixed-time trajectory follows a finite-dimensional Gaussian effective process.

Critical strengths

The resulting theorems hold for a quite general setup, encompassing misspecified priors, misspecified noise, heuristic denoisers, and neural-network denoisers. Lemma D.2 in Appendix D explicitly demonstrates that when N=2N=2, skew-symmetric null directions arise, causing the lower bound to fail. Therefore, the proof goes beyond simply stating that "matrix AMP has been generalized to tensor AMP"; it relies on mathematical structures specific to orders of 3 or higher.

Critical weaknesses

While the concept of a "general core" is clear as a mathematical generalization, the practical motivation for the "known general core" setting is weak; the paper would be more compelling if it could demonstrate a real-world application where this specific setting applies.

Questions for authors

I couldn't quite visualize the types of problems in machine learning or signal processing where the assumed problem setting would arise. Could you provide some concrete examples?

1 comment
AuthorsOpenReview ↗

A known non-diagonal core in hyperspectral image denoising

Thank you for highlighting the non-Bayesian denoisers and the skew-symmetric null directions at N=2N=2 in Lemma D.2. Your question helped us clarify the practical motivation for the known-core setting and improve its presentation in the manuscript.

Teal marks new material and purple marks revised discussion in the revised manuscript.

Q1. Where does a known, non-diagonal core arise in practice?

A core can be determined exactly by model structure, as in tensor-ring models for hyperspectral image denoising, or estimated from independent data and then frozen. The latter requires additional control of estimation error beyond Theorem 4.3.

Image denoising. Chen et al. used ring ranks (R1,R2,R3)=(9,3,3)(R_1,R_2,R_3)=(9,3,3) to denoise the Indian Pines hyperspectral image (Fig. 10 of [R1]). For a group of similar patches, let i,j,ki,j,k index within-patch position, spectral band, and patch, respectively. The tensor-ring factors have dimensions U∈RR1×I1×R2\boldsymbol{\mathcal{U}}\in\mathbb{R}^{R_1\times I_1\times R_2}, V∈RR2×I2×R3\boldsymbol{\mathcal{V}}\in\mathbb{R}^{R_2\times I_2\times R_3}, and W∈RR3×I3×R1\boldsymbol{\mathcal{W}}\in\mathbb{R}^{R_3\times I_3\times R_1}. Expanding Eq. (5) of [R1] gives the signal model [Z]ijk=∑a=1R1∑b=1R2∑c=1R3[U]aib[V]bjc[W]cka.[\boldsymbol{\mathcal{Z}}]_{ijk}=\sum_{a=1}^{R_1}\sum_{b=1}^{R_2}\sum_{c=1}^{R_3}[\boldsymbol{\mathcal{U}}]_{aib}[\boldsymbol{\mathcal{V}}]_{bjc}[\boldsymbol{\mathcal{W}}]_{cka}. Unfolding these tensor-ring cores along their observation modes, with a fixed ordering of the remaining index pairs, gives our unknown factor matrices A1,A2,A3\mathbf{A}_1,\mathbf{A}_2,\mathbf{A}_3, with P1=R1R2=27P_1=R_1R_2=27, P2=R2R3=9P_2=R_2R_3=9, and P3=R3R1=27P_3=R_3R_1=27. Our known core is the non-diagonal binary array selecting exactly the triples ((a,b),(b,c),(c,a))((a,b),(b,c),(c,a)). Once the ranks are fixed, none of its entries is fitted.

Independent estimation. A core shared across tensor instances could be estimated by expectation–maximization on independent data and then frozen for a new instance. Theorem 4.3 assumes that AMP uses the data-generating core. If both cores are expressed in the same latent coordinates and their Frobenius distance tends to zero in probability, a possible extension would couple the two AMP paths on the same data and initialization using the fixed-horizon stability bounds in Appendix E. Consistency of the EM estimate would require separate justification.

Revisions: Sec. 1 (p. 1); Appendix A.1 (pp. 18–19).

References

[R1] Chen et al. “Nonlocal Tensor-Ring Decomposition for Hyperspectral Image Denoising.” IEEE TGRS, 2020.

Reviewer_vAJxOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper establishes rigorous fixed-horizon state evolution for asymmetric multilinear AMP with general cores, heterogeneous channel dimensions, and covariance-dependent updates. It derives matrix-valued covariance maps and an exact factorization of the Onsager correction, extending theoretical guarantees beyond existing symmetric or restricted tensor AMP settings. Theoretical results are supported by numerical state-evolution validation, reaction-factorization experiments, and history-based estimation experiments.

Critical strengths
  1. Substantial theoretical generalization. The rigorous treatment of general-core asymmetric tensor AMP with heterogeneous channels and empirical covariance-dependent updates addresses an important limitation of previous AMP theory.
  2. Connection between theory and computation. The exact Onsager factorization provides a useful computational consequence, while the numerical experiments validate state-evolution predictions and demonstrate the potential of calibrated history readouts.
Critical weaknesses
  1. Restricted theoretical regime. The guarantees concern fixed iteration horizons, fixed channel dimensions, fully observed Gaussian tensors, and known cores. Extensions to learned cores, missing observations, and long-time behavior remain unresolved, limiting immediate applicability.
  2. Finite-dimensional accuracy is not quantified theoretically. Some numerical covariance discrepancies remain appreciable at the tested dimensions. Explicit finite-sample error rates would strengthen the practical interpretation of the asymptotic guarantees.
Questions for authors
  1. Can the authors provide additional intuition or quantitative evidence regarding the finite-dimensional convergence rate of the state-evolution predictions?
  2. Which assumptions are the main obstacles to extending the theorem to partially observed tensors or estimated cores?
3 comments
AuthorsOpenReview ↗

Finite-size SE accuracy and extensions to missing data and estimated cores

Thank you for highlighting the computational value of the Onsager factorization and SE-calibrated readouts. Your questions helped us clarify the finite-size evidence and the theorem’s limits.

Teal marks new material and purple marks revised discussion in the revised manuscript.

Q1. What convergence rate do the data suggest, and what can the theorem guarantee?

We fixed each core's squared Frobenius norm at 3.473.47 and measured the mean relative Frobenius error of the M,QM,Q histories at five proportional sizes (T=5T=5, ν=0.6\nu=0.6, 30 seeds per size). The errors below are for (36,45,54)(36,45,54) and (120,150,180)(120,150,180), respectively. Each log–log slope is fitted against the reference size II using all five sizes.

  • γ=0.2\gamma=0.2: 0.5590.559 to 0.2710.271 (slope −0.61-0.61).
  • γ=0.7\gamma=0.7: 0.5410.541 to 0.2850.285 (slope −0.54-0.54).
  • γ=1\gamma=1: 0.5480.548 to 0.3100.310 (slope −0.48-0.48).

The fitted slopes are near −1/2-1/2, the benchmark for averaging independent finite-variance contributions, but Theorem 4.3 does not establish this rate for AMP rigorously. At the largest size, 93–97% of the mean squared M,QM,Q discrepancy was variation across runs.

For the unequal-channel KK histories (Table 2), relative errors pooled over modes and times were 0.590±0.0760.590\pm0.076, 0.585±0.0780.585\pm0.078, and 0.390±0.0610.390\pm0.061 across increasing sizes (mean ±\pm one standard error). At the largest size, the mean per-run error was 39.0%. Averaging the blocks across the same 30 runs before comparing with deterministic SE gave 6.46%. Between-run variation accounted for 98.4% of the mean squared discrepancy.

Assumption 4.2 requires W2W_2 convergence at initialization but gives no rate. In a scalar channel of a fixed mode, take Xi0=Ai+1/log⁡(2+I)X_i^0=A_i+1/\log(2+I). The empirical mean of ψ(a,x0)=x0−a\psi(a,x^0)=x^0-a differs from its limit by 1/log⁡(2+I)1/\log(2+I) at time zero. This rules out a universal polynomial rate for the full joint row law under Assumption 4.2.

Revisions: Sec. 6.1 (pp. 8–9; Table 2 on p. 9); Appendix H.1.1 (pp. 49–50), Fig. 6 (p. 50); KK decomposition in Appendix H.2 (p. 50); rate limitation in Sec. 7 (p. 10).

Q2. What changes for missing observations or estimated cores?

Missing observations. For an independent Bernoulli mask of density ρ\rho, the non-rigorous SE analysis of CP-GAMP in the matched setting with growing rank [R1] scales precision by ρ\rho at fixed overlaps, or equivalently scales the full variance term vw+V(t)v^w+V(t) by 1/ρ1/\rho, where vwv^w is the observation-noise variance and V(t)V(t) the tensor reconstruction MSE per entry predicted by the SE in [R1]. For fixed queries in our model, the expected Gram matrix of the observed features, without rescaling, is likewise ρ\rho times the fully observed Gram matrix. A proof must control fluctuations for queries that depend on the reused mask and identify the Onsager reaction.

Estimated cores. Theorem 4.3 assumes that AMP uses the data-generating core. Suppose a core is estimated from independent data, frozen, and expressed in the same latent coordinates as the true core. If their Frobenius distance tends to zero in probability, a possible extension would couple the two AMP paths on the same data and initialization using polynomial dependence on the core and the fixed-horizon stability bounds in Appendix E. With persistent mismatch, a candidate SE would use one copy of each core in the signal mean and two copies of the estimated core in the noise covariance. Estimating the core from the same observed tensor also introduces dependence on the observation noise.

Fixed horizon and channel dimensions keep the query list finite. Growing either would require uniform control of response covariances and accumulated errors. Non-Gaussian noise would require replacing exact Gaussian conditioning.

Revisions: Sec. 7 (p. 10); Appendix A.1 (pp. 18–19).

References

[R1] Cheng et al. “Large-Scale Bayesian Tensor Reconstruction via Approximate Message Passing.” IEEE ICDM, 2026.

Thanks for the responses! The authors have addressed most of my comments.

Thank you for your follow-up and constructive feedback! Your comments helped us improve the discussion of finite-size SE accuracy and the scope of our theoretical guarantees. We would be happy to clarify any remaining points.

Reviewer_jTxrOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper establishes rigorous fixed-horizon state evolution (SE) for asymmetric multilinear approximate message passing (AMP) in general-core Tucker tensor models. The main technical contributions include a core-induced covariance map, a factorized expression for the matrix-valued Onsager correction, and a joint empirical-law convergence theorem covering the planted factors, AMP iterates, and effective-field histories. The framework accommodates unequal mode and channel dimensions, covariance-dependent denoisers, and non-Bayesian updates.

The theoretical results are supported by numerical experiments comparing finite-dimensional AMP trajectories with SE predictions. The authors also demonstrate that SE-calibrated linear readouts of AMP histories can improve tensor estimation accuracy.

Critical strengths

The paper extends rigorous SE analysis to a more general class of asymmetric multilinear AMP algorithms, allowing general Tucker cores, unequal channel dimensions, and non-Bayesian denoisers. This appears to be a meaningful theoretical extension of existing tensor AMP results.

Critical weaknesses

My expertise in rigorous AMP theory is limited, and I do not fully understand all the technical details of the proofs. Therefore, my concerns mainly relate to the clarity of the theoretical novelty and the experimental validation, rather than to the mathematical correctness of the results.

  1. The analysis builds substantially on the multi-species tensor AMP framework of Huang and Sellke (2024), including the Gaussian-conditioning approach. While the general-core formulation and matrix-valued Onsager correction are interesting, it is not entirely clear to me which parts require fundamentally new theoretical arguments and which follow from extensions or reformulations of existing results. A more explicit discussion of the essential new technical difficulties and how they are overcome would help establish the significance of the contribution.

  2. In Figure 1, the relative Frobenius errors remain approximately 0.20, 0.29, and 0.50 for the three tested core configurations, even at the largest dimension. Although the theorem is asymptotic, these discrepancies raise questions about the practical accuracy of SE predictions. Furthermore, varying the coupling parameter \gamma also changes the Frobenius norm of the core tensor, making it difficult to distinguish the effects of cross-channel coupling from those of overall signal strength.

  3. The experiments mainly validate SE predictions and demonstrate improvements from history-based readouts. However, the estimation experiments lack comparisons with established tensor reconstruction approaches, such as conventional Tucker decomposition algorithms and existing tensor AMP methods. The main readout baseline is based on the initialization rather than a competitive tensor estimation algorithm. More comprehensive comparisons would help clarify the practical significance of the proposed framework.

Questions for authors
  1. Could the authors clarify which key technical results or proof steps cannot be obtained directly from the existing multi-species tensor AMP framework of Huang and Sellke (2024)? In particular, what are the main new mathematical difficulties introduced by the general core and vector-valued updates?

  2. How do the authors explain the relatively large finite-dimensional discrepancies observed in Figure 1, particularly for stronger core coupling? Could the experiments be repeated with normalized core tensors so that the overall signal strength remains fixed while the cross-channel coupling changes?

  3. Could the authors provide additional comparisons with established tensor reconstruction methods, including conventional Tucker decomposition algorithms or existing tensor AMP approaches? Such comparisons would help assess whether the SE-calibrated readouts offer practical advantages beyond the initialization-based baselines currently considered.

3 comments
AuthorsOpenReview ↗

Proof contributions, equal-energy cores, and the Tucker baseline

Thank you for recognizing the scope of our result for general Tucker cores, unequal channel dimensions, and non-Bayesian denoisers. Your questions sharpened the proof discussion and the experimental comparisons.

Teal marks new material and purple marks revised discussion in the revised manuscript.

Q1. Which proof steps go beyond Huang and Sellke’s multi-species AMP?

We follow the Gaussian-conditioning strategy in Appendix A of [R1]. Since the channels query the same tensor and are denoised jointly, we serialize the synchronous update and recover the core-induced covariance map Kn\mathcal{K}_n from the joint covariance of the scalar responses. Its derivative gives the mixed-time Onsager reaction.

The proof in [R1] first assumes positive interactions across tensor orders and well-conditioned history matrices (Assumptions 2–3). In our pure degree-NN model with N≥3N\geq3, the index repeated N−1N-1 times identifies the query direction after symmetrization. This bounds the smallest eigenvalue of the stacked-response covariance away from zero uniformly in dimension at fixed regularization. At N=2N=2, skew-symmetric directions lie in the kernel. Appendix D.5 then removes the regularization to cover sparse interactions and singular histories. Conditioning on the noise-independent planted–initial arrays permits correlated initialization (Theorem D.8). Appendices D.6 and E transfer the joint law to AMP with empirical coefficients.

Revisions: Sec. 4.3 (p. 7); Lemmas D.2–D.3 (pp. 26–27); Lean 4 verification of Theorem 4.3’s row law and coefficient limits (Reproducibility Statement, p. 11).

Q2. How much of the Figure 1 discrepancy remains at equal core energy?

At the largest tested size, the gap in mean relative error between γ=1\gamma=1 and γ=0.2\gamma=0.2 fell from 0.298 to 0.039. We matched expected signal power per entry (∥C∥F2=3.47\|C\|_F^2=3.47 for Gaussian planted rows) and repeated the five-size simulation with 30 paired runs per size (T=5, ν=0.6T=5,\ \nu=0.6). At (120,150,180)(120,150,180), the mean relative Frobenius errors of the M,QM,Q histories for γ=0.2,0.7,1\gamma=0.2,0.7,1 changed from (0.203,0.285,0.501)(0.203,0.285,0.501) to (0.271,0.285,0.310)(0.271,0.285,0.310). Between-run variation accounted for 93–97% of the equal-energy mean squared discrepancy at that size. An independent Monte Carlo SE reference (120,000 rows per mode) changed the mean relative errors by at most 0.0042.

Revisions: Sec. 6.1 (pp. 8–9; original Fig. 1 on p. 8); Appendix H.1.1 (pp. 49–50; Fig. 6 on p. 50).

Q3. How do history readouts compare with a conventional Tucker estimator?

We compared the frozen readout with rank-(2,2,2)(2,2,2) higher-order orthogonal iteration (HOOI) on 120 test tensors of size (120,150,180)(120,150,180). HOOI estimates its core, and its warm start uses the column space of AMP’s initialization matrix Xn0X_n^0 in each mode. The readout uses the known core and weights fitted on independent SE samples. Each entry is the mean tensor NMSE over the same 30 test instances at that noise level.

Noise ν\nuCalibrated X0X^0Full-history readoutHOOI, spectral startHOOI, warm start
0.500.8670.8593.1972.054
0.200.8670.4841.0850.548
0.100.8670.3240.4300.223
0.050.8670.2310.1010.101

At ν=0.20\nu=0.20, the readout had the lowest mean tensor NMSE among the methods shown. At ν=0.50\nu=0.50, its mean was 0.8590.859, versus 0.8670.867 for calibrated initialization. Warm-start HOOI had lower mean tensor NMSE than the readout at ν=0.10\nu=0.10 and 0.050.05.

Revisions: Sec. 6.2 (pp. 9–10), Table 3 (p. 10); Appendix H.5.5 (p. 55).

References

[R1] Huang and Sellke. “Optimization Algorithms for Multi-Species Spherical Spin Glasses.” Journal of Statistical Physics, 2024.

The authors have made good revisions based on my comments, so I have raised my score.

Thank you for your response! We sincerely appreciate your valuable comments.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Authors’ Summary of Revisions and Contributions

Dear Area Chair and Reviewers,

Thank you for helping us clarify which part of the proof is new, how accurate state evolution (SE) is at finite sizes, and when the core is known in practice.

Revisions prompted by the discussion

  • Proof and reproducibility. Section 4.3 identifies the tensor-specific step in adapting Gaussian conditioning from multi-species AMP: for order three and above, we bound the smallest eigenvalue of the regularized response covariance away from zero uniformly in dimension. The Reproducibility Statement documents a Lean 4 check of Theorem 4.3’s row law and empirical coefficient limits.
  • Finite-size evidence and reconstruction. At (120,150,180)(120,150,180), matching core energy narrowed the gap in mean relative overlap error between the strongest and weakest couplings from 0.298 to 0.039. The errors themselves still ranged from 0.271 to 0.310 (Fig. 6). The log–log slopes across five sizes were near −1/2-1/2, an empirical trend. On the same 30 test tensors per noise level, the known-core history readout had lower mean tensor NMSE than warm-started HOOI at the two higher noise levels and higher NMSE at the two lower ones (Table 3).
  • Known-core motivation. In a tensor-ring model for hyperspectral image denoising, the ring ranks and contraction rule fix a non-diagonal Tucker core, while the factors are fitted to image patches (Appendix A.1). This illustrates the signal model. Missing observations and independently estimated cores remain outside the theorem.

Main contributions and significance

  • An exact finite-system identity. Derivatives of the core-induced covariance maps, evaluated at cross-time iterate overlaps and applied to average denoiser Jacobians, give the exact Onsager correction for each mode.
  • A joint law across iterations. Theorem 4.3 determines the limiting joint law of the planted factor row, iterates, and effective fields within each mode at any fixed horizon, even though AMP reuses the same tensor and computes its coefficients from its iterates. The result covers fully observed asymmetric Gaussian tensor models of order at least three with a known general core and fixed, possibly unequal channel dimensions. It does not require Bayes matching.

For example, the limiting mean squared error of a linear readout combining two effective fields depends on their cross-time second moment. Two separate per-iteration errors do not determine that moment, but the joint law does.

Thank you again for the constructive and high-quality reviews.

Respectfully,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.