One-bit sensing, discrepancy and Stolarsky's principle

D. Bilyk, M. T. Lacey

Research output: Contribution to journalArticlepeer-review

13 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)744-763
Number of pages20
JournalSbornik Mathematics
Issue number6
StatePublished - 2017

Bibliographical note

Funding Information:
The research was partially supported by NSF (grants nos. DMS 1101519 and DMS 1265570). AMS 2010 Mathematics Subject Classification. Primary 11K38, 94A12, 94A20; Secondary 52C99.

Publisher Copyright:
© 2017 Russian Academy of Sciences (DoM), London Mathematical Society, Turpion Ltd.

Copyright 2019 Elsevier B.V., All rights reserved.


  • Discrepancy
  • One-bit sensing
  • Restricted isometry property
  • Stolarsky principle


Dive into the research topics of 'One-bit sensing, discrepancy and Stolarsky's principle'. Together they form a unique fingerprint.

Cite this