pith. sign in

arxiv: 2604.13511 · v1 · submitted 2026-04-15 · 💻 cs.IT · cond-mat.dis-nn· math.IT

Phase transition in compressed sensing using log-sum penalty and adaptive smoothing

Keisuke Morita , Federico Ricci-Tersenghi , Masayuki Ohzeki This is my paper

Pith reviewed 2026-05-10 12:54 UTC · model grok-4.3

classification 💻 cs.IT cond-mat.dis-nnmath.IT
keywords compressed sensingphase transitionlog-sum penaltyapproximate message passingreplica methodstate evolutionsparse recovery
0
0 comments X

The pith

Adaptive smoothing of the log-sum penalty inside approximate message passing extends the exact recovery region beyond ℓ1 minimization for Gaussian matrices.

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

Recovering sparse signals from underdetermined linear measurements is a core problem where ℓ1 minimization works reliably but leaves a performance gap due to its bias. The authors replace it with the nonconvex log-sum penalty, which promotes sparsity more strongly but tends to destabilize standard solvers. They stabilize the approach by adding an adaptive smoothing schedule inside the approximate message passing iterations. Analysis with the replica method and state evolution then shows that the resulting algorithm achieves exact recovery over a measurably larger set of measurement rates and sparsities than ℓ1, although metastable states still block the information-theoretic optimum.

Core claim

The adaptive smoothing strategy applied to the log-sum penalty within the AMP framework yields a larger typical exact-recovery threshold than ℓ1-norm minimization, as computed by the replica method and state evolution for Gaussian measurement matrices, although metastable states prevent the method from reaching the Bayes-optimal limit.

What carries the argument

The adaptive smoothing schedule that gradually reduces the nonconvexity of the log-sum penalty during AMP iterations, keeping the algorithm stable while preserving the sparsity-promoting effect.

If this is right

  • Exact recovery succeeds in a larger region of the measurement-rate versus sparsity plane than with ℓ1 minimization.
  • Replica and state-evolution analysis correctly locates the phase transition for the stabilized log-sum method.
  • Metastable states remain and keep the achievable threshold below the information-theoretic bound.
  • The same adaptive stabilization idea applies to other nonconvex penalties used in sparse recovery.

Where Pith is reading between the lines

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

  • Practical imaging or sensor-array tasks that currently rely on ℓ1 could see improved reconstruction rates if the adaptive schedule is implemented.
  • Further algorithmic changes aimed at escaping metastable states might close the remaining gap to the information-theoretic limit.
  • The phase-transition analysis supplies a concrete benchmark that later iterative methods for nonconvex compressed sensing can be tested against.

Load-bearing premise

That the adaptive smoothing can be inserted into the AMP iterations without creating new instabilities or biases that would invalidate the replica-symmetric and state-evolution predictions.

What would settle it

Monte Carlo simulations of the adaptive AMP algorithm on random Gaussian matrices that either match or deviate from the exact-recovery threshold predicted by state evolution.

Figures

Figures reproduced from arXiv: 2604.13511 by Federico Ricci-Tersenghi, Keisuke Morita, Masayuki Ohzeki.

Figure 1
Figure 1. Figure 1: FIG. 1. Thresholding function [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. Time evolution of (a) MSE and (b) [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Time evolution of MSE with the adaptive smoothing [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. Critical measurement rate [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. Vector field of the SE dynamics with adaptive smoothing on the MSE– [PITH_FULL_IMAGE:figures/full_fig_p019_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. Number of iterations for AMP to converge as a function of measurement rate [PITH_FULL_IMAGE:figures/full_fig_p020_6.png] view at source ↗
read the original abstract

In many real-world problems, recovering sparse signals from underdetermined linear systems remains a fundamental challenge. Although $\ell_1$ norm minimization is widely used, it suffers from estimation bias that prevents it from reaching the Bayes-optimal reconstruction limit. Nonconvex alternatives, such as the log-sum penalty, have been proposed to promote stronger sparsity. However, maintaining their algorithmic stability is challenging. To address this challenge, we introduce an adaptive smoothing strategy within an approximate message passing framework to mitigate algorithmic instability. Furthermore, we evaluate the typical exact-recovery threshold for Gaussian measurement matrices using the replica method and state evolution. The results indicate that the adaptive method achieves exact recovery over a broader region than $\ell_1$ norm minimization, although metastable states hinder reaching the information-theoretic limit.

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 / 1 minor

Summary. The manuscript proposes an adaptive smoothing strategy integrated into the approximate message passing (AMP) framework to stabilize the nonconvex log-sum penalty for sparse signal recovery from underdetermined linear measurements. It applies the replica method and state evolution to determine the typical exact-recovery threshold under Gaussian measurement matrices, claiming that the resulting adaptive scheme enlarges the exact-recovery region relative to standard ℓ₁ minimization while metastable states still prevent attainment of the information-theoretic limit.

Significance. If the analysis is shown to correctly incorporate the adaptive rule, the result would supply a concrete, theoretically characterized improvement in phase-transition thresholds for compressed sensing, illustrating how state-dependent stabilization can extend the utility of nonconvex penalties beyond ℓ₁ without sacrificing the tractability of AMP. The explicit use of replica and state-evolution machinery is a strength, as it yields falsifiable predictions for the location of the recovery threshold.

major comments (2)
  1. [Abstract] Abstract: the central claim that the adaptive log-sum method achieves exact recovery over a broader region than ℓ₁ rests on replica and state-evolution calculations. The abstract gives no indication that the fixed-point equations or stability analysis were re-derived to accommodate the state-dependent smoothing parameter inside the proximal operator or Onsager correction term. Standard state-evolution derivations assume an iteration-independent denoiser; without the modified equations or a demonstration that the extra terms vanish, the reported enlargement of the recovery region is not guaranteed by the analysis.
  2. [Abstract] Abstract: no derivation details, error bounds, or numerical checks of the replica/state-evolution thresholds are supplied. Because the adaptive smoothing rule is the novel ingredient, the absence of even a sketch of the modified state-evolution recursion or a comparison against non-adaptive log-sum baselines leaves the quantitative location of the phase boundary unsupported.
minor comments (1)
  1. [Abstract] The abstract would benefit from a one-sentence statement of the precise adaptive update rule (e.g., how the smoothing parameter evolves with iteration or residual) so that readers can immediately judge its compatibility with existing AMP analyses.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments correctly identify that the abstract does not sufficiently highlight the technical adaptations made to the state-evolution analysis. We address each point below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim that the adaptive log-sum method achieves exact recovery over a broader region than ℓ₁ rests on replica and state-evolution calculations. The abstract gives no indication that the fixed-point equations or stability analysis were re-derived to accommodate the state-dependent smoothing parameter inside the proximal operator or Onsager correction term. Standard state-evolution derivations assume an iteration-independent denoiser; without the modified equations or a demonstration that the extra terms vanish, the reported enlargement of the recovery region is not guaranteed by the analysis.

    Authors: We agree that the abstract should explicitly note the re-derivation. In the full manuscript (Section 3), the state-evolution equations are adapted for the state-dependent smoothing parameter. We show that the additional derivative terms in the Onsager correction arising from the dependence on the current iterate vanish in the large-system limit for the chosen adaptive rule, so the standard fixed-point analysis continues to apply with the updated denoiser. We will revise the abstract to state that the fixed-point equations and stability analysis have been re-derived to accommodate the adaptive smoothing. revision: yes

  2. Referee: [Abstract] Abstract: no derivation details, error bounds, or numerical checks of the replica/state-evolution thresholds are supplied. Because the adaptive smoothing rule is the novel ingredient, the absence of even a sketch of the modified state-evolution recursion or a comparison against non-adaptive log-sum baselines leaves the quantitative location of the phase boundary unsupported.

    Authors: We acknowledge that the abstract lacks a sketch and supporting checks. The manuscript derives the modified state-evolution recursion in Section 3 and presents numerical validation of the thresholds (including direct comparisons to non-adaptive log-sum) in Section 5. To address the concern, we will insert a concise sketch of the adapted recursion into the abstract and add explicit error bounds on the numerically located phase-transition points in the revised version. revision: yes

Circularity Check

0 steps flagged

Replica/state-evolution analysis of adaptive log-sum penalty is self-contained

full rationale

The paper applies the standard replica method and state-evolution formalism to compute the typical exact-recovery threshold for the proposed adaptive-smoothing variant of the log-sum penalty inside AMP. The abstract and description indicate that the adaptive rule is inserted into the iteration and the resulting fixed-point equations are solved in the usual way; no equation is shown to be defined in terms of its own output, no fitted parameter is relabeled as a prediction, and no load-bearing uniqueness claim rests on a self-citation whose content is itself unverified. The comparison to the ℓ1 threshold is obtained by repeating the same external machinery on a different penalty, which is a legitimate (if model-dependent) calculation rather than a tautology. The derivation therefore remains independent of its own target result.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The analysis rests on standard compressed-sensing assumptions and statistical-physics tools whose applicability to the non-convex case is taken as given.

axioms (2)
  • domain assumption Measurement matrix entries are i.i.d. Gaussian
    Required for the typical exact-recovery threshold calculation via replica and state evolution.
  • domain assumption Replica method and state evolution remain valid for the adaptively smoothed log-sum penalty
    Central to locating the phase-transition boundary.

pith-pipeline@v0.9.0 · 5435 in / 1244 out tokens · 59550 ms · 2026-05-10T12:54:32.453385+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [1]

    = R Dξ1f(ξ 1) n . Then, by repeatedly applying the following Gaussian integral formula, Z Dξexp − λ 2 (Aξ+B) 2 = 1 +λA 2 −1/2 exp −1 2 λB2 1 +λA 2 ,(B3) 25 we obtain the following expression for smalln: nβΨ =−log 1 +n q−2m+ρ σ2 +Q−q − 1 2 1 + Q−q σ2 − n 2 = n 2 q−2m+ρ σ2 +Q−q + log 1 + Q−q σ2 +O(n 2).(B4) Next, the eΨ term (Eq. (33)) is simplified as foll...

    work page

  2. [2]

    The replica indices a, b∈ {1,

    1RSB free energy density We consider the following block structure of the order parameters. The replica indices a, b∈ {1, . . . , n}are divided inton/m 1 blocks of sizem 1. Each replica indexais uniquely rep- resented using a block indexa 0 ∈ {1, . . . , n/m1}and an intra-block indexa 1 ∈ {1, . . . , m1} asa=m 1(a0 −1) +a 1. Based on this hierarchical str...

    work page

  3. [3]

    By deriving the condition thatq 1 −q RS does not expand per iteration, the AT stability condition can be determined

    dA T stability condition To obtain the dAT stability condition, we fix the order parameters other thanq 1 and ˜q1 at their RS values, denoted byQ RS,q RS,m RS, eQRS, ˜qRS and ˜mRS, and derive the asymptotic self-consistent equation ofq 1 −q RS whenq 1 ≈q RS. By deriving the condition thatq 1 −q RS does not expand per iteration, the AT stability condition ...

    work page

  4. [4]

    Lustig, D

    M. Lustig, D. Donoho, and J. M. Pauly, Magn. Reson. Med.58, 1182 (2007)

    work page 2007

  5. [5]

    M. F. Duarte, M. A. Davenport, D. Takhar, J. N. Laska, T. Sun, K. F. Kelly, and R. G. Baraniuk, IEEE Signal Process. Mag.25, 83 (2008)

    work page 2008

  6. [6]

    Wagadarikar, R

    A. Wagadarikar, R. John, R. Willett, and D. Brady, Appl. Opt.47, B44 (2008)

    work page 2008

  7. [7]

    O. E. Ayach, S. Rajagopal, S. Abu-Surra, Z. Pi, and R. W. Heath, IEEE Trans. Wirel. Commun.13, 1499 (2014)

    work page 2014

  8. [8]

    D. L. Donoho, IEEE Trans. Inf. Theory52, 1289 (2006)

    work page 2006

  9. [9]

    E. J. Cand` es, J. K. Romberg, and T. Tao, Commun. Pure Appl. Math.59, 1207 (2006)

    work page 2006

  10. [10]

    Krzakala, M

    F. Krzakala, M. M´ ezard, F. Sausset, Y. Sun, and L. Zdeborov´ a, J. Stat. Mech.2012, P08009 (2012)

    work page 2012

  11. [11]

    D. L. Donoho, A. Maleki, and A. Montanari, Proc. Natl. Acad. Sci. U. S. A.106, 18914 (2009)

    work page 2009

  12. [12]

    Bayati and A

    M. Bayati and A. Montanari, IEEE Trans. Inf. Theory57, 764 (2011)

    work page 2011

  13. [13]

    Kabashima, T

    Y. Kabashima, T. Wadayama, and T. Tanaka, J. Stat. Mech.2009, L09003 (2009)

    work page 2009

  14. [14]

    Ganguli and H

    S. Ganguli and H. Sompolinsky, Phys. Rev. Lett.104, 188701 (2010)

    work page 2010

  15. [15]

    Krzakala, M

    F. Krzakala, M. M´ ezard, F. Sausset, Y. F. Sun, and L. Zdeborov´ a, Phys. Rev. X.2, 021005 (2012)

    work page 2012

  16. [16]

    Wu and S

    Y. Wu and S. Verdu, IEEE Trans. Inf. Theory58, 6241 (2012)

    work page 2012

  17. [17]

    H. Zou, J. Am. Stat. Assoc.101, 1418 (2006)

    work page 2006

  18. [18]

    Fan and R

    J. Fan and R. Li, J. Am. Stat. Assoc.96, 1348 (2001)

    work page 2001

  19. [19]

    Chartrand, IEEE Signal Processing Letters14, 707 (2007)

    R. Chartrand, IEEE Signal Processing Letters14, 707 (2007)

    work page 2007

  20. [20]

    Zhang, Ann

    C.-H. Zhang, Ann. Stat.38, 894 (2010)

    work page 2010

  21. [21]

    R. R. Coifman and M. V. Wickerhauser, IEEE Trans. Inf. Theory38, 713 (1992). 33

    work page 1992

  22. [22]

    E. J. Cand` es, M. B. Wakin, and S. P. Boyd, J Fourier Anal Appl Springer Texts in Statistics, 14, 877 (2008)

    work page 2008

  23. [23]

    Daubechies, R

    I. Daubechies, R. DeVore, M. Fornasier, and C. S. G¨ unt¨ urk, Commun. Pure Appl. Math.63, 1 (2010)

    work page 2010

  24. [24]

    Chartrand and W

    R. Chartrand and W. Yin, in2008 IEEE International Conference on Acoustics, Speech and Signal Processing(IEEE, 2008) pp. 3869–3872

    work page 2008

  25. [25]

    Sakata and Y

    A. Sakata and Y. Xu, J. Stat. Mech.2018, 033404 (2018)

    work page 2018

  26. [26]

    X. Gu, A. Sakata, and T. Obuchi, arXiv [stat.ML] (2025)

    work page 2025

  27. [27]

    Sakata and T

    A. Sakata and T. Obuchi, J. Stat. Mech.2021, 093401 (2021)

    work page 2021

  28. [28]

    Prater-Bennette, L

    A. Prater-Bennette, L. Shen, and E. E. Tripp, J. Sci. Comput.93, 67 (2022)

    work page 2022

  29. [29]

    Daubechies, M

    I. Daubechies, M. Defrise, and C. De Mol, Commun. Pure Appl. Math.57, 1413 (2004)

    work page 2004

  30. [30]

    Beck and M

    A. Beck and M. Teboulle, SIAM J. Imaging Sci.2, 183 (2009)

    work page 2009

  31. [31]

    Boyd, Found

    S. Boyd, Found. Trends®Mach. Learn.3, 1 (2010)

    work page 2010

  32. [32]

    Y. Shen, J. Fang, and H. Li, IEEE Signal Process. Lett.20, 1223 (2013)

    work page 2013

  33. [33]

    Nagano and K

    Y. Nagano and K. Hukushima, Phys. Rev. E.107, 034126 (2023)

    work page 2023

  34. [34]

    Nagano and K

    Y. Nagano and K. Hukushima, J. Stat. Mech. (2024)

    work page 2024

  35. [35]

    C. M. Carvalho, N. G. Polson, and J. G. Scott, Biometrika97, 465 (2010)

    work page 2010

  36. [36]

    Armagan, D

    A. Armagan, D. B. Dunson, and J. Lee, Stat. Sin.23, 119 (2013)

    work page 2013

  37. [37]

    Ma and L

    J. Ma and L. Ping, IEEE Access5, 2020 (2017)

    work page 2020

  38. [38]

    Rangan, P

    S. Rangan, P. Schniter, and A. K. Fletcher, in2017 IEEE International Symposium on Infor- mation Theory (ISIT)(IEEE, 2017) pp. 1588–1592

    work page 2017

  39. [39]

    Furuhashi, H

    T. Furuhashi, H. Hontani, Q. Zhao, and T. Yokota, arXiv [cs.LG] (2026). 34

    work page 2026