CaltechAUTHORS
  A Caltech Library Service

Near-optimal sample complexity bounds for circulant binary embedding

Oymak, Samet and Thrampoulidis, Christos and Hassibi, Babak (2017) Near-optimal sample complexity bounds for circulant binary embedding. In: 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE , Piscataway, NJ, pp. 6359-6363. ISBN 978-1-5090-4117-6 . http://resolver.caltech.edu/CaltechAUTHORS:20170621-165223982

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20170621-165223982

Abstract

Binary embedding is the problem of mapping points from a high-dimensional space to a Hamming cube in lower dimension while preserving pairwise distances. An efficient way to accomplish this is to make use of fast embedding techniques involving Fourier transform e.g. circulant matrices. While binary embedding has been studied extensively, theoretical results on fast binary embedding are rather limited. In this work, we build upon the recent literature to obtain significantly better dependencies on the problem parameters. A set of N points in ℝ^n can be properly embedded into the Hamming cube {±1}^k with δ distortion, by using k ∼ δ^−3 log N samples which is optimal in the number of points N and compares well with the optimal distortion dependency δ^−2. Our optimal embedding result applies in the regime log N ≲ n^(1/3). Furthermore, if the looser condition log N ≲ √n holds, we show that all but an arbitrarily small fraction of the points can be optimally embedded. We believe the proposed techniques can be useful to obtain improved guarantees for other nonlinear embedding problems.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1109/ICASSP.2017.7953380DOIArticle
http://ieeexplore.ieee.org/document/7953380/PublisherArticle
Additional Information:© 2017 IEEE.
Record Number:CaltechAUTHORS:20170621-165223982
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20170621-165223982
Official Citation:S. Oymak, C. Thrampoulidis and B. Hassibi, "Near-optimal sample complexity bounds for circulant binary embedding," 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), New Orleans, LA, USA, 2017, pp. 6359-6363. doi: 10.1109/ICASSP.2017.7953380
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78444
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:22 Jun 2017 01:19
Last Modified:22 Jun 2017 01:19

Repository Staff Only: item control page