Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models

Jonathan Scarlett; Zhaoqiang Liu

REVIEW 1 major objections 4 minor 1 cited by

Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models

T0 review · 1 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read For compressive sensing with Lipschitz generative models, $m = \Omega(k \log L)$ measurements are information-theoretically unavoidable.

desk verdict Solid first lower bounds for generative-model CS, but Theorem 7's proof has a real amplitude error that needs fixing. read the letter →

arxiv 1908.10744 v2 pith:BRSCL7IL submitted 2019-08-28 cs.IT cs.LGeess.SPmath.ITmath.STstat.MLstat.TH

Zhaoqiang Liu , Jonathan Scarlett This is my paper · ORCID

classification cs.ITcs.LGeess.SPmath.ITmath.STstat.MLstat.TH MSC 94A1262C2068T07

keywords compressivesensinggenerativemodelsinformation-theoreticlowerboundssamplecomplexitygroupsparsityminimaxriskReLUnetworksLipschitzcontinuity

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 asks how many noisy linear measurements are truly needed to recover a signal known to lie near the range of a generative model. The authors prove algorithm-independent lower bounds: no estimator, however computationally powerful, can achieve squared error of order $\alpha$ unless the number of measurements is $\Omega\big(k \log \frac{L r}{\sqrt{\alpha}}\big)$ for spherical input domains, and $\Omega\big(k \log \frac{L r \sqrt{k}}{\sqrt{\alpha}}\big)$ for rectangular domains, where $k$ is the latent dimension and $L$ is the Lipschitz constant. For generative models implemented by ReLU networks with depth $d$ and width $w$, the necessary measurement count is $\Omega\big(k d \frac{\log w}{\log n}\big)$ in general, and $\Omega(k d \log w)$ in some regimes. These bounds match, up to constants or logarithmic factors, the previously known upper bounds from [14], so the existing scaling laws cannot be improved without additional assumptions. The proof works by constructing a simple Lipschitz or ReLU generative model that can generate group-sparse signals, then invoking minimax lower bounds for group-sparse recovery.

What carries the argument

The load-bearing object is a specially designed generative model that reduces the general problem to group-sparse recovery. For the Lipschitz case, the model divides the output into $k$ blocks and maps each scalar input $z_i$ through a double-triangular waveform into one block, so that exactly one entry per block is nonzero; its Lipschitz constant is $L = \frac{2 n x_{\max}}{k r}$. The argument then applies a minimax lower bound for estimating $k$-group-sparse signals from Gaussian measurements, obtained via a distance-based Fano inequality. The proof chooses the amplitude $x_{\max}$ and the output dimension $n$ so that the hard signal set fits inside the model range while the Lipschitz constraint is respected, forcing $m = \Omega\big(k \log \frac{n}{k}\big)$, which translates into the stated $k \log L$ bound. For ReLU networks, the same group-sparse signals are generated using recursive sawtooth and trapezoidal constructions, and standard ReLU implementation results control the width and depth, producing the stated depth/width dependence.

What would settle it

Instantiate the paper's double-triangular generative model with the prescribed parameters and compute the minimax risk over its range for a number of measurements $m$ below the claimed bound; if any estimator achieves average squared error $O(\alpha)$ on that constructed group-sparse signal set, then Lemma 2 would be false and the lower bound would collapse.

Watch

Extended reading notes

Core claim

The central discovery is that the sample-complexity scaling established in [14] for compressive sensing with generative models is not an artifact of any particular algorithm: it is an information-theoretic requirement. For bounded $L$-Lipschitz generative models with $k$-dimensional inputs, the paper constructs a generative model whose range consists of $k$-group-sparse signals, built from blockwise double-triangular scalar mappings. A minimax lower bound for group-sparse recovery then implies that any algorithm achieving average squared error $O(\alpha)$ in the idealized no-representation-error, no-optimization-error, i.i.d. Gaussian-noise setting needs $m = \Omega\big(k \log \frac{L r \sqrt{k}}{\sqrt{\alpha}}\big)$ measurements for rectangular domains and $m = \Omega\big(k \log \frac{L r}{\sqrt{\alpha}}\big)$ for spherical domains. For ReLU networks, a recursive construction generates $(k k_0)$-group-sparse signals and yields a necessary measurement count of $\Omega\big(k k_0 \log \frac{n}{k k_0}\big)$, which specialises to $\Omega\big(k d \frac{\log w}{\log n}\big)$ in general and $\Omega(k d \log w)$ in some regimes, matching the $O(k d \log w)$ upper bound up to a log factor or exactly. The lower bounds hold for every fixed measurement matrix with normalized Frobenius norm, so the bottleneck is intrinsic to the model class itself.

Load-bearing premise

The lower bounds hold only in the idealized setting where the signal lies exactly in the model range, optimization error is zero, and the noise is i.i.d. Gaussian, and the Lipschitz results additionally require the Lipschitz constant $L$ to be above a stated threshold relative to $\alpha$, $k$, and $r$; below that threshold the problem can become trivial and the bounds do not apply.

Editorial extensions

If this is right

The known upper bounds for Lipschitz generative models are tight up to constants in the idealized setting, so any further reduction in measurements must come from extra assumptions beyond Lipschitzness and bounded inputs.
For ReLU-network generative models, the $O(k d \log w)$ upper bound is optimal or near-optimal; in particular, the depth-2 high-width construction gives a regime with matching scaling up to mild logarithmic terms.
The lower bounds hold for any algorithm and any fixed measurement matrix with normalized Frobenius norm, meaning the sample-complexity bottleneck is a property of the model class, not of specific recovery procedures.
Because the proof uses a hard prior distribution over signals, the same lower bound applies even to average-case recovery guarantees over that prior, strengthening the impossibility result.
If one wants fewer measurements, one must impose structure beyond the Lipschitz or ReLU architectural assumptions, such as distributional or weight-based assumptions, since the model classes considered here alone do not lower the information-theoretic cost.

Reading between the lines

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

I read this result as a warning that worst-case Lipschitz generative priors have fundamentally limited sample efficiency; the empirical gains seen with generative priors may therefore rely on real signal distributions being far better than the worst case.
A natural testable extension would be to check whether natural image priors avoid the adversarial geometry of the constructed group-sparse model by attempting recovery with fewer than $k \log L$ measurements on realistic datasets.
The paper leaves open whether the extra $\log n$ factor in the general ReLU lower bound can be removed by sharper constructions; closing that gap would settle the exact constant-order sample complexity for deep generative models.
The same group-sparse reduction technique could plausibly be applied to other generative-model inverse problems, such as phase retrieval or non-Gaussian measurement models, to see whether the same scaling laws survive.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Two things you should know. First, the paper gives the first algorithm-independent lower bounds for compressive sensing with generative models, and the Lipschitz part is solid: the group-sparse hard-instance construction is elegant and the minimax argument checks out. Second, the ReLU-network result in Theorem 7 has a real bug in the proof as written. The stated amplitude ξ = Θ(√(α/k)) is too large by a factor √k0. Substituting the chosen m* into Lemma 2 (with K = kk0) yields ξ = Θ(√(α/(k k0))), not Θ(√(α/k)). With the larger ξ, the Fano ratio I/((K/3) log(n/K)) scales like Θ(k0) at m ≈ m*, so the lower bound becomes vacuous for large k0. This isn't a cosmetic typo: the proof explicitly claims the substitution gives the stated behavior. The fix is local — set ξ = Θ(√(α/(k k0))) and the Fano argument goes through unchanged, giving the same Ω(k k0 log(n/(k k0))) lower bound. The pulse construction still works at that smaller amplitude. So the theorem's conclusion likely stands, but a referee needs to require the correction.

What the paper does well: the construction of an L-Lipschitz generative model that encodes group sparsity, the exact Lipschitz calculation, and the careful reduction to known minimax bounds are all clean. The spherical-domain extension via the largest inscribed ∞-ball is crude but works, and they explain why. They also acknowledge the concurrent work by Kamath et al., and they are upfront about the log n gap in the ReLU lower bound.

Soft spots in proportion: the scope is the narrowly specialized setting of Corollaries 1-2 (no representation error, exact optimization, Gaussian noise), and the Lipschitz results need L above a small threshold; the paper states both clearly. The self-cited mutual-information bound in Appendix B is standard. These are minor.

Who it's for: anyone building on Bora et al. or working on minimax sample complexity for structured priors. It deserves a serious referee. My recommendation: send to peer review; accept after the Theorem 7 amplitude correction. The bug is load-bearing for that proof as written, but it is clearly fixable and the main contribution is sound.

Referee Report

1 major / 4 minor

Summary. The paper establishes algorithm-independent lower bounds on the number of measurements for compressive sensing with generative models. It constructs an explicit L-Lipschitz generative model whose range contains k-group-sparse signals, and combines this with a minimax lower bound for group-sparse recovery (Lemma 2) to show that, in a no-representation-error, no-optimization-error Gaussian-noise setting, any estimator with expected squared error O(alpha) needs m = Omega(k log L) measurements for both rectangular and spherical input domains (Theorems 3 and 4). These match the upper bounds of Bora et al. up to constants. For ReLU-network generative models, the paper constructs a more complex (k k0)-group-sparse signal generator and claims lower bounds that depend on depth and width (Theorem 7), showing the O(kd log w) upper bound is optimal or near-optimal in various regimes. The proofs are based on Fano-type inequalities; the main auxiliary result, Lemma 2, is proved in Appendix B, with a self-contained derivation of the mutual information bound and the covariance of the group-sparse prior.

Significance. If correct, the paper fills an important gap in the theory of compressive sensing with deep generative priors by showing that the sample-complexity scaling laws of Bora et al. cannot be improved without further assumptions. The Lipschitz lower bound construction is explicit, elementary, and directly matches the covering-number-based upper bound. The group-sparse minimax bound in Lemma 2 is carefully proved in an appendix, and the reciprocity between the constructed generative model and the group-sparse hard instance is transparent. These contributions are likely to become a standard reference for lower bounds in this area.

major comments (1)

[Section IV-B (Theorem 7) and Appendix B (Lemma 2)] In the proof of Theorem 7, Lemma 2 is applied with K = k k0 groups, sigma^2 = alpha/m, and ||A||_F^2 = C_A n. Lemma 2 requires the hard-signal amplitude to satisfy xi^2 = n sigma^2 log(n/K)/(4||A||_F^2) = alpha log(n/K)/(4 C_A m). With m = m* chosen as the largest integer below K log(n/K)/(64 C1 C_A), this yields xi^2 = Theta(alpha/(k k0)), not Theta(alpha/k). The theorem instead states xi = sqrt(C2 alpha/k), which is a factor sqrt(k0) larger. For the stated xi, the mutual information bound I(V;y) <= xi^2/(2 sigma^2) * (K/n)||A||_F^2 becomes Theta(k0) times the term (K/3) log(n/K) in the denominator of the Fano lower bound in (32)-(35), so the bound is vacuous for large k0. Thus the proof as written does not establish the first claim of Theorem 7 for its stated parameter xi. The theorem should either be corrected to xi = Theta(sqrt(alpha/(k k0))) with a suitable constant, or the proof must exhibit a hard subset of Range(G) at the smaller amplitude; the recursive pulse construction of Section IV-B does not obviously provide such a subset, since the pulses are defined with fixed amplitude xi on their respective intervals. This is a load-bearing gap in the main ReLU lower bound.

minor comments (4)

[Abstract] In the abstract, the phrase 'ReLU networks with high depth and/or high depth' should be 'with high depth and/or high width'; this appears to be a typographical error.
[Proof of Theorem 3] After setting C' = 1/sqrt(128 C1), the text says (21) reduces to m >= 1/(128 C' C_A) k log(n/k); substituting C' gives 1/(128 C1 C_A) k log(n/k), so the printed denominator appears to have a typographical error, replacing C1 with C'.
[Theorem 6] The statement 'depth O(log n/(kr))' is ambiguous; it should read O(log(n/(kr))) to clearly indicate the logarithm of the ratio.
[Proof of Theorem 7, part (b)] The claim that the width is a constant multiple of the number of outputs, w = O(n), would benefit from a brief justification that each of the n parallel outputs can be realized with O(1) width and the specified depth using the sawtooth construction.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower bounds are derived from explicit group-sparse hard-instance constructions and Fano/minimax arguments, not from the target upper bounds.

full rationale

The central derivation chain is self-contained. Lemma 2 proves a minimax lower bound for k-group-sparse recovery by placing a uniform prior on group-sparse ±1 patterns and applying Fano's inequality; the only self-citation is [34], used in Appendix B for the Gaussian mutual-information bound I(V;y) ≤ ξ²/(2σ²) E[||AV||²]. That bound is an auxiliary, parameter-free inequality for Gaussian channels with stated assumptions; it does not assert or assume any of the paper's target lower bounds, and the surrounding proof independently establishes Cov[V]=(k/n)I_n. Theorems 3 and 4 convert the resulting k log(n/k) necessity into k log(Lr√k/√α) and k log(Lr/√α) by explicitly constructing a generative model and choosing the free output dimension n and amplitude xmax via Lemma 1; this is a valid existential construction rather than an importation of the upper-bound scaling. Theorem 7 likewise applies Lemma 2 with K=kk0 groups and builds a ReLU-implementable recursive group-sparse generator, with depth/width trade-offs obtained from standard piecewise-linear ReLU representation results. The comparison with Corollaries 1 and 2 is for interpretation only and is not used as input to the lower-bound proofs. The only apparent circularity candidate, the self-citation [34], is non-load-bearing and independently verifiable, so it does not raise the score. Separately, the skeptical arithmetic check of Theorem 7's stated ξ=√(C2 α/k) against Lemma 2 is a proof-consistency/correctness concern, not a circularity, because the Fano argument does not assume the upper-bound conclusion; no prediction in the paper reduces by construction to its inputs.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The proofs rest on standard information-theoretic tools, explicit domain assumptions, and external ReLU representation results. The construction parameters n, x_max, xi, k0 and n0 are chosen to satisfy constraints in the lower bound, not fitted to data; no invented physical entities are introduced.

free parameters (4)

Output dimension n (hard-instance construction) = C' L r k^{3/2} / sqrt(alpha)
Set in Theorem 3 proof to make k log(n/k) = Theta(k log(L r sqrt(k)/sqrt(alpha))) and n >= C0 k. This is a lower-bound construction parameter, not fitted to data.
Signal magnitude xi (hard prior) = sqrt(alpha log(n/k)/(4 C_A m)) in Lemma 2; sqrt(C2 alpha/k) in Theorem 7
Chosen to balance the Fano bound; any smaller xi weakens the lower bound, any larger breaks x_max >= xi. A design choice for the hard instance.
x_max (output magnitude bound) = sqrt(alpha)/(2 C' sqrt(k))
Determined by equating L = 2 n x_max/(k r) with the chosen n; ensures the constructed model has Lipschitz constant L and can generate the hard prior signals.
ReLU block parameter k0 (and n0) = arbitrary subject to n0 >= C0 k0 and the chosen d-w tradeoff
Theorem 7's lower bound is stated for any k0; choosing k0 and n0 yields the depth-width tradeoffs in the three network cases.

assumptions (5)

standard math Fano's inequality and the distance-based minimax lower bound (Lemma 4 from [24])
Used in Appendix B to turn packing and hypothesis-testing bounds into estimation lower bounds.
domain assumption Gaussian noise model eta ~ N(0, (alpha/m) I) and chi-square concentration
Theorems 3, 4 and 7 are stated for this noise model; Corollaries 1 and 2 are simplified in the same setting.
domain assumption Signals lie exactly in Range(G), with no representation error and no optimization error
Specialized setting of Corollaries 1 and 2; the lower bounds inherit this restriction, noted before Corollary 1 and in Remarks 1-2.
domain assumption Lipschitz lower-bound condition L >= Omega((1/r) sqrt(alpha/k)) for rectangular and L >= Omega(sqrt(alpha)/r) for spherical domains
Used in the proofs to choose n and to ensure the log term is nontrivial; the paper calls the condition mild and notes the converse regime can be trivial.
standard math ReLU representation facts from [30]-[32]: piecewise-linear functions with N pieces are implementable by depth-2 width-O(N) ReLU networks, and sawtooth functions need depth O(log R)
Used in Theorem 7 to implement the hard-instance generative model as a ReLU network with the stated depth and width.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models." pith.science (2026). https://pith.science/paper/BRSCL7IL

@misc{pith2026190810744,
  author       = {Pith},
  title        = {Pith review of: Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BRSCL7IL}},
  note         = {Machine review of arXiv:1908.10744}
}

abstract

It has recently been shown that for compressive sensing, significantly fewer measurements may be required if the sparsity assumption is replaced by the assumption the unknown vector lies near the range of a suitably-chosen generative model. In particular, in (Bora {\em et al.}, 2017) it was shown roughly $O(k\log L)$ random Gaussian measurements suffice for accurate recovery when the generative model is an $L$-Lipschitz function with bounded $k$-dimensional inputs, and $O(kd \log w)$ measurements suffice when the generative model is a $k$-input ReLU network with depth $d$ and width $w$. In this paper, we establish corresponding algorithm-independent lower bounds on the sample complexity using tools from minimax statistical analysis. In accordance with the above upper bounds, our results are summarized as follows: (i) We construct an $L$-Lipschitz generative model capable of generating group-sparse signals, and show that the resulting necessary number of measurements is $\Omega(k \log L)$; (ii) Using similar ideas, we construct ReLU networks with high depth and/or high depth for which the necessary number of measurements scales as $\Omega\big( kd \frac{\log w}{\log n}\big)$ (with output dimension $n$), and in some cases $\Omega(kd \log w)$. As a result, we establish that the scaling laws derived in (Bora {\em et al.}, 2017) are optimal or near-optimal in the absence of further assumptions.

Figures

Figures reproduced from arXiv: 1908.10744 by the authors.

**Figure 1.** Example of a k-group-sparse signal with length n = 16 and sparsity k = 4. Each segment of size n k = 4 has one non-zero entry, indicated by being filled instead of blank. at most one non-zero entry.5 See [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

**Figure 2.** Generative model that produces sparse signals. This figure shows [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗

**Figure 3.** Illustration of how the functions in Figure [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Recursively defined generative model mapping a single input [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

**Figure 5.** Figure 5: Depiction of a sawtooth function with one triangular region (Left) and [PITH_FULL_IMAGE:figures/full_fig_p010_5.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Robust One-Bit Recovery via ReLU Generative Networks: Near-Optimal Statistical Rate and Global Landscape Analysis
math.ST 2019-08 conditional novelty 6.0 of 10

A dithered one-bit compressed sensing estimator over ReLU generative priors achieves O~(kn log d / epsilon^2) uniform recovery and a benign optimization landscape under a weight distribution condition.

Reference graph

Works this paper leans on

36 extracted references · 30 canonical work pages · cited by 1 Pith paper

[1]

Foucart and H

S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing. Springer New York, 2013. 11To see this, note that the bracketed term would exactly equal 1 2 if the log 2 term were dropped and we were to replace k 3 by k 4 in the denominator

work page 2013
[2]

M. J. Wainwright, High-dimensional statistics: A non-asymptotic view- point. Cambridge University Press, 2019, vol. 48

2019
[3]

Just relax: Convex programming methods for identifying sparse signals in noise,

J. A. Tropp, “Just relax: Convex programming methods for identifying sparse signals in noise,” IEEE Trans. Inf. Theory , vol. 52, no. 3, pp. 1030–1051, March 2006

work page 2006
[4]

Sharp thresholds for high-dimensional and noisy sparsity recovery using 𝓁1-constrained quadratic programming (Lasso),

M. Wainwright, “Sharp thresholds for high-dimensional and noisy sparsity recovery using 𝓁1-constrained quadratic programming (Lasso),” IEEE Trans. Inf. Theory , vol. 55, no. 5, pp. 2183–2202, May 2009

work page 2009
[5]

Greed is good: Algorithmic results for sparse approxi- mation,

J. A. Tropp, “Greed is good: Algorithmic results for sparse approxi- mation,” IEEE Trans. Inf. Theory , vol. 50, no. 10, pp. 2231–2242, Oct 2004

work page 2004
[6]

A sharp condition for exact support recovery with orthogonal matching pursuit,

J. Wen, Z. Zhou, J. Wang, X. Tang, and Q. Mo, “A sharp condition for exact support recovery with orthogonal matching pursuit,” IEEE Trans. Sig. Proc., vol. 65, no. 6, pp. 1370–1382, 2016

work page 2016
[7]

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

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

work page 2013
[8]

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

D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp, “Living on the edge: Phase transitions in convex programs with random data,” Information and Inference , vol. 3, no. 3, pp. 224–294, 2014

work page 2014

Show all 36 references

[9]

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

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

2009
[10]

On the fundamen- tal limits of adaptive sensing,

E. Arias-Castro, E. J. Candes, and M. A. Davenport, “On the fundamen- tal limits of adaptive sensing,” IEEE Trans. Inf. Theory , vol. 59, no. 1, pp. 472–481, Jan. 2013

2013
[11]

How well can we estimate a sparse vector?

E. J. Candes and M. A. Davenport, “How well can we estimate a sparse vector?” Appl. Comp. Harm. Analysis, vol. 34, no. 2, pp. 317–323, 2013

2013
[12]

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

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

2017
[13]

Foster, Generative Deep Learning : Teaching Machines to Paint, Write, Compose and Play

D. Foster, Generative Deep Learning : Teaching Machines to Paint, Write, Compose and Play . O’Reilly Media, Inc, USA, 2019

2019
[14]

Compressed sensing using generative models,

A. Bora, A. Jalal, E. Price, and A. G. Dimakis, “Compressed sensing using generative models,” in Int. Conf. Mach. Learn. (ICML) , 2017, pp. 537–546

2017
[15]

Model-based compressive sensing,

R. Baraniuk, V . Cevher, M. Duarte, and C. Hegde, “Model-based compressive sensing,” IEEE Trans. Inf. Theory, vol. 56, no. 4, pp. 1982– 2001, April 2010

1982
[16]

Solving linear inverse problems using GAN priors: An algorithm with provable guarantees,

V . Shah and C. Hegde, “Solving linear inverse problems using GAN priors: An algorithm with provable guarantees,” in IEEE Int. Conf. Acoust. Sp. Sig. Proc. (ICASSP) , 2018, pp. 4609–4613

2018
[17]

Solving inverse problems via auto-encoders,

S. Jalali and X. Yuan, “Solving inverse problems via auto-encoders,” 2019, https://arxiv.org/abs/1901.05045

2019 arXiv
[18]

Modeling sparse deviations for compressed sensing using generative models,

M. Dhar, A. Grover, and S. Ermon, “Modeling sparse deviations for compressed sensing using generative models,” inInt. Conf. Mach. Learn. (ICML), 2018

2018
[19]

Global guarantees for enforcing deep generative priors by empirical risk,

P. Hand and V . V oroninski, “Global guarantees for enforcing deep generative priors by empirical risk,” in Conf. Learn. Theory (COLT) , S. Bubeck, V . Perchet, and P. Rigollet, Eds., 2018, pp. 970–978

2018
[20]

On the statistical rate of nonlinear recovery in generative models with heavy-tailed data,

X. Wei, Z. Yang, and Z. Wang, “On the statistical rate of nonlinear recovery in generative models with heavy-tailed data,” in Int. Conf. Mach. Learn. (ICML) , 2019

2019
[21]

Compressed sensing with deep image prior and learned regularization,

D. Van Veen, A. Jalal, M. Soltanolkotabi, E. Price, S. Vishwanath, and A. G. Dimakis, “Compressed sensing with deep image prior and learned regularization,” https://arxiv.org/abs/1806.06438, 2018

2018 arXiv
[22]

Deep decoder: Concise image representations from untrained non-convolutional networks,

R. Heckel and P. Hand, “Deep decoder: Concise image representations from untrained non-convolutional networks,” in Int. Conf. Learn. Repr. (ICLR), 2019

2019
[23]

Lower bounds for compressed sensing with generative models,

A. Kamath, S. Karmalkar, and E. Price, “Lower bounds for compressed sensing with generative models,” 2019, https://arxiv.org/abs/1912.02938

2019 arXiv
[24]

Distance-based and continuum Fano inequalities with applications to statistical estimation,

J. C. Duchi and M. J. Wainwright, “Distance-based and continuum Fano inequalities with applications to statistical estimation,” 2013, https://arxiv.org/abs/1311.2669

2013 arXiv
[25]

Information theoretic bounds for compressed sensing,

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

2010
[26]

Shannon-theoretic limits on noisy com- pressive sampling,

M. Akcakaya and V . Tarokh, “Shannon-theoretic limits on noisy com- pressive sampling,”IEEE Trans. Inf. Theory, vol. 56, no. 1, pp. 492–504, Jan. 2010

2010
[27]

Approximate sparsity pattern recovery: Information-theoretic lower bounds,

G. Reeves and M. Gastpar, “Approximate sparsity pattern recovery: Information-theoretic lower bounds,” IEEE Trans. Inf. Theory , vol. 59, no. 6, pp. 3451–3465, June 2013

2013
[28]

Sparse signal processing with linear and nonlinear observations: A uniﬁed Shannon-theoretic 12 approach,

C. Aksoylar, G. K. Atia, and V . Saligrama, “Sparse signal processing with linear and nonlinear observations: A uniﬁed Shannon-theoretic 12 approach,” IEEE Trans. Inf. Theory , vol. 63, no. 2, pp. 749–776, Feb. 2017

2017
[29]

A probabilistic and RIPless theory of compressed sensing,

E. J. Candes and Y . Plan, “A probabilistic and RIPless theory of compressed sensing,”IEEE Trans. Inf. Theory, vol. 57, no. 11, pp. 7235– 7254, 2011

2011
[30]

Understanding deep neural networks with rectiﬁed linear units,

R. Arora, A. Basu, P. Mianjy, and A. Mukherjee, “Understanding deep neural networks with rectiﬁed linear units,” in Int. Conf. Learn. Repr. (ICLR), 2018

2018
[31]

Representation beneﬁts of deep feedforward networks,

M. Telgarsky, “Representation beneﬁts of deep feedforward networks,” 2015, https://arxiv.org/abs/1509.08101

2015 arXiv
[32]

Beneﬁts of depth in neural networks,

——, “Beneﬁts of depth in neural networks,” in Conf. Learn. Theory (COLT), 2016

2016
[33]

T. M. Cover and J. A. Thomas, Elements of Information Theory . John Wiley & Sons, Inc., 2006

2006
[34]

An introductory guide to Fano’s inequality with applications in statistical estimation,

J. Scarlett and V . Cevher, “An introductory guide to Fano’s inequality with applications in statistical estimation,” 2019, https://arxiv.org/abs/1901.00555

2019 arXiv
[35]

The universal approximation power of ﬁnite-width deep ReLU networks,

D. Perekrestenko, P. Grohs, D. Elbr ¨achter, and H. B ¨olcskei, “The universal approximation power of ﬁnite-width deep ReLU networks,” 2018, https://arxiv.org/abs/1806.01528

2018 arXiv
[36]

Depth- width trade-offs for ReLU networks via Sharkovsky’s theorem,

V . Chatziafratis, S. G. Nagarajan, I. Panageas, and X. Wang, “Depth- width trade-offs for ReLU networks via Sharkovsky’s theorem,” in Int. Conf. Learn. Repr. (ICLR) , 2020. Zhaoqiang Liu was born in China in 1991. He is currently a research fellow in School of Computing at th...

2020

Pith tools

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

[1] [1]

Foucart and H

S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing. Springer New York, 2013. 11To see this, note that the bracketed term would exactly equal 1 2 if the log 2 term were dropped and we were to replace k 3 by k 4 in the denominator

work page 2013

[2] [2]

M. J. Wainwright, High-dimensional statistics: A non-asymptotic view- point. Cambridge University Press, 2019, vol. 48

2019

[3] [3]

Just relax: Convex programming methods for identifying sparse signals in noise,

J. A. Tropp, “Just relax: Convex programming methods for identifying sparse signals in noise,” IEEE Trans. Inf. Theory , vol. 52, no. 3, pp. 1030–1051, March 2006

work page 2006

[4] [4]

Sharp thresholds for high-dimensional and noisy sparsity recovery using 𝓁1-constrained quadratic programming (Lasso),

M. Wainwright, “Sharp thresholds for high-dimensional and noisy sparsity recovery using 𝓁1-constrained quadratic programming (Lasso),” IEEE Trans. Inf. Theory , vol. 55, no. 5, pp. 2183–2202, May 2009

work page 2009

[5] [5]

Greed is good: Algorithmic results for sparse approxi- mation,

J. A. Tropp, “Greed is good: Algorithmic results for sparse approxi- mation,” IEEE Trans. Inf. Theory , vol. 50, no. 10, pp. 2231–2242, Oct 2004

work page 2004

[6] [6]

A sharp condition for exact support recovery with orthogonal matching pursuit,

J. Wen, Z. Zhou, J. Wang, X. Tang, and Q. Mo, “A sharp condition for exact support recovery with orthogonal matching pursuit,” IEEE Trans. Sig. Proc., vol. 65, no. 6, pp. 1370–1382, 2016

work page 2016

[7] [7]

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

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

work page 2013

[8] [8]

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

D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp, “Living on the edge: Phase transitions in convex programs with random data,” Information and Inference , vol. 3, no. 3, pp. 224–294, 2014

work page 2014