Pith. sign in

REVIEW 3 major objections 4 minor 47 references

Phase Transitions in Phase-Only Compressed Sensing

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Phase-only compressed sensing's phase transition sits at the statistical dimension of a signal-dependent descent cone, and it needs strictly fewer measurements than linear compressed sensing — about 68% as many for a 1-sparse…

desk verdict Solid phase-transition theory, but the 68% headline is a finite-n artifact; the true limit from the paper's own formulas is 2/pi. read the letter →

arxiv 2501.11905 v1 pith:GSOLK3H2 submitted 2025-01-21 cs.IT eess.SPmath.IT

Junren Chen , Lexiao Lai , Arian Maleki This is my paper · ORCID
classification cs.ITeess.SPmath.IT MSC 94A1290C2560D05
keywords phase-onlycompressedsensingphasetransitionbasispursuitstatisticaldimensiondescentconeGaussianmin-maxtheoremsparserecoverylow-rankmatrix
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

Phase-only compressed sensing asks how many complex measurements of the form $z = \mathrm{sign}(\Phi x)$ are enough to exactly recover a structured vector $x$. This paper proves that for a fixed signal and an i.i.d. complex Gaussian sensing matrix, the phase transition of the standard linearized basis pursuit procedure is located at an explicit quantity $\zeta_{PO}(x;f)$, and that this quantity is well approximated by the statistical dimension of the descent cone of a norm $f_x$ that depends on the signal. Using that approximation, the paper derives asymptotically exact formulas for sparse vectors and low-rank matrices, and shows that phase-only sensing needs fewer measurements than ordinary linear compressed sensing. In the canonical example of a 1-sparse equal-amplitude signal in high dimension, the ratio is about 0.678, contradicting an earlier suggestion that the two thresholds coincide.

What carries the argument

The load-bearing quantity is $\zeta_{PO}(x;f) = \left(\mathbb{E} \sup_{u \in T_f(x), \|Q_x u\|_2=1} \langle (I_n - xx^\top)g, u\rangle\right)^2$, with $Q_x = I_n + (\sqrt{\pi/2}-1)xx^\top$ and $g \sim N(0,I_n)$. The proof that this is the threshold uses the convex Gaussian min-max theorem after Lemma 3 shows that $A_z P_x^\top$ is distributionally close to a Gaussian matrix: up to a signal-dependent orthogonal transform, the sensing matrix has i.i.d. Gaussian entries except for its first column, which is governed by the mean modulus of a complex Gaussian. Proposition 1 is the second mechanism: it identifies $\zeta_{PO}$ with the statistical dimension $\delta(T_{f_x}(x))$ of the descent cone of the signal-dependent norm $f_x(u)=f(u-(1-\sqrt{2/\pi})\langle x,u\rangle x)$, which then admits explicit computation through the standard squared-distance-to-subdifferential formula.

What would settle it

Compute the exact threshold $\zeta_{PO}(x;\ell_1)$ from (6) for a fixed 1-sparse equal-amplitude vector $x$ in $\mathbb{R}^n$ using Monte Carlo evaluation of the Gaussian supremum, and compare it with $n\psi(1/n,1)$; if the ratio to $\zeta_{LN}(x;\ell_1)$ does not approach about 0.678 as $n$ grows, or if empirical success probabilities near that measurement count are not centered at 50%, the surrogate-based 68% claim fails.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: after reformulating phase-only compressed sensing as a linear problem with sensing matrix $A_z$ and applying basis pursuit, recovery of a fixed $x$ succeeds with high probability when $m \geq (1+t)\zeta_{PO}(x;f)$ and fails with high probability when $m \leq (1-t)\zeta_{PO}(x;f)$, where $\zeta_{PO}(x;f)$ is the squared expectation in (6). Proposition 1 then approximates $\zeta_{PO}$ by $\delta(T_{f_x}(x))$, the statistical dimension of the descent cone of the signal-dependent norm $f_x(u)=f(u-(1-\sqrt{2/\pi})\langle x,u\rangle x)$, up to an error of order $\sqrt{\delta}$. For $\ell_1$ recovery of $s$-sparse vectors this gives the asymptotic threshold $n\psi(s/n, \|x\|_1^2/s)$, and for nuclear-norm recovery of rank-$r$ matrices it gives $pq\Psi(r/p, p/q, \|X\|_{\mathrm{nu}}^2/r)$. Since these surrogates are smaller than the corresponding linear compressed sensing thresholds and the ratio is bounded away from 1 for nontrivial structure, the paper concludes that phase-only measurements are fundamentally more efficient.

Load-bearing premise

The paper proves the phase-transition formula for a surrogate quantity that lies within an error of order the square root of the true threshold, but the constant in that error is not rigorously bounded and the 0.678 limit is not proven for the exact threshold, so the headline saving rests on the surrogate being accurate at the level of the ratio.

Editorial extensions

If this is right

  • For sparse signals, the phase transition depends on $\|x\|_1$ as well as on $n$ and $s$; equal-amplitude sparse signals are the most favorable, with the earliest transition.
  • For low-rank matrices, the threshold depends on the nuclear norm; matrices with equal singular values require the fewest phase-only measurements.
  • Phase-only compressed sensing requires strictly fewer measurements than linear compressed sensing for nontrivial sparsity or rank; 1-sparse equal-amplitude signals need about 68% of the linear-CS measurements.
  • The result disproves the earlier conjecture or empirical observation that $\zeta_{PO} \approx \zeta_{LN}$ for structured signals; the ratio is bounded away from 1 whenever sparsity or rank is bounded away from the ambient dimension.

Reading between the lines

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

  • If the $O(\sqrt{\delta})$ gap in Proposition 1 can be sharpened to a uniform constant, the ratio formulas for $\zeta_{PO}/\zeta_{LN}$ would become rigorous for fixed sparsity or rank rather than asymptotic surrogates.
  • The signal-dependence of the threshold suggests an adaptive strategy: with side information about $\|x\|_1$ or the nuclear norm, one could choose sensing designs or regularizers tuned to the signal class to lower measurement counts further.
  • The same near-Gaussianity argument may apply to other nonlinear observations that linearize into a phase-dependent matrix, potentially giving sharp thresholds for quantized or phase-retrieval variants of compressed sensing.
  • A testable extension is to measure the predicted monotone dependence on $\|x\|_1$ across a grid of signal amplitudes; the formulas imply a continuum of transition curves, not a single curve per sparsity or rank.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. This paper analyzes phase-only compressed sensing (PO-CS): recovering a structured signal x ∈ S^{n−1} from the phases z = sign(Φx) of complex Gaussian measurements, using the linearized reformulation (3)–(4) followed by basis pursuit. The central claim is Theorem 1: for a fixed signal x, the success/failure boundary of this procedure is sharply located at ζ_PO(x;f), the squared expectation of a Gaussian supremum over the descent cone T_f(x) under the norm Q_x, with explicit exponential probability bounds on both sides. Proposition 1 approximates ζ_PO(x;f) by the statistical dimension of the descent cone of the signal-dependent norm f_x(w) = f(Q_x^{−1}w), and Theorems 3–4 convert this into explicit formulas n·ψ(s/n, ‖x‖₁²/s) for s-sparse vectors and pq·Ψ(r/p, p/q, ‖X‖_nu²/r) for low-rank matrices, each depending on the signal's ℓ₁ or nuclear norm in addition to sparsity or rank. The paper concludes that PO-CS requires strictly fewer measurements than linear compressed sensing for structured signals, with a headline example claiming that 1-sparse signals need about 68% of the linear-CS measurement count. The main technical machinery (the distributional identity in Lemma 3 and the Gaussian min-max comparison) is coherent, but the headline quantitative claim is not correct as an asymptotic statement.

Significance. If it survives revision, the paper makes a substantive contribution: Theorem 1 is a sharp, algorithm-specific phase transition for PO-CS with explicit rates; Lemma 3 is an elegant exact distributional identity that makes the Gaussian comparison framework applicable; and the explicit formulas (15)–(16) and (21)–(22) are evaluable, falsifiable predictions, which the numerical experiments in Figures 3–4 support. The structural conclusion that ζ_PO/ζ_LN is bounded away from 1 for structured signals contradicts the empirical observation of Jacques and Feuillen [25] and is the paper's most important message; it survives the issue identified below, since the correct asymptotic ratio (2/π ≈ 0.6366 for equal-amplitude 1-sparse signals) is even smaller than the claimed 0.678. The defect is concentrated in the interpretation of the numerical limits in Section 3.3, Figure 2, and the abstract: those quantitative claims are wrong as stated, but the main theorems and the comparative conclusion are defensible.

major comments (3)
  1. [Section 3.3 / Figure 2 / Abstract] The claimed limit is incorrect. For v = 1, equations (14) and (16) reduce to ψ(u,1) = inf_τ {u(1 + 2τ²/π) + (1−u)I(τ)} and ψ₁(u) = inf_τ {u(1 + τ²) + (1−u)I(τ)} with I(τ) = √(2/π)∫_τ^∞ (w−τ)² e^{−w²/2} dw. As u → 0+, both optimizers are large with τ*² = 2 log(1/u) + O(log log(1/u)), and the first-order condition with I′(τ) ≈ −τI(τ) gives (1−u)I(τ*) ≈ 2u for ψ₁ and (1−u)I(τ*) ≈ 4u/π for ψ. Each minimum is therefore a·u·τ*² + O(u) with a = 1 and a = 2/π respectively, so lim_{u→0+} Rsp(u,1) = 2/π ≈ 0.6366, not 0.678. The value 0.678 is the ratio at u ≈ 10⁻³ (n ≈ 1000 for a 1-sparse signal), where the O(log log(1/u)/log(1/u)) corrections are still substantial; it is not the n → ∞ limit. The abstract's statement that a 1-sparse signal 'with sufficiently large dimension' requires approximately 68% of the linear-CS measurements, and the caption's 'lim_{u→0+} Rsp(u,1) ≈ 0.678', are therefore wrong as asymptotic statements. The bounded-away-from-1 conclusion survives (the asymptotic ratio is 2/π, which is even smaller), and the authors should either prove and state the correct limit, which follows from a short two-scale analysis, or explicitly report 0.678 as a finite-n value. The same caution applies to the claimed limits Rlr(u,1,1) → 0.758 and Rlr(u,1,0.6) → 0.856 in the right panel of Figure 2, which are reported without proof.
  2. [Equations (15)–(17) / Section 3.3] In the fixed-sparsity regime (s fixed, u = s/n → 0), which is precisely the regime of the headline 1-sparse claim, the lower bound in (17) is vacuous. The error term √(2πn)/‖x‖₁ is Θ(√n) because rad(Q_x^{−1}∂f(x)) ≥ √(n−s) (the subgradient components on the zero coordinates are unchanged by Q_x^{−1}), while nψ(s/n, ‖x‖₁²/s) = Θ(log n). Consequently the paper's rigorous bounds give only the one-sided statement ζ_PO ≤ nψ(s/n, ·); together with the standard lower bound ζ_LN ≥ nψ₁(s/n) − O(1) (e.g., [1, Thm. 4.3]) this yields limsup ζ_PO/ζ_LN ≤ 2/π but does not pin down the exact ratio. The values plotted in Figure 2 and cited in Section 1.2 are surrogate ratios, not consequences of (17), and Section 3.3 explicitly disclaims an analytical analysis of Rsp and Rlr. The abstract and Section 1.2 should therefore distinguish the rigorous upper bound from the numerical equality claim, or the authors should supply a matching lower bound for ζ_PO in the fixed-s regime (for instance, by direct asymptotic analysis of the expected supremum in (6)).
  3. [Section 3.3 vs. Figure 2 caption] There is an internal inconsistency between the text and the caption: Section 3.3 states that 'an analytical analysis of Rsp and Rlr is not pursued in the present paper,' yet the Figure 2 caption announces limits of Rsp and Rlr as u → 0+. Since the sparse-case limit is not 0.678, the caption's limit notation is misleading for both panels; the authors should either provide the asymptotic analysis or replace the limit claims by values at a specified finite u.
minor comments (4)
  1. [Section 1.1] The phrase 'if m /greaterorsimilar s log(n)' contains an unrendered LaTeX operator, and 'm ≥C1s log( en s )' is missing a space before the constant C1; both should be corrected.
  2. [Appendix A.3, Eq. (42)] For the stated threshold |g₁| ≥ (3/4)√(m)t, the standard Gaussian tail gives P ≤ 2exp(−(9/32)mt²), which is weaker than the displayed exp(−mt²); the constants (for example, the factor 14 in Theorem 1) should be re-derived, although the structure of the argument is unaffected.
  3. [Appendix A.3] In the inequality following (42), '‖ũ‖₁' should read '‖ũ‖₂'; with the ℓ₁ norm the subsequent bound |2u₁‖ũ‖₂| ≤ u₁² + ‖ũ‖₂² would not be available.
  4. [Abstract] 'Disproves earlier conjecture' overstates the status of the claim in [25], which is reported there as an empirical observation; 'contradicts the empirical claim reported in [25]' would be more precise.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the phase-transition formulas are derived from proved concentration/min-max arguments and evaluated from definitions; no fitted parameter or self-citation is load-bearing.

full rationale

The derivation chain is self-contained. zeta_PO(x;f) in (6) is an explicit Gaussian-supremum expectation, and Theorem 1 proves (rather than assumes) that recovery succeeds and fails around this value using Lemma 2 (Gaussian min-max theorem) and Lemma 3 (near-Gaussianity of A_z), both proved in the appendix with only external results (Gordon's comparison inequality via [40,41] and the statistical-dimension framework of [1]) that do not presuppose the target result. Proposition 1 then approximates zeta_PO by delta(T_fx(x)) through proved inequalities, and Theorems 3 and 4 evaluate the surrogate inf_tau E dist^2(g, tau Q_x^{-1} partial f(x)) by direct calculus and Marchenko-Pastur asymptotics, with no parameter fitted to the simulations. The empirical phase transitions in Section 4 are independent corroboration rather than inputs. The only flagged limitation, in Section 3.3, states that 'an analytical analysis of Rsp and Rlr is not pursued in the present paper'; this is a completeness/correctness caveat about the numerically displayed limit 0.678, not a circular step, because the ratio is computed from the derived formulas and is an output, not an input. Author self-citations ([8]-[10]) are background and motivation only and are not load-bearing. Overall, no reduction to inputs by construction or by self-citation occurs.

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

The derivation introduces no fitted free parameters and no new physical entities. All constants, including sqrt(pi/2) and 2/pi, arise from Gaussian and Rayleigh expectations or from the definition of the statistical dimension. The signal-dependent norm f_x is a mathematical construction defined in the proof, not an entity requiring independent evidence.

assumptions (7)
  • standard math Convex Gaussian min-max theorem (Lemma 2, from Chandrasekher et al.) correctly characterizes the minimax of Gaussian matrices.
    Used throughout the proof of Theorem 1; cited as Lemma 2 with references [7, 40, 41].
  • standard math The near-Gaussian representation A_z P_x^T has the distribution [L e1, G/sqrt(m)] with L and G independent (Lemma 3).
    This exact distributional identity is the bridge that lets the Gaussian min-max theorem apply to the non-Gaussian A_z.
  • standard math The Amelunxen-Tropp statistical dimension recipe, including inf E[dist^2(g, tau * subdifferential)] with radius error terms.
    Used in Theorems 2-4 to convert delta(T_fx(x)) into explicit formulas; cited as [1, Thm 4.3].
  • standard math Subdifferential formulas for the ell-1 norm and the nuclear norm, and the shrinkage expectation identity for Gaussian random variables.
    Used in the exact computations for sparse and low-rank recovery in Theorems 3 and 4.
  • standard math Marchenko-Pastur limit for the low-rank Wishart-type expectation in Theorem 4.
    Borrowed from Amelunxen et al., Appendix D.3, to obtain the integral expression for Psi.
  • domain assumption The descent cone T_f(x) is closed and not a subspace, and f is a norm.
    Lemma 1 requires this to prove the success and failure conditions; stated explicitly in Lemma 1.
  • domain assumption The sensing matrix has i.i.d. complex Gaussian entries.
    Lemma 3 and all theorems depend on this distributional assumption; the paper does not extend to other sensing ensembles.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Phase Transitions in Phase-Only Compressed Sensing." pith.science (2026). https://pith.science/paper/GSOLK3H2

@misc{pith2026250111905,
  author       = {Pith},
  title        = {Pith review of: Phase Transitions in Phase-Only Compressed Sensing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GSOLK3H2}},
  note         = {Machine review of arXiv:2501.11905}
}
abstract

The goal of phase-only compressed sensing is to recover a structured signal $\mathbf{x}$ from the phases $\mathbf{z} = {\rm sign}(\mathbf{\Phi}\mathbf{x})$ under some complex-valued sensing matrix $\mathbf{\Phi}$. Exact reconstruction of the signal's direction is possible: we can reformulate it as a linear compressed sensing problem and use basis pursuit (i.e., constrained norm minimization). For $\mathbf{\Phi}$ with i.i.d. complex-valued Gaussian entries, this paper shows that the phase transition is approximately located at the statistical dimension of the descent cone of a signal-dependent norm. Leveraging this insight, we derive asymptotically precise formulas for the phase transition locations in phase-only sensing of both sparse signals and low-rank matrices. Our results prove that the minimum number of measurements required for exact recovery is smaller for phase-only measurements than for traditional linear compressed sensing. For instance, in recovering a 1-sparse signal with sufficiently large dimension, phase-only compressed sensing requires approximately 68% of the measurements needed for linear compressed sensing. This result disproves earlier conjecture suggesting that the two phase transitions coincide. Our proof hinges on the Gaussian min-max theorem and the key observation that, up to a signal-dependent orthogonal transformation, the sensing matrix in the reformulated problem behaves as a nearly Gaussian matrix.

Figures

Figures reproduced from arXiv: 2501.11905 by the authors.

Figure 1
Figure 1. We fix n = 1000 and plot the (approximate) curves of ζPO/ζLN v.s. s = 1 : 1000 under kxk1 = √ s, 0.7 √ s + 0.3, 0.3 √ s + 0.7. These curves are monotonically increasing. As we will clarify later, there is another interesting and important difference between ζPO and ζLN in terms of the dependence on the signal. For example, while ζLN(x; ℓ1) only depends on x through the dimension n and the sparsity s, ζPO(x; ℓ1) also… view at source ↗
Figure 2
Figure 2. The left figure plots Rsp(u, 1) and Rsp(u, 0.6), showing limu→0+ Rsp(u, 1) ≈ 0.678 and limu→0+ Rsp(u, 0.6) ≈ 0.808; the former indicates that for recovering s-sparse x ∈ S n−1 with nonzero entries being ±1/ √ s, if s is fixed and n → ∞, then PO-CS requires no more than 0.68ζLN(x; k · k1) phases to succeed, as we highlighted in the abstract. Similarly, the right figure plots Rlr(u, 1, 1) and Rlr(u, 1, 0.6), and we fu… view at source ↗
Figure 3
Figure 3. The left figure shows that the empirical phase trans [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The left figure shows that the empirical phase trans [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

47 extracted references · 44 canonical work pages

  1. [25]

    The importance of phase in complex compressive sensing

    Laurent Jacques and Thomas Feuillen. The importance of phase in complex compressive sensing. IEEE Transactions on Information Theory , 67(6):4150–4161, 2021

    work page 2021

  2. [1]

    Living on the edge: Phase transitions in convex programs with random data

    Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel A Tropp. Living on the edge: Phase transitions in convex programs with random data. Information and Inference: A Journal of the IMA , 3(3):224–294, 2014

    work page 2014

  3. [2]

    Angle-preserving quantized phase e mbeddings

    Petros T Boufounos. Angle-preserving quantized phase e mbeddings. In Wavelets and Sparsity XV , volume 8858, pages 375–383. SPIE, 2013

    work page 2013

  4. [3]

    Sparse signal reconstruction from p hase-only measurements

    Petros T Boufounos. Sparse signal reconstruction from p hase-only measurements. In Proc. Int. Conf. Sampling Theory and Applications (SampTA) , volume 4. Citeseer, 2013

    work page 2013

  5. [4]

    Optimal rates of convergence for noisy sparse phase retrieval via thresholded wirtinger flow

    T Tony Cai, Xiaodong Li, and Zongming Ma. Optimal rates of convergence for noisy sparse phase retrieval via thresholded wirtinger flow. The Annals of Statistics , 44(5):2221–2251, 2016

    work page 2016

  6. [5]

    Phase retrieval via wirtinger flow: Theory and algorithms

    Emmanuel J Candes, Xiaodong Li, and Mahdi Soltanolkotab i. Phase retrieval via wirtinger flow: Theory and algorithms. IEEE Transactions on Information Theory , 61(4):1985–2007, 2015. 11

    work page 1985

  7. [6]

    The convex geometry of linear inverse problems

    Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo , and Alan S Willsky. The convex geometry of linear inverse problems. Foundations of Computational Mathematics , 12(6):805–849, 2012

    work page 2012

  8. [7]

    Sharp global conver- gence guarantees for iterative nonconvex optimization wit h random data

    Kabir Aladin Chandrasekher, Ashwin Pananjady, and Chri stos Thrampoulidis. Sharp global conver- gence guarantees for iterative nonconvex optimization wit h random data. The Annals of Statistics , 51(1):179–210, 2023

    work page 2023

Show all 47 references
  1. [8]

    Robust instance optimal phase- only compressed sensing

    Junren Chen, Zhaoqiang Liu, Michael K Ng, and Jonathan Sc arlett. Robust instance optimal phase- only compressed sensing. arXiv preprint arXiv:2408.06275 , 2024

    2024 arXiv

  2. [9]

    Signal reconstruction from phase-only measurements: Unique- ness condition, minimal measurement number and beyond

    Junren Chen and Michael K Ng. Signal reconstruction from phase-only measurements: Unique- ness condition, minimal measurement number and beyond. SIAM Journal on Applied Mathematics , 83(4):1341–1365, 2023

    2023

  3. [10]

    Junren Chen and Michael K. Ng. Uniform exact reconstruc tion of sparse signals and low-rank matrices from phase-only measurements. IEEE Transactions on Information Theory , 69(10):6739–6764, 2023

    2023

  4. [11]

    Ng, and Di Wang

    Junren Chen, Michael K. Ng, and Di Wang. Quantizing heav y-tailed data in statistical estimation: (near) minimax rates, covariate quantization, and uniform recovery. IEEE Transactions on Informa- tion Theory, 70(3):2003–2038, 2024

    2003

  5. [12]

    A unified framework for uniform signal recovery in nonlinear generative compressed sensin g

    Junren Chen, Jonathan Scarlett, Michael Ng, and Zhaoqi ang Liu. A unified framework for uniform signal recovery in nonlinear generative compressed sensin g. Advances in Neural Information Processing Systems, 36, 2024

    2024

  6. [13]

    Optimal quantized compresse d sensing via projected gradient descent

    Junren Chen and Ming Yuan. Optimal quantized compresse d sensing via projected gradient descent. arXiv preprint arXiv:2407.04951 , 2024

    2024 arXiv

  7. [14]

    Quantized compressed sensing: a surve y

    Sjoerd Dirksen. Quantized compressed sensing: a surve y. In Compressed Sensing and Its Applications: Third International MATHEON Conference 2017 , pages 67–95. Springer, 2019

    2017

  8. [15]

    Non-gaussian hyp erplane tessellations and robust one-bit compressed sensing

    Sjoerd Dirksen and Shahar Mendelson. Non-gaussian hyp erplane tessellations and robust one-bit compressed sensing. Journal of the European Mathematical Society , 23(9):2913–2947, 2021

    2021

  9. [16]

    Counting faces of random ly projected polytopes when the projection radically lowers dimension

    David Donoho and Jared Tanner. Counting faces of random ly projected polytopes when the projection radically lowers dimension. Journal of the American Mathematical Society , 22(1):1–53, 2009

    2009

  10. [17]

    High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension

    David L Donoho. High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension. Discrete & Computational Geometry , 35:617–652, 2006

    2006

  11. [18]

    Mes sage-passing algorithms for compressed sensing

    David L Donoho, Arian Maleki, and Andrea Montanari. Mes sage-passing algorithms for compressed sensing. Proceedings of the National Academy of Sciences , 106(45):18914–18919, 2009

    2009

  12. [19]

    The noise-sensitivity phase transition in compressed sensing

    David L Donoho, Arian Maleki, and Andrea Montanari. The noise-sensitivity phase transition in compressed sensing. IEEE Transactions on Information Theory , 57(10):6920–6941, 2011

    2011

  13. [20]

    ( ℓ1,ℓ 2)-rip and projected back-projection reconstruction for phase-only measureme nts

    Thomas Feuillen, Mike E Davies, Luc Vandendorpe, and La urent Jacques. ( ℓ1,ℓ 2)-rip and projected back-projection reconstruction for phase-only measureme nts. IEEE Signal Processing Letters, 27:396– 400, 2020

    2020

  14. [21]

    A unified appr oach to uniform signal recovery from non- linear observations

    Martin Genzel and Alexander Stollenwerk. A unified appr oach to uniform signal recovery from non- linear observations. Foundations of Computational Mathematics , 23(3):899–972, 2023

    2023

  15. [22]

    Some inequalities for gaussian proces ses and applications

    Yehoram Gordon. Some inequalities for gaussian proces ses and applications. Israel Journal of Math- ematics, 50:265–289, 1985. 12

    1985

  16. [23]

    On milman’s inequality and random subs paces which escape through a mesh in Rn

    Yehoram Gordon. On milman’s inequality and random subs paces which escape through a mesh in Rn. In Geometric Aspects of Functional Analysis: Israel Seminar (G AF A) 1986–87, pages 84–106. Springer, 1988

    1986

  17. [24]

    Cvx: Matlab software fo r disciplined convex programming, version 2.1, 2014

    Michael Grant and Stephen Boyd. Cvx: Matlab software fo r disciplined convex programming, version 2.1, 2014

    2014

  18. [26]

    Robust 1-bit com- pressive sensing via binary stable embeddings of sparse vec tors

    Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1-bit com- pressive sensing via binary stable embeddings of sparse vec tors. IEEE Transactions on Information Theory, 59(4):2082–2102, 2013

    2013

  19. [27]

    Adaptive estimat ion of a quadratic functional by model selec- tion

    Beatrice Laurent and Pascal Massart. Adaptive estimat ion of a quadratic functional by model selec- tion. Annals of Statistics , pages 1302–1338, 2000

    2000

  20. [28]

    Probability in Banach Spaces: isoperimetry and processes

    Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes . Springer Science & Business Media, 2013

    2013

  21. [29]

    Asymptotic analysis of complex lasso via complex approximate message passing (camp)

    Arian Maleki, Laura Anitori, Zai Yang, and Richard G Bar aniuk. Asymptotic analysis of complex lasso via complex approximate message passing (camp). IEEE Transactions on Information Theory , 59(7):4290–4308, 2013

    2013

  22. [30]

    Binary iterative h ard thresholding converges with optimal number of measurements for 1-bit compressed sensing

    Namiko Matsumoto and Arya Mazumdar. Binary iterative h ard thresholding converges with optimal number of measurements for 1-bit compressed sensing. Journal of the ACM , 71(5):1–64, 2024

    2024

  23. [31]

    The importance of phase in signals

    Alan V Oppenheim and Jae S Lim. The importance of phase in signals. Proceedings of the IEEE , 69(5):529–541, 1981

    1981

  24. [32]

    Universality laws for rand omized dimension reduction, with appli- cations

    Samet Oymak and Joel A Tropp. Universality laws for rand omized dimension reduction, with appli- cations. Information and Inference: A Journal of the IMA , 7(3):337–446, 2018

    2018

  25. [33]

    Robust 1-bit compresse d sensing and sparse logistic regression: A convex programming approach

    Yaniv Plan and Roman Vershynin. Robust 1-bit compresse d sensing and sparse logistic regression: A convex programming approach. IEEE Transactions on Information Theory , 59(1):482–494, 2012

    2012

  26. [34]

    One-bit compressed sen sing by linear programming

    Yaniv Plan and Roman Vershynin. One-bit compressed sen sing by linear programming. Communi- cations on pure and Applied Mathematics , 66(8):1275–1297, 2013

    2013

  27. [35]

    The generalized lasso w ith non-linear observations

    Yaniv Plan and Roman Vershynin. The generalized lasso w ith non-linear observations. IEEE Trans- actions on Information Theory , 62(3):1528–1537, 2016

    2016

  28. [36]

    High- dimensional estimation with geometric constraints

    Yaniv Plan, Roman Vershynin, and Elena Yudovina. High- dimensional estimation with geometric constraints. Information and Inference: A Journal of the IMA , 6(1):1–40, 2017

    2017

  29. [37]

    ℓ1 optimization and its various thresholds in compressed sens ing

    Mihailo Stojnic. ℓ1 optimization and its various thresholds in compressed sens ing. In 2010 IEEE International Conference on Acoustics, Speech and Signal Pro cessing, pages 3910–3913. IEEE, 2010

    2010

  30. [38]

    A framework to characterize performa nce of lasso algorithms

    Mihailo Stojnic. A framework to characterize performa nce of lasso algorithms. arXiv preprint arXiv:1303.7291, 2013

    2013 arXiv

  31. [39]

    Phase transitio ns in recovery of structured signals from corrupted measurements

    Zhongxing Sun, Wei Cui, and Yulong Liu. Phase transitio ns in recovery of structured signals from corrupted measurements. IEEE Transactions on Information Theory , 68(7):4837–4863, 2022

    2022

  32. [40]

    Precise error analysis of regularized m-estimators in high dimensions

    Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassi bi. Precise error analysis of regularized m-estimators in high dimensions. IEEE Transactions on Information Theory , 64(8):5592–5628, 2018. 13

    2018

  33. [41]

    Regularized linear regression: A precise analysis of the estimation error

    Christos Thrampoulidis, Samet Oymak, and Babak Hassib i. Regularized linear regression: A precise analysis of the estimation error. In Conference on Learning Theory , pages 1683–1709. PMLR, 2015

    2015

  34. [42]

    The gene ralized lasso for sub-gaussian measurements with dithered quantization

    Christos Thrampoulidis and Ankit Singh Rawat. The gene ralized lasso for sub-gaussian measurements with dithered quantization. IEEE Transactions on Information Theory , 66(4):2487–2500, 2020

    2020

  35. [43]

    Quantized compressive sensing with rip matrices: The benefit of dithering

    Chunlei Xu and Laurent Jacques. Quantized compressive sensing with rip matrices: The benefit of dithering. Information and Inference: A Journal of the IMA , 9(3):543–586, 2020. Appendix A Deferred Proofs A.1 Proof of Lemma 1 We should first emphasize that if ( 3) is successful, ...

    2020

  36. [44]

    The only remaining part is to show that A′ d= G√m . Since diag(sign( φ ∗ 1)) is a unitary matrix, we have diag(sign(φ ∗ 1))[φ 2, · · ·, φ n] ∼ N m×(n−1)(0, 1) + N m×(n−1)(0, 1)i, which then implies that ℜ ( diag(sign(φ ∗ 1))[φ 2, · · ·, φ n] ) ∼ N m×(n−1)(0, 1) and ℑ ( diag(si...

  37. [45]

    Furthermore, ( 36) holds because changing min v maxu to maxu minv cannot increase the final value, and in ( 37) we optimize over v ∈ Sm as in ( 30)–(31)

    corresponds to ( 25), (34) corresponds to ( 26)–(28), and ( 35) corresponds to (29). Furthermore, ( 36) holds because changing min v maxu to maxu minv cannot increase the final value, and in ( 37) we optimize over v ∈ Sm as in ( 30)–(31). Concentration of ‖ ‖‖˜u‖2g + √ mLu1e1 ‖...

  38. [46]

    we have Ps ≥ 2/C8 (Es) − 1. This implies that Ps ≥ 2/C8 (Es and E ) − 1 ≥ 2/C8 ({ ∀u ∈ PxT ∗ f (x), h⊤ ˜u ≤ √m [ ‖˜u‖2 2 + πu2 1 2 ] 1/2 − 5√mt } and E ) − 1 (43) ≥ 2/C8 ( ∀u ∈ PxT ∗ f (x), h⊤ ˜u (‖˜u‖2 2 + πu2 1 2 )1/2 ≤ √m(1 − 5t) ) − 2/C8 (E c) − 1 (44) ≥ 2/C8 ( sup u∈PxT ∗...

  39. [49]

    This completes the proof

    because ⟨(In−xx⊤)g,u⟩ ‖Qxu‖2 is homogeneous in u, and the final equality holds similarly due to the homogeneity. This completes the proof. 18 A.4 Proof of Proposition 1 Recall that Qx = In + (√ π 2 − 1)xx⊤ and Q−1 x = In − (1 − √ 2 π )xx⊤. If we define w = Qxu, then we have /BX ...

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.