Pith. sign in

REVIEW 19 cited by

Various thresholds for $\ell_1$-optimization in compressed sensing

Not yet reviewed by Pith; the record is open.

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

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 0907.3666 v1 pith:2MS25EIW submitted 2009-07-21 cs.IT math.IT

Mihailo Stojnic This is my paper · ORCID
classification cs.ITmath.IT
keywords optimizationcitedonohopolsystemunknownvectorcompressedequations
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
abstract

Recently, \cite{CRT,DonohoPol} theoretically analyzed the success of a polynomial $\ell_1$-optimization algorithm in solving an under-determined system of linear equations. In a large dimensional and statistical context \cite{CRT,DonohoPol} proved that if the number of equations (measurements in the compressed sensing terminology) in the system is proportional to the length of the unknown vector then there is a sparsity (number of non-zero elements of the unknown vector) also proportional to the length of the unknown vector such that $\ell_1$-optimization succeeds in solving the system. In this paper, we provide an alternative performance analysis of $\ell_1$-optimization and obtain the proportionality constants that in certain cases match or improve on the best currently known ones from \cite{DonohoPol,DT}.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 19 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Testing Unate Distributions

    cs.DS 2026-07 unverdicted novelty 8.0 of 10

    Unate distributions require θ̃(n^{3/2}) samples for uniformity testing and allow Õ(n^{3/2}) conditional samples for unateness testing in the subcube model.

  2. Sharp Guarantees for Solving Random Equations with One-Bit Information

    math.ST 2019-08 conditional novelty 7.0 of 10

    For Gaussian one-bit measurements, the correlation of any convex-loss estimator is sharply predicted by a system of three equations, yielding new per-estimator comparisons and an optimality bound.

  3. Learning switched non-linear dynamical systems from a single trajectory

    stat.ML 2026-07 conditional novelty 6.0 of 10

    ERM learns switched nonlinear dynamics from one trajectory at rates governed by metric entropy and effective sample size T p_i under stability and i.i.d. mode switching.

  4. Precise sample covariance spectral norm error -- an RDT view

    math.ST 2026-07 conditional novelty 6.0 of 10

    For Gaussian data in the proportional limit, the spectral-norm error of the sample covariance converges to γ̂√φ1/(√φ1−√α), with γ̂ solving an equation in the covariance spectrum.

  5. Single-Head Attention in High Dimensions: A Theory of Generalization, Weights Spectra, and Scaling Laws

    stat.ML 2025-09 conditional novelty 6.0 of 10

    For a high-dimensional Gaussian sequence model, empirical risk minimization in single-head tied attention has exactly computable test error, interpolation and recovery thresholds, and a singular-value spectrum that be...

  6. CLuP practically achieves $\sim 1.77$ positive and $\sim 0.33$ negative Hopfield model ground state free energy

    cond-mat.dis-nn 2025-07 conditional novelty 6.0 of 10

    CLuP±Hop approximates Hopfield ground state free energies to within about 0.3% using simple gradient descent, backed by the author's fully lifted random duality theory.

  7. Optimal spectral initializers impact on phase retrieval phase transitions -- an RDT view

    stat.ML 2025-06 conditional novelty 6.0 of 10

    Optimal spectral initializers at the theoretical phase retrieval threshold sit in flat landscape regions, so roughly 15% oversampling is needed for reliable descending algorithms.

  8. Phase transition of \emph{descending} phase retrieval algorithms

    stat.ML 2025-06 reject novelty 6.0 of 10

    The paper derives RDT-based lower bounds and predicts a phase transition at oversampling ratio α≈1.4 where descending phase retrieval algorithms transition from failing to succeeding, but the key isomorphism with conv...

  9. Deep ReLU networks -- injectivity capacity upper bounds

    stat.ML 2024-12 reject novelty 6.0 of 10

    For deep ReLU networks with random Gaussian weights, the paper gives upper bounds on the layer expansion needed for injectivity and finds the expansion need saturates by four layers.

  10. Controlled Loosening-up (CLuP) -- achieving exact MIMO ML in polynomial time

    cs.IT 2019-09 reject novelty 6.0 of 10

    CLuP, an iterative convex optimization algorithm, is claimed to achieve MIMO ML detection performance in polynomial time, but the claim rests on heuristic random duality arguments and an empirical iteration count.

  11. A CLuP algorithm to practically achieve $\sim 0.76$ SK--model ground state free energy

    cond-mat.dis-nn 2025-07 conditional novelty 5.0 of 10

    The authors propose a CLuP-SK barrier-descent algorithm and report it achieves approximately 0.76 of the SK ground state free energy for n around 2000 to 8000, approaching the theoretical Parisi limit of about 0.763.

  12. Rare dense solutions clusters in asymmetric binary perceptrons -- local entropy via fully lifted RDT

    stat.ML 2025-06 conditional novelty 5.0 of 10

    For the asymmetric binary perceptron, the worst-case local entropy breaks down for constraint density alpha in (0.77, 0.78), matching replica predictions and the range where fast algorithms stop working.

  13. Fully lifted \emph{blirp} interpolation -- a large deviation view

    math.PR 2025-06 conditional novelty 5.0 of 10

    A large-deviation upgrade of fully lifted blirp interpolation is derived, yielding explicit derivative identities that the author links to local entropy and computational gaps in perceptron models.

  14. Phase retrieval with rank $d$ measurements -- \emph{descending} algorithms phase transitions

    stat.ML 2025-06 conditional novelty 5.0 of 10

    For rank d phase retrieval with Gaussian measurements, descending gradient algorithms are predicted to succeed above a sample complexity ratio near 2.79 for d=2, with lifted bounds lowering this estimate and simulatio...

  15. Complexity analysis of the Controlled Loosening-up (CLuP) algorithm

    cs.IT 2019-09 conditional novelty 5.0 of 10

    Using Random Duality Theory, the paper argues that the CLuP algorithm reaches near-optimal MIMO ML detection in a small, dimension-independent number of quadratic-programming iterations.

  16. An RDT based confirmation of Lehner's formula for Kronecker-Gaussian matrices

    math.PR 2026-07 conditional novelty 4.0 of 10

    This paper uses Random Duality Theory to give an alternative proof of Lehner's deterministic spectral edge formula for Kronecker-Gaussian matrices.

  17. A large deviation view of \emph{stationarized} fully lifted blirp interpolation

    math.PR 2025-06 conditional novelty 4.0 of 10

    The paper derives new derivative identities for a stationarized fully lifted bilinearly indexed random process interpolator and states an equality between large deviation limits at the opposite ends of an interpolation path.

  18. Starting CLuP with polytope relaxation

    cs.IT 2019-09 conditional novelty 4.0 of 10

    CLuP-plt, a CLuP detector variant that starts from a box-constrained least-squares solution, reaches near-ML error rates within three to five iterations in the tested MIMO settings.

  19. High-Dimensional Statistics: Reflections on Progress and Open Problems

    math.ST 2026-05 unverdicted novelty 2.0 of 10

    This review synthesizes representative advances in high-dimensional statistics, highlights common themes and open problems, and points to key entry works.

Pith tools