EUVIMEDEUVIMED entdecken
Crossref

The all-or-nothing phenomenon in sparse linear regression

Galen Reeves, Jiaming Xu, Ilias Zadik

Mathematical Statistics and Learning · 2021

DOI: 10.4171/msl/22 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematical Statistics and Learning, 2021. Verfasst von Galen Reeves und 2 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of recovering a hidden binary k -sparse p -dimensional vector \beta from n noisy linear observations Y=X\beta+W , where X_{ij} are i.i.d. \mathcal{N}(0,1) and W_i are i.i.d. \mathcal{N}(0,\sigma^2) . A closely related hypothesis testing problem is to distinguish the pair (X,Y) generated from this structured model from a corresponding null model where (X,Y) consist of purely independent Gaussian entries. In the low sparsity k=o(\sqrt{p}) and high signal-to-noise ratio k/\sigma^2 \to \infty regime, we establish an “all-or-nothing” information-theoretic phase transition at a critical sample size n^{\ast}=2 k\log (p/k) /\log (1+k/\sigma^2) , resolving a conjecture of Gamarnik and Zadik (2017). Specifically, we show that if \liminf_{p\to \infty} n/n^{\ast}>1 , then the maximum likelihood estimator almost perfectly recovers the hidden vector with high probability and moreover the true hypothesis can be detected with a vanishing error probability. Conversely, if \limsup_{p\to \infty} n/n^{\ast}

Zitieren

APA

Reeves, G., Xu, J., & Zadik, I. (2021). The all-or-nothing phenomenon in sparse linear regression. Mathematical Statistics and Learning. https://doi.org/10.4171/msl/22

Vancouver

Reeves G, Xu J, Zadik I. The all-or-nothing phenomenon in sparse linear regression. Mathematical Statistics and Learning. 2021. doi:10.4171/msl/22

BibTeX
@article{Reeves2021,
  author = {Reeves, Galen and Xu, Jiaming and Zadik, Ilias},
  title = {The all-or-nothing phenomenon in sparse linear regression},
  journal = {Mathematical Statistics and Learning},
  year = {2021},
  doi = {10.4171/msl/22}
}
Kostenlos starten →