One-bit sensing, discrepancy and Stolarsky's principle

Dmitriy Bilyk   ; Michael T. Lacey

Sbornik. Mathematics, Tome 208 (2017) no. 6, pp. 744-763

Résumé

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.

Détail

Keywords: discrepancy, one-bit sensing, restricted isometry property, Stolarsky principle.

Bibliographie

[1] C. Aistleitner, J. S. Brauchart, J. Dick, “Point sets on the sphere $\mathbb{S}^2$ with small spherical cap discrepancy”, Discrete Comput. Geom., 48:4 (2012), 990–1024 | DOI | MR | Zbl

[2] K. Ball, “The Ribe programme”, Séminaire Bourbaki, Exposés 1043–1058, v. 2011/2012, Astérisque, 352, Soc. Math. France, Paris, 2013, viii, 147–159, Exp. No. 1047 | MR | Zbl

[3] R. Baraniuk, M. Davenport, R. DeVore, M. Wakin, “A simple proof of the restricted isometry property for random matrices”, Constr. Approx., 28:3 (2008), 253–263 | DOI | MR | Zbl

[4] R. Baraniuk, S. Foucart, D. Needell, Y. Plan, M. Wootters, Exponential decay of reconstruction error from binary measurements of sparse signals, arXiv: 1407.8246

[5] J. Beck, “Some upper bounds in the theory of irregularities of distribution”, Acta Arith., 43:2 (1984), 115–130 | MR | Zbl

[6] J. Beck, “Sums of distances between points on a sphere – an application of the theory of irregularities of distribution to discrete geometry”, Mathematika, 31:1 (1984), 33–41 | DOI | MR | Zbl

[7] J. Beck, W. W. L. Chen, Irregularities of distribution, Cambridge Tracts in Math., 89, Cambridge Univ. Press, Cambridge, 1987, xiv+294 pp. | DOI | MR | Zbl

[8] J. J. Benedetto, M. Fickus, “Finite normalized tight frames”, Adv. Comput. Math., 18:2-4 (2003), 357–385 | DOI | MR | Zbl

[9] D. Bilyk, F. Dai, R. Matzke, Stolarsky principle and energy optimization on the sphere, arXiv: 1611.04420

[10] D. Bilyk, M. T. Lacey, Random tessellations, restricted isometric embeddings, and one bit sensing, arXiv: 1512.06697

[11] M. Blümlinger, “Slice discrepancy and irregularities of distribution on spheres”, Mathematika, 38:1 (1991), 105–116 | DOI | MR | Zbl

[12] P. Boufounos, R. Baraniuk, “1-bit compressive sensing”, 2008 42nd annual conference on information sciences and systems CISS, IEEE, Princeton, NJ, 2008, 16–21 | DOI

[13] J. Bourgain, J. Lindenstrauss, “Distribution of points on spheres and approximation by zonotopes”, Israel J. Math., 64:1 (1988), 25–31 | DOI | MR | Zbl

[14] J. S. Brauchart, J. Dick, “A simple proof of Stolarsky's invariance principle”, Proc. Amer. Math. Soc., 141:6 (2013), 2085–2096 | DOI | MR | Zbl

[15] J. S. Brauchart, J. Dick, E. B. Saff, I. H. Sloan, Y. G. Wang, R. S. Womersley, “Covering of spheres by spherical caps and worst-case error for equal weight cubature in Sobolev spaces”, J. Math. Anal. Appl., 431:2 (2015), 782–811 | DOI | MR | Zbl

[16] E. J. Candes, T. Tao, “Near-optimal signal recovery from random projections: universal encoding strategies?”, IEEE Trans. Inform. Theory, 52:12 (2006), 5406–5425 | DOI | MR | Zbl

[17] P. G. Casazza, D. Redmond, J. C. Tremain, “Real equiangular frames”, 2008 42nd annual conference on information sciences and systems, IEEE, Princeton, NJ, 2008, 715–720 | DOI

[18] B. Chazelle, The discrepancy method. Randomness and complexity, Cambridge Univ. Press, Cambridge, 2000, xviii+463 pp. | DOI | MR | Zbl

[19] A. Dvoretzky, “Some results on convex bodies and Banach spaces”, Proc. Internat. Sympos. Linear Spaces (Jerusalem, 1960), Jerusalem Academic Press, Jerusalem; Pergamon, Oxford, 1961, 123–160 | MR | Zbl

[20] U. Feige, G. Schechtman, “On the optimality of the random hyperplane rounding technique for MAX CUT”, Random Structures Algorithms, 20:3 (2002), 403–440 | DOI | MR | Zbl

[21] S. Foucart, H. Rauhut, A mathematical introduction to compressive sensing, Appl. Numer. Harmon. Anal., Birkhäuser/Springer, New York, 2013, xviii+625 pp. | DOI | MR | Zbl

[22] K. G. Larsen, J. Nelson, “The Johnson–Lindenstrauss lemma is optimal for linear dimensionality reduction”, 43rd international colloquium on automata, languages, and programming (ICALP 2016) (Rome, 2016), LIPIcs, 55, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, 2016, 82, 11 pp. | DOI

[23] L. Jacques, K. Degraux, C. De Vleeschouwer, “Quantized iterative hard thresholding: bridging 1-bit and high-resolution quantized compressed sensing”, 10th international conference on sampling theory and applications (SampTA 2013), 2013, 105–108 http://www.eurasip.org/Proceedings/Ext/SampTA2013/papers/p105-jacques.pdf

[24] L. Jacques, J. N. Laska, P. T. Boufounos, R. G. Baraniuk, “Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors”, IEEE Trans. Inform. Theory, 59:4 (2013), 2082–2102 | DOI | MR

[25] P. Leopardi, “A partition of the unit sphere into regions of equal area and small diameter”, Electron. Trans. Numer. Anal., 25 (2006), 309–327 | MR | Zbl

[26] P. Leopardi, “Diameter bounds for equal area partitions of the unit sphere”, Electron. Trans. Numer. Anal., 35 (2009), 1–16 | MR | Zbl

[27] J. Matoušek, Geometric discrepancy. An illustrated guide, Algorithms Combin., 18, Springer-Verlag, Berlin, 1999, xii+288 pp. | DOI | MR | Zbl

[28] A. Naor, “An introduction to the Ribe program”, Jpn. J. Math., 7:2 (2012), 167–233 | DOI | MR | Zbl

[29] F. Pausinger, S. Steinerberger, “On the discrepancy of jittered sampling”, J. Complexity, 33 (2016), 199–216 ; arXiv: 1510.00251 | DOI | MR | Zbl

[30] Y. Plan, R. Vershynin, “One-bit compressed sensing by linear programming”, Comm. Pure Appl. Math., 66:8 (2013), 1275–1297 | DOI | MR | Zbl

[31] Y. Plan, R. Vershynin, “Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach”, IEEE Trans. Inform. Theory, 59:1 (2013), 482–494 | DOI | MR

[32] Y. Plan, R. Vershynin, “Dimension reduction by random hyperplane tessellations”, Discrete Comput. Geom., 51:2 (2014), 438–461 | DOI | MR | Zbl

[33] A. Reznikov, E. B. Saff, “The covering radius of randomly distributed points on a manifold”, Int. Math. Res. Not. IMRN, 2016:19 (2016), 6065–6094 | DOI | MR

[34] G. Schechtman, “Two observations regarding embedding subsets of Euclidean spaces in normed spaces”, Adv. Math., 200:1 (2006), 125–135 | DOI | MR | Zbl

[35] K. B. Stolarsky, “Sums of distances between points on a sphere. II”, Proc. Amer. Math. Soc., 41:2 (1973), 575–582 | DOI | MR | Zbl

[36] S. Tabachnikov, Geometry and billiards, Stud. Math. Libr., 30, Amer. Math. Soc., Providence, RI; Mathematics Advanced Study Semesters, University Park, PA, 2005, xii+176 pp. | DOI | MR | Zbl

[37] V. Temlyakov, Greedy approximation, Cambridge Monogr. Appl. Comput. Math., 20, Cambridge Univ. Press, Cambridge, 2011, xiv+418 pp. | DOI | MR | Zbl

[38] S. Torquato, “Reformulation of the covering and quantizer problems as ground states of interacting particles”, Phys. Rev. E (3), 82:5 (2010), 056109, 52 pp. ; arXiv: 1009.1443 | DOI

[39] R. Vershynin, “Introduction to the non-asymptotic analysis of random matrices”, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, 210–268 | DOI | MR