|
This article is cited in 15 scientific papers (total in 15 papers)
One-bit sensing, discrepancy and Stolarsky's principle
Dmitriy Bilyka, Michael T. Laceyb a School of Mathematics, University of Minnesota, Minneapolis, MN, USA
b School of Mathematics, Georgia Institute of Technology, Atlanta, GA, USA
Abstract:
A sign-linear one-bit map from the $d$-dimensional sphere $\mathbb S^{d}$ to the $N$-dimensional Hamming cube $H^N=\{-1, +1\}^{n}$ is given by
$$
x \mapsto \{\mathrm{sign} (x \cdot z_j) \colon 1\leq j \leq N\},
$$
where $\{z_j\} \subset \mathbb S^{d}$. For $0<\delta<1$, we estimate $N(d,\delta)$, the smallest integer $N$ so that there is a sign-linear map which has the $\delta$-restricted isometric property, where we impose the normalized geodesic distance on $\mathbb S^{d}$ and the Hamming metric on $H^N$. Up to a polylogarithmic factor, $N(d,\delta)\approx\delta^{-2 + 2/(d+1)}$, which has a dimensional correction in the power of $\delta$. This is a question that arises from the one-bit sensing literature, and the method of proof follows from geometric discrepancy theory. We also obtain an analogue of the Stolarsky invariance principle for this situation, which implies that minimizing the $L^2$-average of the embedding error is equivalent to minimizing the discrete energy $\sum_{i,j} \bigl(\frac12 - d(z_i,z_j) \bigr)^2$, where $d$ is the normalized geodesic distance.
Bibliography: 39 titles.
Keywords:
discrepancy, one-bit sensing, restricted isometry property, Stolarsky principle.
Received: 21.12.2015 and 13.12.2016
Citation:
Dmitriy Bilyk, Michael T. Lacey, “One-bit sensing, discrepancy and Stolarsky's principle”, Mat. Sb., 208:6 (2017), 4–25; Sb. Math., 208:6 (2017), 744–763
Linking options:
https://www.mathnet.ru/eng/sm8656https://doi.org/10.1070/SM8656 https://www.mathnet.ru/eng/sm/v208/i6/p4
|
Statistics & downloads: |
Abstract page: | 496 | Russian version PDF: | 71 | English version PDF: | 15 | References: | 39 | First page: | 19 |
|