pith. sign in

arxiv: 2512.03326 · v2 · submitted 2025-12-03 · 💻 cs.IT · math.IT

Generalized Orthogonal Approximate Message-Passing for Sublinear Sparsity

Keigo Takeuchi This is my paper

Pith reviewed 2026-05-17 02:58 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords approximate message passingsublinear sparsityorthogonally invariant matricesstate evolutionOnsager correctionsparse signal reconstructioncompressed sensinggeneralized linear measurements
0
0 comments X

The pith

GOAMP achieves error-free reconstruction of sublinearly sparse signals from linear measurements with orthogonally invariant matrices exactly when the measurement dimension exceeds the standard AMP threshold.

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

The paper introduces generalized orthogonal approximate message-passing (GOAMP) to recover signals whose non-zero entries grow slower than the overall dimension from generalized linear measurements. It constructs an Onsager correction through state-evolution analysis that applies to any orthogonally invariant sensing matrix once sparsity and measurement count both tend to infinity sublinearly in the ambient dimension. The correction restores the asymptotic Gaussianity of errors that standard AMP loses on non-Gaussian matrices. For linear measurements, when the support of the non-zero coefficients stays away from a neighborhood of the origin, the method is proved to deliver perfect recovery if and only if the number of measurements exceeds a threshold identical to the one known for AMP on Gaussian matrices. Simulations indicate that the same algorithm also outperforms prior sublinear-sparsity methods on ill-conditioned matrices for both linear and 1-bit compressed sensing.

Core claim

GOAMP is proposed for signals with sublinear sparsity from generalized linear measurements. The Onsager correction is designed via state evolution for orthogonally invariant sensing matrices in the sublinear sparsity limit, where the signal sparsity and measurement dimension tend to infinity at sublinear speed in the signal dimension. When the support of non-zero signals does not contain a neighborhood of the origin, GOAMP using Bayesian denoisers is proved to achieve error-free signal reconstruction for linear measurements if and only if the measurement dimension is larger than a threshold, which is equal to that of AMP for standard Gaussian sensing matrices.

What carries the argument

The Onsager correction designed via state evolution for orthogonally invariant sensing matrices in the sublinear sparsity limit, which restores asymptotic Gaussianity of the estimation errors.

If this is right

  • Error-free reconstruction holds for linear measurements whenever the measurement dimension exceeds the identified threshold and the support condition is met.
  • The reconstruction threshold equals the one already known for standard AMP on Gaussian matrices.
  • GOAMP outperforms generalized AMP and other existing algorithms on ill-conditioned matrices in the sublinear-sparsity regime.
  • The same procedure applies to both linear measurements and 1-bit compressed sensing.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar Onsager corrections might be derivable for sensing matrices that are not orthogonally invariant, potentially broadening the class of usable matrices.
  • The sublinear-sparsity regime could be exploited in applications where the number of non-zeros stays very small relative to dimension and the matrix has known structure.
  • Extensions to other non-linear measurement models beyond the linear case analyzed here remain open for future state-evolution derivations.

Load-bearing premise

The sensing matrices are orthogonally invariant, sparsity remains sublinear in the ambient dimension, and the support of the non-zero entries avoids a neighborhood of the origin.

What would settle it

Check whether perfect reconstruction fails for linear measurements precisely when the measurement dimension drops below the stated threshold or when the non-zero support begins to include a neighborhood of the origin.

Figures

Figures reproduced from arXiv: 2512.03326 by Keigo Takeuchi.

Figure 1
Figure 1. Figure 1: Unnormalized square error versus the condition numb [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: State evolution chart of Bayesian OAMP for the linear [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: Squared norm for the normalized errors versus [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
read the original abstract

This paper addresses the reconstruction of sparse signals from generalized linear measurements. Signal sparsity is assumed to be sublinear in the signal dimension while it was proportional to the signal dimension in conventional research. Approximate message-passing (AMP) has poor convergence properties for sensing matrices beyond standard Gaussian matrices. To solve this convergence issue, generalized orthogonal AMP (GOAMP) is proposed for signals with sublinear sparsity. The main feature of GOAMP is the so-called Onsager correction to realize asymptotic Gaussianity of estimation errors. The Onsager correction in GOAMP is designed via state evolution for orthogonally invariant sensing matrices in the sublinear sparsity limit, where the signal sparsity and measurement dimension tend to infinity at sublinear speed in the signal dimension. When the support of non-zero signals does not contain a neighborhood of the origin, GOAMP using Bayesian denoisers is proved to achieve error-free signal reconstruction for linear measurements if and only if the measurement dimension is larger than a threshold, which is equal to that of AMP for standard Gaussian sensing matrices. Numerical simulations are also presented for linear measurements and 1-bit compressed sensing. When ill-conditioned sensing matrices are used, GOAMP for sublinear sparsity is shown to outperform existing reconstruction algorithms, including generalized AMP for sublinear sparsity.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes Generalized Orthogonal Approximate Message-Passing (GOAMP) for sparse signal reconstruction from generalized linear measurements under sublinear sparsity (k, m = o(n)). It introduces an Onsager correction derived from state evolution tailored to orthogonally invariant sensing matrices in the sublinear limit, and proves that GOAMP with Bayesian denoisers achieves error-free reconstruction for linear measurements if and only if the measurement dimension exceeds a threshold identical to that of standard AMP for Gaussian matrices, provided the support of non-zero entries avoids a neighborhood of the origin. Numerical simulations for linear measurements and 1-bit compressed sensing are presented, with emphasis on improved performance for ill-conditioned matrices compared to existing methods.

Significance. If the state-evolution derivation and the error-free reconstruction guarantee hold, the work is significant for extending AMP methods beyond linear sparsity and Gaussian matrices to the sublinear regime with orthogonally invariant ensembles. The explicit equivalence of the recovery threshold to the Gaussian case, combined with the provision of reproducible numerical results, strengthens the contribution to compressed sensing theory and practice with structured sensing matrices.

major comments (2)
  1. [Main theorem and state-evolution section] The central claim in the main theorem (error-free reconstruction iff m exceeds the Gaussian AMP threshold) is conditioned on the support avoiding a neighborhood of the origin (|x_i| ≥ δ > 0). The state-evolution analysis must explicitly demonstrate that this condition forces the effective noise variance below the Bayesian denoiser threshold with probability 1 in the sublinear limit; without this step the fixed-point equation may retain positive error even above the claimed threshold.
  2. [State-evolution derivation] The Onsager correction is obtained via state evolution for orthogonally invariant matrices. The derivation should include the explicit limiting equations for the variance terms under k, m = o(n) to confirm asymptotic Gaussianity of the estimation errors; standard AMP techniques do not automatically carry over without additional justification in this regime.
minor comments (2)
  1. [Numerical simulations] The simulation section would benefit from explicit reporting of the sublinear scaling parameters (e.g., exact ratios k/n and m/n used) and the precise definition of the ill-conditioned matrix ensembles.
  2. [Preliminaries] Notation for the generalized linear measurement model and the Bayesian denoiser should be introduced with a single consistent table or equation block to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and insightful comments on our manuscript. We appreciate the recognition of the significance of extending AMP methods to the sublinear sparsity regime with orthogonally invariant matrices. We address each major comment below and plan to incorporate revisions to enhance the clarity of the state-evolution analysis.

read point-by-point responses

  1. Referee: [Main theorem and state-evolution section] The central claim in the main theorem (error-free reconstruction iff m exceeds the Gaussian AMP threshold) is conditioned on the support avoiding a neighborhood of the origin (|x_i| ≥ δ > 0). The state-evolution analysis must explicitly demonstrate that this condition forces the effective noise variance below the Bayesian denoiser threshold with probability 1 in the sublinear limit; without this step the fixed-point equation may retain positive error even above the claimed threshold.

    Authors: We agree that making this step explicit will strengthen the presentation. In the revised version, we will add a new lemma in the state-evolution section that rigorously shows how the condition |x_i| ≥ δ > 0 for non-zero entries ensures that the effective noise variance in the state evolution converges to a value strictly below the threshold for the Bayesian denoiser to achieve perfect recovery, with probability 1 as n → ∞ under the sublinear sparsity regime. This leverages the fact that the denoiser, being Bayesian, has a unique fixed point at zero error when the input noise variance is below a certain level, and the support condition prevents any mass near zero that could lead to residual error. revision: yes

  2. Referee: [State-evolution derivation] The Onsager correction is obtained via state evolution for orthogonally invariant matrices. The derivation should include the explicit limiting equations for the variance terms under k, m = o(n) to confirm asymptotic Gaussianity of the estimation errors; standard AMP techniques do not automatically carry over without additional justification in this regime.

    Authors: We thank the referee for this suggestion. While the current derivation builds on the orthogonally invariant state evolution framework adapted to the sublinear limit, we acknowledge that additional explicit equations would improve accessibility. In the revision, we will expand the state-evolution derivation to include the explicit limiting expressions for the variance parameters (such as the effective noise variance and the Onsager correction term) as k, m = o(n), and provide a step-by-step justification for the asymptotic Gaussianity of the estimation errors, emphasizing the role of the sublinear sparsity in allowing the standard techniques to apply with the necessary modifications. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation applies standard state-evolution techniques to new sublinear regime

full rationale

The paper introduces GOAMP with an Onsager correction explicitly constructed from state-evolution analysis specialized to orthogonally invariant matrices and the sublinear-sparsity limit. The central theorem then proves, under the stated support-separation assumption, that the resulting iteration reaches the zero-error fixed point if and only if the measurement dimension exceeds a threshold that coincides with the known Gaussian-AMP threshold. This equivalence is obtained by direct fixed-point comparison within the derived state-evolution equations rather than by fitting parameters or renaming prior results. The support condition is an explicit modeling assumption required for the denoiser to separate signal from noise with probability 1; it is not smuggled in via self-citation or definition. All load-bearing steps therefore remain independent of the target claim and rest on externally verifiable state-evolution machinery.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on extensions of state evolution and Onsager corrections from prior approximate message-passing work, plus domain assumptions about matrix invariance and signal support; no new free parameters or invented entities are explicitly introduced in the abstract.

axioms (2)
  • domain assumption State evolution analysis holds for orthogonally invariant sensing matrices in the sublinear sparsity limit
    Invoked to design the Onsager correction that realizes asymptotic Gaussianity of estimation errors.
  • domain assumption The support of non-zero signals does not contain a neighborhood of the origin
    Required for the error-free reconstruction guarantee with Bayesian denoisers.

pith-pipeline@v0.9.0 · 5514 in / 1509 out tokens · 42596 ms · 2026-05-17T02:58:56.767605+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

  • IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear
    ?
    unclear

    Relation between the paper passage and the cited Recognition theorem.

    When the support of non-zero signals does not contain a neighborhood of the origin, GOAMP using Bayesian denoisers is proved to achieve error-free signal reconstruction ... if and only if the measurement dimension is larger than a threshold

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

72 extracted references · 72 canonical work pages

  1. [1]

    Compressed sensing,

    D. L. Donoho, “Compressed sensing,” IEEE Trans. Inf. Theory , vol. 52, no. 4, pp. 1289–1306, Apr. 2006

    work page 2006

  2. [2]

    Robust uncertaint y principles: Exact signal reconstruction from highly incomplete freque ncy informa- tion,

    E. J. Cand` es, J. Romberg, and T. Tao, “Robust uncertaint y principles: Exact signal reconstruction from highly incomplete freque ncy informa- tion,” IEEE Trans. Inf. Theory , vol. 52, no. 2, pp. 489–509, Feb. 2006

    work page 2006

  3. [3]

    Sparsity oracle i nequalities for the Lasso,

    F. Bunea, A. Tsybakov, and M. Wegkamp, “Sparsity oracle i nequalities for the Lasso,” Electron. J. Statist. , vol. 1, pp. 169–194, 2007

    work page 2007

  4. [4]

    High-dimensional generalized linear models and the lasso,

    S. A. van de Geer, “High-dimensional generalized linear models and the lasso,” Ann. Statist. , vol. 36, no. 2, pp. 614–645, Apr. 2008

    work page 2008

  5. [5]

    1-Bit compressive se nsing,

    P . T. Boufounos and R. G. Baraniuk, “1-Bit compressive se nsing,” in Proc. 42nd Ann. Conf. Inf. Sci. Syst. , Princeton, NJ, USA, Mar. 2008, pp. 16–21

    work page 2008

  6. [6]

    A practical algorithm f or the determination of the phase from image and diffraction plane pictures,

    R. W. Gerchberg and W. O. Saxton, “A practical algorithm f or the determination of the phase from image and diffraction plane pictures,” Optik, vol. 35, pp. 237–246, 1972

    work page 1972

  7. [7]

    Phase retrieval algorithms: a comparison ,

    J. R. Fienup, “Phase retrieval algorithms: a comparison ,” Appl. Opt. , vol. 21, no. 15, pp. 2758–2769, Aug. 1982

    work page 1982

  8. [8]

    Information-theoretic limits on spa rsity recovery in the high-dimensional and noisy setting,

    M. J. Wainwright, “Information-theoretic limits on spa rsity recovery in the high-dimensional and noisy setting,” IEEE Trans. Inf. Theory , vol. 55, no. 12, pp. 5728–5741, Dec. 2009

    work page 2009

  9. [9]

    Necessary and sufficient conditions for sparsity pattern recovery,

    A. K. Fletcher, S. Rangan, and V . K. Goyal, “Necessary and sufficient conditions for sparsity pattern recovery,” IEEE Trans. Inf. Theory , vol. 55, no. 12, pp. 5758–5772, Dec. 2009

    work page 2009

  10. [10]

    Information theor etic bounds for compressed sensing,

    S. Aeron, V . Saligrama, and M. Zhao, “Information theor etic bounds for compressed sensing,” IEEE Trans. Inf. Theory , vol. 56, no. 10, pp. 5111–5130, Oct. 2010

    work page 2010

  11. [11]

    Limits on support recovery w ith probabilistic models: An information-theoretic framework,

    J. Scarlett and V . Cevher, “Limits on support recovery w ith probabilistic models: An information-theoretic framework,” IEEE Trans. Inf. Theory , vol. 63, no. 1, pp. 593–620, Jan. 2017

    work page 2017

  12. [12]

    High dimensional regression with binary coefficients. estimating squared error and a phase transtit ion,

    D. Gamarnik and I. Zadik, “High dimensional regression with binary coefficients. estimating squared error and a phase transtit ion,” in Proc. 30th Annu. Conf. Learn. Theory , Amsterdam, Netherlands, Jul. 2017

    work page 2017

  13. [13]

    The all-or-nothing phen omenon in sparse linear regression,

    G. Reeves, J. Xu, and I. Zadik, “The all-or-nothing phen omenon in sparse linear regression,” Math. Stat. Learn. , vol. 3, no. 3/4, pp. 259– 313, 2020

    work page 2020

  14. [14]

    Regression shrinkage and selection vi a the lasso,

    R. Tibshirani, “Regression shrinkage and selection vi a the lasso,” J. R. Stat. Soc. B , vol. 58, no. 1, pp. 267–288, 1996

    work page 1996

  15. [15]

    An iterative t hresholding al- gorithm for linear inverse problems with a sparsity constra int,

    I. Daubechies, M. Defrise, and C. D. Mol, “An iterative t hresholding al- gorithm for linear inverse problems with a sparsity constra int,” Commun. Pure Appl. Math. , vol. 57, no. 11, pp. 1413–1457, Aug. 2004

    work page 2004

  16. [16]

    A fast iterative shrinkage-th resholding algorithm for linear inverse problems,

    A. Beck and M. Teboulle, “A fast iterative shrinkage-th resholding algorithm for linear inverse problems,” SIAM J. Imaging Sci. , vol. 2, no. 1, pp. 183–202, 2009

    work page 2009

  17. [17]

    An interior-point metho d for large- scale ℓ1-regularized logistic regression,

    K. Koh, S.-J. Kim, and S. Boyd, “An interior-point metho d for large- scale ℓ1-regularized logistic regression,” J. Mach. Learn. Res. , vol. 8, no. 54, pp. 1519–1555, Jul. 2007

    work page 2007

  18. [18]

    Gradi ent projection for sparse reconstruction: Application to compressed sens ing and other inverse problems,

    M. A. T. Figueiredo, R. D. Nowak, and S. J. Wright, “Gradi ent projection for sparse reconstruction: Application to compressed sens ing and other inverse problems,” IEEE J. Sel. Topics Signal Process. , vol. 1, no. 4, pp. 586–597, Dec. 2007

    work page 2007

  19. [19]

    Bregman it erative al- gorithms for ℓ1-minimization with applications to compressed sensing,

    W. Yin, S. Osher, D. Goldfarb, and J. Darbon, “Bregman it erative al- gorithms for ℓ1-minimization with applications to compressed sensing,” SIAM J. Imag. Sci. , vol. 1, no. 1, pp. 143–168, 2008

    work page 2008

  20. [20]

    Applications of Lagrangian-based alternat ing direction meth- ods and connections to split Bregman,

    E. Esser, “Applications of Lagrangian-based alternat ing direction meth- ods and connections to split Bregman,” UCLA Comput. Appl. Ma th., Tech. Rep. 09-31, 2009

    work page 2009

  21. [21]

    Alternating direction algorithm s for ℓ1-problems in compressive sensing,

    J. Y ang and Y . Zhang, “Alternating direction algorithm s for ℓ1-problems in compressive sensing,” SIAM J. Sci. Comput. , vol. 33, no. 1, pp. 250– 278, 2011

    work page 2011

  22. [22]

    Iterative hard thresho lding for compressed sensing,

    T. Blumensath and M. E. Davies, “Iterative hard thresho lding for compressed sensing,” Appl. Comput. Harmon. Anal. , vol. 27, no. 3, pp. 265–274, Nov. 2009

    work page 2009

  23. [23]

    Robust 1-bit compressed sens ing and sparse logistic regression: A convex programming approach,

    Y . Plan and R. V ershynin, “Robust 1-bit compressed sens ing and sparse logistic regression: A convex programming approach,” IEEE Trans. Inf. Theory, vol. 59, no. 1, pp. 482–494, Jan. 2013

    work page 2013

  24. [24]

    The generalized Lasso with non-linear observatio ns,

    ——, “The generalized Lasso with non-linear observatio ns,” IEEE Trans. Inf. Theory , vol. 62, no. 3, pp. 1528–1537, Mar. 2016

    work page 2016

  25. [25]

    LASSO wit h non-linear measurements is equivalent to one with linear measurements ,

    C. Thrampoulidis, E. Abbasi, and B. Hassibi, “LASSO wit h non-linear measurements is equivalent to one with linear measurements ,” in Adv. Neural Inf. Process. Syst. , vol. 28, Dec. 2015

    work page 2015

  26. [26]

    Robust 1- bit compressive sensing via binary stable embeddings of spa rse vectors,

    L. Jacques, J. N. Laska, P . T. Boufounos, and R. G. Barani uk, “Robust 1- bit compressive sensing via binary stable embeddings of spa rse vectors,” IEEE Trans. Inf. Theory , vol. 59, no. 4, pp. 2082–2102, Apr. 2013

    work page 2082

  27. [27]

    Binary iterative hard th resholding converges with optimal number of measurements for 1-bit com pressed sensing,

    N. Matsumoto and A. Mazumdar, “Binary iterative hard th resholding converges with optimal number of measurements for 1-bit com pressed sensing,” in Proc. 63rd Annu. Symp. F ound. Comput. Sci. , Denver, CO, USA, Oct.–Nov. 2022, pp. 813–822

    work page 2022

  28. [28]

    Message-pas sing algo- rithms for compressed sensing,

    D. L. Donoho, A. Maleki, and A. Montanari, “Message-pas sing algo- rithms for compressed sensing,” Proc. Nat. Acad. Sci. , vol. 106, no. 45, pp. 18 914–18 919, Nov. 2009

    work page 2009

  29. [29]

    Generalized approximate message passing f or estimation with random linear mixing,

    S. Rangan, “Generalized approximate message passing f or estimation with random linear mixing,” in Proc. 2011 IEEE Int. Symp. Inf. Theory , Saint Petersburg, Russia, Aug. 2011, pp. 2168–2172

    work page 2011

  30. [30]

    A CDMA multiuser detection algorithm on the basis of belief propagation,

    Y . Kabashima, “A CDMA multiuser detection algorithm on the basis of belief propagation,” J. Phys. A: Math. Gen. , vol. 36, no. 43, pp. 11 111– 11 121, Oct. 2003

    work page 2003

  31. [31]

    Message-pass ing de- quantization with applications to compressed sensing,

    U. S. Kamilov, V . K. Goyal, and S. Rangan, “Message-pass ing de- quantization with applications to compressed sensing,” IEEE Trans. Signal Process. , vol. 60, no. 12, pp. 6270–6281, Dec. 2012. SUBMITTED TO IEEE TRANSACTIONS ON INFORMA TION THEORY 33

    work page 2012

  32. [32]

    Compressive phase retrieva l via generalized approximate message passing,

    P . Schniter and S. Rangan, “Compressive phase retrieva l via generalized approximate message passing,” IEEE Trans. Signal Process. , vol. 63, no. 4, pp. 1043–1055, Feb. 2015

    work page 2015

  33. [33]

    Approximate messa ge passing with spectral initialization for generalized linear model s,

    M. Mondelli and R. V enkataramanan, “Approximate messa ge passing with spectral initialization for generalized linear model s,” J. Stat. Mech., vol. 2022, no. 11, p. 114003, Nov. 2022

    work page 2022

  34. [34]

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

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

    work page 2011

  35. [35]

    State evolution for gen eral approxi- mate message passing algorithms, with applications to spat ial coupling,

    A. Javanmard and A. Montanari, “State evolution for gen eral approxi- mate message passing algorithms, with applications to spat ial coupling,” Inf. Inference: A Journal of the IMA , vol. 2, no. 2, pp. 115–144, Dec. 2013

    work page 2013

  36. [36]

    Decentralized generalized approximate message-passing for tree-structured networks,

    K. Takeuchi, “Decentralized generalized approximate message-passing for tree-structured networks,” IEEE Trans. Inf. Theory , vol. 70, no. 10, pp. 7385–7409, Oct. 2024

    work page 2024

  37. [37]

    An iterative construction of solution s of the TAP equa- tions for the Sherrington-Kirkpatrick model,

    E. Bolthausen, “An iterative construction of solution s of the TAP equa- tions for the Sherrington-Kirkpatrick model,” Commun. Math. Phys., vol. 325, no. 1, pp. 333–366, Jan. 2014

    work page 2014

  38. [38]

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

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

    work page 2019

  39. [39]

    Mutual i nformation and optimality of approximate message-passing in random linea r estimation,

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

    work page 2020

  40. [40]

    Optimal errors and phase transitions in high-dimensional generalized linear models,

    J. Barbier, F. Krzakala, N. Macris, L. Miolane, and L. Zd eborov´ a, “Optimal errors and phase transitions in high-dimensional generalized linear models,” Proc. Nat. Acad. Sci. , vol. 116, no. 12, pp. 5451–5460, Mar. 2019

    work page 2019

  41. [41]

    On con vergence of approximate message passing,

    F. Caltagirone, L. Zdeborov´ a, and F. Krzakala, “On con vergence of approximate message passing,” in Proc. 2014 IEEE Int. Symp. Inf. Theory, Honolulu, HI, USA, Jul. 2014, pp. 1812–1816

    work page 2014

  42. [42]

    On t he convergence of approximate message passing with arbitrary matrices,

    S. Rangan, P . Schniter, A. Fletcher, and S. Sarkar, “On t he convergence of approximate message passing with arbitrary matrices,” IEEE Trans. Inf. Theory , vol. 65, no. 9, pp. 5339–5351, Sep. 2019

    work page 2019

  43. [43]

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

    J. Vila, P . Schniter, S. Rangan, F. Krzakala, and L. Zdeb orov´ a, “Adaptive damping and mean removal for the generalized approximate me ssage passing algorithm,” in Proc. 2015 IEEE Int. Conf. Acoust. Speech Signal Process., South Brisbane, Australia, Apr. 2015, pp. 2021–2025

    work page 2015

  44. [44]

    Swept approximate message passing for sparse estimation,

    A. Manoel, F. Krzakala, E. W. Tramel, and L. Zdeborov´ a, “Swept approximate message passing for sparse estimation,” in Proc. 32nd Int. Conf. Mach. Learn. , Lille, France, Jul. 2015, pp. 1123–1132

    work page 2015

  45. [45]

    Orthogonal AMP,

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

    work page 2020

  46. [46]

    V ector appr oximate message passing,

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

    work page 2019

  47. [47]

    Approximate message passin g with unitary transformation for robust bilinear recovery,

    Z. Y uan, Q. Guo, and M. Luo, “Approximate message passin g with unitary transformation for robust bilinear recovery,” IEEE Trans. Signal Process., vol. 69, pp. 617–630, 2021

    work page 2021

  48. [48]

    Expectation consistent appro ximate infer- ence,

    M. Opper and O. Winther, “Expectation consistent appro ximate infer- ence,” J. Mach. Learn. Res. , vol. 6, pp. 2177–2204, Dec. 2005

    work page 2005

  49. [49]

    Expectation propagation detection for high-order high-d imensional MIMO systems,

    J. C´ espedes, P . M. Olmos, M. S´ anchez-Fern´ andez, and F. Perez-Cruz, “Expectation propagation detection for high-order high-d imensional MIMO systems,” IEEE Trans. Commun. , vol. 62, no. 8, pp. 2840–2849, Aug. 2014

    work page 2014

  50. [50]

    Rigorous dynamics of expectation-propa gation-based sig- nal recovery from unitarily invariant measurements,

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

    work page 2020

  51. [51]

    Th e mutual information in random linear estimation beyond i.i.d. matr ices,

    J. Barbier, N. Macris, A. Maillard, and F. Krzakala, “Th e mutual information in random linear estimation beyond i.i.d. matr ices,” in Proc. 2018 IEEE Int. Symp. Inf. Theory , V ail, CO, USA, Jun. 2018, pp. 1390– 1394

    work page 2018

  52. [52]

    Random linear estimatio n with rotationally-invariant designs: Asymptotics at high temp erature,

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

    work page 2024

  53. [53]

    Universality of approxim ate message passing algorithms and tensor networks,

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

    work page 2024

  54. [54]

    Spectral universality i n regularized linear regression with nearly deterministic sensing matri ces,

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

    work page 2024

  55. [55]

    V ector appr oximate message passing for the generalized linear model,

    P . Schniter, S. Rangan, and A. K. Fletcher, “V ector appr oximate message passing for the generalized linear model,” in Proc. 50th Asilomar Conf. Signals, Systems, Comput. , Pacific Grove, CA, USA, Nov. 2016, pp. 1525–1529

    work page 2016

  56. [56]

    Inference i n deep networks in high dimensions,

    A. K. Fletcher, S. Rangan, and P . Schniter, “Inference i n deep networks in high dimensions,” in Proc. 2018 IEEE Int. Symp. Inf. Theory , V ail, CO, USA, Jun. 2018, pp. 1884–1888

    work page 2018

  57. [57]

    A theory of solvin g TAP equations for Ising models with general invariant random ma trices,

    M. Opper, B. C ¸ akmak, and O. Winther, “A theory of solvin g TAP equations for Ising models with general invariant random ma trices,” J. Phys. A: Math. Theor . , vol. 49, no. 11, p. 114002, Feb. 2016

    work page 2016

  58. [58]

    Approximate message passing algorithms for ro tationally in- variant matrices,

    Z. Fan, “Approximate message passing algorithms for ro tationally in- variant matrices,” Ann. Statist. , vol. 50, no. 1, pp. 197–224, Feb. 2022

    work page 2022

  59. [59]

    Estim ation in ro- tationally invariant generalized linear models via approx imate message passing,

    R. V enkataramanan, K. K¨ ogler, and M. Mondelli, “Estim ation in ro- tationally invariant generalized linear models via approx imate message passing,” in Proc. 39th Int. Conf. Mach. Learn. , Baltimore, MD, USA, Jul. 2022

    work page 2022

  60. [60]

    Bayes-optimal convolutional AMP,

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

    work page 2021

  61. [61]

    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

    work page 2022

  62. [62]

    Rigorous dynamics of expect ation- propagation signal detection via the conjugate gradient me thod,

    K. Takeuchi and C.-K. Wen, “Rigorous dynamics of expect ation- propagation signal detection via the conjugate gradient me thod,” in Proc. 18th IEEE Int. W orkshop Sig. Process. Advances Wirel. Commun., Sapporo, Japan, Jul. 2017, pp. 88–92

    work page 2017

  63. [63]

    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

    work page 2022

  64. [64]

    All-or-nothing sta tistical and computational phase transitions in sparse spiked matrix es timation,

    J. Barbier, N. Macris, and C. Rush, “All-or-nothing sta tistical and computational phase transitions in sparse spiked matrix es timation,” in Adv. Neural Inf. Process. Syst. , vol. 33, Dec. 2020, pp. 14 915–14 926

    work page 2020

  65. [65]

    Fundamental limits and algorithms for sp arse linear regression with sublinear sparsity,

    L. V . Truong, “Fundamental limits and algorithms for sp arse linear regression with sublinear sparsity,” J. Mach. Learn. Res. , vol. 24, no. 64, pp. 1–49, 2023

    work page 2023

  66. [66]

    Generalized approximate message-passi ng for compressed sensing with sublinear sparsity,

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

    work page 2025

  67. [67]

    Orthogonal approximate message-passing for subl inear sparsity,

    ——, “Orthogonal approximate message-passing for subl inear sparsity,” submitted to 2026 IEEE Int. Conf. Acoust. Speech Signal Process

    work page 2026

  68. [68]

    Orthogonal approximate message-passing for spat ially coupled linear models,

    ——, “Orthogonal approximate message-passing for spat ially coupled linear models,” IEEE Trans. Inf. Theory , vol. 70, no. 1, pp. 594–631, Jan. 2024

    work page 2024

  69. [69]

    Signal recovery from rand om mea- surements via orthogonal matching pursuit,

    J. A. Tropp and A. C. Gilbert, “Signal recovery from rand om mea- surements via orthogonal matching pursuit,” IEEE Trans. Inf. Theory , vol. 53, no. 12, pp. 4655–4666, Dec. 2007

    work page 2007

  70. [70]

    Adaptive restart for acc elerated gradient schemes,

    B. O’Donoghue and E. Cand` es, “Adaptive restart for acc elerated gradient schemes,” F ound. Comput. Math., vol. 15, no. 3, pp. 715–732, Jun. 2015

    work page 2015

  71. [71]

    A bound for the error in the normal approximat ion to the distribution of a sum of dependent random variables,

    C. Stein, “A bound for the error in the normal approximat ion to the distribution of a sum of dependent random variables,” in 6th Berkeley Symp. Math. Statist. Prob. , vol. 2, 1972, pp. 583–602

    work page 1972

  72. [72]

    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

    work page 2022