Pith. sign in

REVIEW 2 major objections 2 minor 27 references

Complex Approximate Message Passing with Non-separable Denoising

T0 review · 2 major / 2 minor · reviewed 2026-05-09 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read Complex AMP with non-separable denoisers admits scalar state evolution via real-valued lifting

desk verdict The lifting trick for complex non-separable AMP state evolution is the main contribution, but whether it truly collapses to scalar recursions still needs checking. read the letter →

arxiv 2604.21115 v1 submitted 2026-04-22 eess.SP stat.AP

Vishnu Teja Kunde , Alessandro Mirri , Jean-Francois Chamberland , Enrico Paolini This is my paper · ORCID
classification eess.SPstat.AP
keywords approximatemessagepassingstateevolutionnon-separabledenoisingcomplexsignalsWirtingerderivativescompressedsensinggroupsparsityOTFS
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes a unified state evolution theory for approximate message passing on complex-valued signals when the denoising functions are non-separable. Earlier advances covered complex AMP and non-separable functions in isolation, but lacked a joint treatment. The authors lift the complex problem into an augmented real-valued system, apply a many-to-one canonical transformation back to the complex domain, and obtain Onsager correction terms through Wirtinger derivatives; the resulting recursions remain scalar despite the non-separable structure. The construction extends directly to matrix-valued AMP and supports joint sparsity patterns such as simultaneous group and element sparsity. Numerical checks confirm that the predicted state evolution tracks actual algorithm behavior and that the non-separable complex denoisers improve recovery over separable or real-valued baselines.

What carries the argument

Augmented real-valued system with many-to-one canonical transformation, whose Onsager correction employs Wirtinger derivatives to produce scalar complex state evolution recursions for non-separable denoisers

What would settle it

Empirical observation that the predicted scalar state evolution deviates from measured AMP performance in a complex non-separable denoising instance would falsify the claim.

Watch

Extended reading notes

Core claim

The article establishes state evolution for complex approximate message passing with non-separable denoising functions by constructing an augmented real-valued system that lifts the problem to higher dimension and recovers the complex domain through a many-to-one canonical transformation. Under this lift the Onsager correction uses Wirtinger derivatives and the state evolution collapses to scalar complex recursions. The same framework extends to the matrix-valued case, enabling simultaneous handling of multiple feature vectors and joint structural constraints such as group-plus-element sparsity.

Load-bearing premise

The augmented real-valued lifting together with the many-to-one canonical transformation and Wirtinger derivatives correctly produces scalar complex state evolution recursions even when the denoisers are non-separable.

Editorial extensions

If this is right

  • State evolution accurately predicts performance in numerical experiments on complex recovery tasks.
  • The framework extends to matrix-valued AMP, allowing simultaneous processing of multiple feature vectors.
  • Complex non-separable denoising enables exploitation of joint structures such as simultaneous group and element sparsity.
  • The complex sparse group LASSO instantiation applies to preamble detection in OTFS-based unsourced random access.

Reading between the lines

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

  • The lifting technique may extend to other iterative algorithms that currently lack state evolution in the complex non-separable regime.
  • Applications in wireless communications could benefit from joint sparsity exploitation in complex channels without requiring separability assumptions.
  • Similar real-valued augmentations might simplify analysis of non-separable functions in related high-dimensional inference settings.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper claims to establish state evolution for complex approximate message passing (AMP) with non-separable denoising functions. It constructs an augmented real-valued system via lifting, applies real-valued AMP, and recovers scalar complex recursions through a many-to-one canonical transformation that incorporates Wirtinger derivatives in the Onsager correction term. The framework extends to matrix-valued AMP and is instantiated on complex sparse group LASSO for OTFS-based unsourced random access, with numerical experiments validating the state evolution predictions.

Significance. If the central derivation holds, the work supplies a previously missing theoretical tool for complex AMP under non-separable denoisers, enabling exploitation of joint structures such as simultaneous group and element sparsity. This directly supports improved recovery algorithms in communications applications and unifies prior separate advances in matrix AMP, complex AMP, and non-separable AMP.

major comments (2)
  1. [Main theoretical derivation (lifting and canonical transformation)] The lifting construction and subsequent many-to-one canonical transformation (described in the main theoretical section following the abstract) are asserted to collapse the real-valued covariance tracking of non-separable AMP into scalar complex state evolution recursions. However, standard real AMP state evolution for non-separable denoisers maintains the full noise covariance matrix; the manuscript does not explicitly demonstrate why the transformation forces all off-diagonal cross terms to vanish or to depend only on a single complex variance parameter, nor does it state the precise symmetry assumptions on the lifted noise or sensing matrix required for this reduction.
  2. [State evolution recursions] The claim that the Onsager correction naturally involves Wirtinger derivatives and yields scalar recursions despite non-separability (abstract and subsequent state-evolution equations) is load-bearing for the entire contribution. Without a self-contained proof or explicit verification that the many-to-one mapping eliminates the extra covariance degrees of freedom, the reduction to scalar complex form remains unverified and could require additional assumptions not stated in the current presentation.
minor comments (2)
  1. [Preliminaries and notation] Notation for the augmented real-valued vectors and the canonical transformation mapping could be clarified with an explicit diagram or table relating the complex, real-augmented, and transformed variables.
  2. [Matrix-valued extension] The extension to the matrix-valued setting is stated but the corresponding state-evolution equations are only sketched; a dedicated subsection with the full recursion would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of the manuscript and the constructive comments on the theoretical sections. The feedback highlights areas where additional explicit derivations will strengthen the presentation. We address each major comment below and will revise the manuscript to incorporate the requested clarifications.

read point-by-point responses

  1. Referee: [Main theoretical derivation (lifting and canonical transformation)] The lifting construction and subsequent many-to-one canonical transformation (described in the main theoretical section following the abstract) are asserted to collapse the real-valued covariance tracking of non-separable AMP into scalar complex state evolution recursions. However, standard real AMP state evolution for non-separable denoisers maintains the full noise covariance matrix; the manuscript does not explicitly demonstrate why the transformation forces all off-diagonal cross terms to vanish or to depend only on a single complex variance parameter, nor does it state the precise symmetry assumptions on the lifted noise or sensing matrix required for this reduction.

    Authors: We appreciate this observation. The reduction follows from the circular symmetry of the i.i.d. complex Gaussian sensing matrix and noise, which induces a block structure in the lifted real-valued covariance that is preserved under the many-to-one canonical transformation, causing off-diagonal cross terms to vanish and leaving only a single complex variance parameter. This symmetry is used throughout the state-evolution analysis, but we agree that an explicit statement and derivation would improve clarity. In the revision we will add a dedicated lemma immediately after the lifting construction that states the precise assumptions (i.i.d. circularly symmetric complex Gaussian entries) and proves the vanishing of the extra covariance degrees of freedom. revision: yes

  2. Referee: [State evolution recursions] The claim that the Onsager correction naturally involves Wirtinger derivatives and yields scalar recursions despite non-separability (abstract and subsequent state-evolution equations) is load-bearing for the entire contribution. Without a self-contained proof or explicit verification that the many-to-one mapping eliminates the extra covariance degrees of freedom, the reduction to scalar complex form remains unverified and could require additional assumptions not stated in the current presentation.

    Authors: We agree that a more self-contained verification strengthens the contribution. The appearance of Wirtinger derivatives in the Onsager term is a direct consequence of applying the real-valued AMP state evolution to the lifted system and then projecting back via the canonical mapping; the mapping eliminates the extra covariance parameters precisely because of the circular symmetry already invoked in the lifting step. To address the concern we will expand the state-evolution section with an explicit step-by-step verification (including an appendix calculation) that shows how the many-to-one transformation reduces the full matrix covariance to the scalar complex recursion, and we will list all required assumptions at the start of the section. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: state evolution derived via lifting construction without reduction to self-defined inputs or fitted parameters

full rationale

The paper's central derivation lifts the complex non-separable AMP problem to an augmented real-valued system, applies standard real AMP, then uses a many-to-one canonical transformation with Wirtinger derivatives to recover scalar complex state evolution recursions. This is presented as a first-principles construction in the abstract and reader's summary, with no quoted equations or claims showing that the resulting recursions are equivalent by definition to quantities fitted from the authors' prior work or self-cited uniqueness theorems. No self-citation load-bearing steps, no fitted-input-called-prediction, and no ansatz smuggled via citation are evident. The derivation is self-contained against the lifting and transformation steps, consistent with the reader's assessment of independence from fitted values.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The derivation rests on the lifting construction and standard large-system assumptions typical of AMP state evolution; no free parameters, new entities, or ad-hoc axioms are visible in the abstract.

assumptions (1)
  • domain assumption Large-system limit and i.i.d. matrix entries under which state evolution holds
    Standard background assumption for AMP analyses, invoked implicitly by the claim of scalar recursions.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Complex Approximate Message Passing with Non-separable Denoising." pith.science (2026). https://pith.science/paper/2604.21115

@misc{pith2026260421115,
  author       = {Pith},
  title        = {Pith review of: Complex Approximate Message Passing with Non-separable Denoising},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2604.21115}},
  note         = {Machine review of arXiv:2604.21115}
}
read the original abstract

Approximate Message Passing (AMP) is a general framework for iterative algorithms, originally developed for compressed sensing and later extended to a wide range of high-dimensional inference problems. Although recent work has advanced matrix AMP, complex AMP, and AMP for non-separable functions independently, a unified state evolution theory for complex AMP with non-separable denoisers has been lacking. This article fills that gap by establishing state evolution in the setting of complex, non-separable denoising functions. The proposed approach constructs an augmented real-valued system that lifts the problem to a higher-dimensional space, then recovers the complex domain through a many-to-one canonical transformation. Under this construction, the Onsager correction naturally involves Wirtinger derivatives, and the resulting state evolution reduces to scalar complex recursions despite the non-separable structure of the denoisers. The framework extends to the matrix-valued setting, accommodating multiple feature vectors simultaneously. This generalization enables AMP to exploit joint structural constraints, such as simultaneous group and element sparsity, in complex-valued recovery problems. The complex sparse group least absolute shrinkage and selection operator (LASSO) serves as a key instantiation, motivated by preamble detection in Orthogonal Time-Frequency Space (OTFS)-based unsourced random access. Numerical experiments confirm that state evolution accurately predicts performance and show that complex non-separable denoising can produce significant gains over separable and real-valued alternatives.

Figures

Figures reproduced from arXiv: 2604.21115 by the authors.

Figure 1
Figure 1. Convergence of complex AMP and complex ISTA with the non-separable SGL denoiser. The dashed curve shows the state evolution [PITH_FULL_IMAGE:figures/full_fig_p016_1.png] view at source ↗
Figure 2
Figure 2. NMSE versus SNR for four AMP variants. The dashed curve shows the SE prediction for Complex SGL. Parameters: [PITH_FULL_IMAGE:figures/full_fig_p017_2.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages

  1. [1]

    Message-passing algorithms for compressed sensing,

    D. L. Donoho, A. Maleki, and A. Montanari, “Message-passing algorithms for compressed sensing,”Proc. National Academy of Sciences, vol. 106, no. 45, pp. 18914–18919, 2009

    work page 2009

  2. [2]

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

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

    work page 2011

  3. [3]

    Universality in polytope phase transitions and message passing algorithms,

    M. Bayati, M. Lelarge, and A. Montanari, “Universality in polytope phase transitions and message passing algorithms,”The Annals of Applied Probability, vol. 25, no. 2, pp. 753–822, 2015

    work page 2015

  4. [4]

    Bilinear generalized approximate message passing–Part I: Derivation,

    J. T. Parker, P. Schniter, and V . Cevher, “Bilinear generalized approximate message passing–Part I: Derivation,”IEEE Trans. Signal Process., vol. 62, no. 22, pp. 5839–5853, 2014

    work page 2014

  5. [5]

    Bilinear generalized approximate message passing–Part II: Applications,

    J. T. Parker, P. Schniter, and V . Cevher, “Bilinear generalized approximate message passing–Part II: Applications,”IEEE Trans. Signal Process., vol. 62, no. 22, pp. 5854–5867, 2014. April 24, 2026 DRAFT 28

    work page 2014

  6. [6]

    From denoising to compressed sensing,

    C. A. Metzler, A. Maleki, and R. G. Baraniuk, “From denoising to compressed sensing,”IEEE Trans. Inf. Theory, vol. 62, no. 9, pp. 5117–5144, 2016

    work page 2016

  7. [7]

    Vector approximate message passing,

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

    work page 2019

  8. [8]

    Mixed regression via approximate message passing,

    N. Tan and R. Venkataramanan, “Mixed regression via approximate message passing,”J. of Machine Learning Research, vol. 24, no. 317, pp. 1–44, 2023

    work page 2023

Show all 27 references
  1. [9]

    Fast, robust approximate message passing,

    M. Ivkov and T. Schramm, “Fast, robust approximate message passing,” inACM Symp. on Theory of Computing (STOC), 2025, pp. 2237–2248

    2025

  2. [10]

    Approximate message-passing decoder and capacity achieving sparse superposition codes,

    J. Barbier and F. Krzakala, “Approximate message-passing decoder and capacity achieving sparse superposition codes,”IEEE Trans. Inf. Theory, vol. 63, no. 8, pp. 4894–4927, 2017

    2017

  3. [11]

    Capacity-achieving sparse superposition codes via approximate message passing decoding,

    C. Rush, A. Greig, and R. Venkataramanan, “Capacity-achieving sparse superposition codes via approximate message passing decoding,” IEEE Trans. Inf. Theory, vol. 63, no. 3, pp. 1476–1500, 2017

    2017

  4. [12]

    Unsourced random access with coded compressed sensing: Integrating AMP and belief propagation,

    V . K. Amalladinne, A. K. Pradhan, C. Rush, J.-F. Chamberland, and K. R. Narayanan, “Unsourced random access with coded compressed sensing: Integrating AMP and belief propagation,”IEEE Trans. Inf. Theory, vol. 68, no. 4, pp. 2384–2409, 2021

    2021

  5. [13]

    State evolution for approximate message passing with non-separable functions,

    R. Berthier, A. Montanari, and P.-M. Nguyen, “State evolution for approximate message passing with non-separable functions,”IMA Inf. and Inference, vol. 9, no. 1, pp. 33–79, 2020

    2020

  6. [14]

    Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing,

    D. L. Donoho, A. Javanmard, and A. Montanari, “Information-theoretically optimal compressed sensing via spatial coupling and approximate message passing,”IEEE Trans. Inf. Theory, vol. 59, no. 11, pp. 7434–7464, 2013

    2013

  7. [15]

    A unifying tutorial on approximate message passing,

    O. Y . Feng, R. Venkataramanan, C. Rush, and R. J. Samworth, “A unifying tutorial on approximate message passing,”Foundations and Trends® in Machine Learning, vol. 15, no. 4, pp. 335–536, 2022

    2022

  8. [16]

    Graph-based approximate message passing iterations,

    C. Gerbelot and R. Berthier, “Graph-based approximate message passing iterations,”Inf. and Inference: A J. of the IMA, vol. 12, pp. 2562–2628, 2023

    2023

  9. [17]

    Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP),

    A. Maleki, L. Anitori, Z. Yang, and R. G. Baraniuk, “Asymptotic analysis of complex LASSO via complex approximate message passing (CAMP),”IEEE Trans. Inf. Theory, vol. 59, no. 7, pp. 4290–4308, 2013

    2013

  10. [18]

    Sparse activity detection for massive connectivity,

    Z. Chen, F. Sohrabi, and W. Yu, “Sparse activity detection for massive connectivity,”IEEE Trans. Signal Process., vol. 66, no. 7, pp. 1890–1904, 2018

    1904

  11. [19]

    Optimization-based AMP for phase retrieval: The impact of initialization andℓ 2 regularization,

    J. Ma, J. Xu, and A. Maleki, “Optimization-based AMP for phase retrieval: The impact of initialization andℓ 2 regularization,”IEEE Trans. Inf. Theory, vol. 65, no. 6, pp. 3600–3629, 2019

    2019

  12. [20]

    Joint message detection and channel estimation for unsourced random access in cell-free user-centric wireless networks,

    B. Çakmak, E. Gkiouzepi, M. Opper, and G. Caire, “Joint message detection and channel estimation for unsourced random access in cell-free user-centric wireless networks,”IEEE Trans. Inf. Theory, vol. 71, no. 5, pp. 3614–3643, 2025

    2025

  13. [21]

    Iterative recovery algorithms for complex-valued distributed compressed sensing,

    E. Sterk and R. F. H. Fischer, “Iterative recovery algorithms for complex-valued distributed compressed sensing,” in2025 14th International ITG Conference on Systems, Communications and Coding (SCC), 2025

    2025

  14. [22]

    A sparse-group lasso,

    N. Simon, J. Friedman, T. Hastie, and R. Tibshirani, “A sparse-group lasso,”J. of Computational and Graphical Statistics, vol. 22, no. 2, pp. 231–245, 2013

    2013

  15. [23]

    Model selection and estimation in regression with grouped variables,

    M. Yuan and Y . Lin, “Model selection and estimation in regression with grouped variables,”J. of the Royal Statistical Society. Series B (Statistical Methodology), vol. 68, no. 1, pp. 49–67, 2006

    2006

  16. [24]

    Approximate message passing for multi-preamble detection in OTFS random access,

    A. Mirri, V . T. Kunde, E. Paolini, and J.-F. Chamberland, “Approximate message passing for multi-preamble detection in OTFS random access,” 2025, arXiv preprint arXiv:2509.03980

    2025

  17. [25]

    State evolution for general approximate message passing algorithms, with applications to spatial coupling,

    A. Javanmard and A. Montanari, “State evolution for general approximate message passing algorithms, with applications to spatial coupling,”IMA Inf. and Inference, vol. 2, no. 2, pp. 115–144, 2013

    2013

  18. [26]

    Householder dice: A matrix-free algorithm for simulating dynamics on gaussian and random orthogonal ensembles,

    Y . M. Lu, “Householder dice: A matrix-free algorithm for simulating dynamics on gaussian and random orthogonal ensembles,”IEEE Trans. Inf. Theory, vol. 67, no. 12, pp. 8264–8272, 2021

    2021

  19. [27]

    Asymptotic statistical analysis of sparse group LASSO via approximate message passing,

    K. Chen, Z. Bu, and S. Xu, “Asymptotic statistical analysis of sparse group LASSO via approximate message passing,” inProc. Joint European Conf. on Machine Learning and Knowledge Discovery in Databases. Springer, 2021, pp. 510–526. DRAFT April 24, 2026

    2021

Pith tools

Reviewed May 9, 2026 · model on record in the stance chip above.