TY - JOUR
T1 - One-bit sensing, discrepancy and Stolarsky's principle
AU - Bilyk, D.
AU - Lacey, M. T.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - A sign-linear one-bit map from the d-dimensional sphere Sd to the N-dimensional Hamming cube HN = {-1,+1}n is given by × ↦ {sign(x · zj): 1 ≤ j ≤ N}, where {zj} C Sd. For 0 < δ < 1, we estimate N(d,δ), the smallest integer N so that there is a sign-linear map which has the δ-restricted isometric property, where we impose the normalized geodesic distance on Sd and the Hamming metric on HN. Up to a polylogarithmic factor, N(d,δ) ≈ δ-2+2/(d+1), which has a dimensional correction in the power of δ. 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 L2-average of the embedding error is equivalent to minimizing the discrete energy Σi,j (1/2 - d(zi, zj)2, where d is the normalized geodesic distance.
AB - A sign-linear one-bit map from the d-dimensional sphere Sd to the N-dimensional Hamming cube HN = {-1,+1}n is given by × ↦ {sign(x · zj): 1 ≤ j ≤ N}, where {zj} C Sd. For 0 < δ < 1, we estimate N(d,δ), the smallest integer N so that there is a sign-linear map which has the δ-restricted isometric property, where we impose the normalized geodesic distance on Sd and the Hamming metric on HN. Up to a polylogarithmic factor, N(d,δ) ≈ δ-2+2/(d+1), which has a dimensional correction in the power of δ. 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 L2-average of the embedding error is equivalent to minimizing the discrete energy Σi,j (1/2 - d(zi, zj)2, where d is the normalized geodesic distance.
KW - Discrepancy
KW - One-bit sensing
KW - Restricted isometry property
KW - Stolarsky principle
UR - http://www.scopus.com/inward/record.url?scp=85027987946&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85027987946&partnerID=8YFLogxK
U2 - 10.1070/SM8656
DO - 10.1070/SM8656
M3 - Article
AN - SCOPUS:85027987946
VL - 208
SP - 744
EP - 763
JO - Sbornik Mathematics
JF - Sbornik Mathematics
SN - 1064-5616
IS - 6
ER -