EUVIMEDEUVIMED entdecken
Crossref

Sharp Estimates on Random Hyperplane Tessellations

Sjoerd Dirksen, Shahar Mendelson, Alexander Stollenwerk

SIAM Journal on Mathematics of Data Science · 31.12.2022 · 4 (4) · 1396-1419

DOI: 10.1137/22m1485826 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Mathematics of Data Science, online erschienen am 20.12.2022. Verfasst von Sjoerd Dirksen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 9 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We study the problem of generating a hyperplane tessellation of an arbitrary set [Formula: see text] in [Formula: see text], ensuring that the Euclidean distance between any two points corresponds to the fraction of hyperplanes separating them up to a prespecified error [Formula: see text]. We focus on random Gaussian tessellations with uniformly distributed shifts and derive sharp bounds on the number of hyperplanes [Formula: see text] that are required. This result has natural applications in data dimension reduction—it yields a binary version of the Johnson–Lindenstrauss embedding—and signal processing under coarse quantization. Surprisingly, our lower estimates falsify the conjecture that [Formula: see text], where [Formula: see text] is the Gaussian width of [Formula: see text], is optimal. This conjecture is the natural analogue of a conjecture by Plan and Vershynin on random tessellations of subsets of the Euclidean sphere. As it turns out, the true optimal rate is larger by an order of magnitude in the accuracy parameter [Formula: see text] and depends in an intricate way on the geometry of the set. In particular, we give an explicit example where [Formula: see text] is required. To the best of our knowledge, the fact that the optimal error decay rate depends on the geometry of the set [Formula: see text] is a new phenomenon in the general context of random embeddings.

Zitieren

APA

Dirksen, S., Mendelson, S., & Stollenwerk, A. (2022). Sharp Estimates on Random Hyperplane Tessellations. SIAM Journal on Mathematics of Data Science, 4(4), 1396-1419. https://doi.org/10.1137/22m1485826

Vancouver

Dirksen S, Mendelson S, Stollenwerk A. Sharp Estimates on Random Hyperplane Tessellations. SIAM Journal on Mathematics of Data Science. 2022;4(4):1396-1419. doi:10.1137/22m1485826

BibTeX
@article{Dirksen2022,
  author = {Dirksen, Sjoerd and Mendelson, Shahar and Stollenwerk, Alexander},
  title = {Sharp Estimates on Random Hyperplane Tessellations},
  journal = {SIAM Journal on Mathematics of Data Science},
  year = {2022},
  volume = {4},
  number = {4},
  pages = {1396--1419},
  doi = {10.1137/22m1485826}
}
Kostenlos starten →