English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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

Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models