Near-optimal sample complexity bounds for circulant binary embedding
Samet Oymak, Christos Thrampoulidis, Babak Hassibi
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 ℝ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> can be properly embedded into the Hamming cube {±1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">k</sup> with δ distortion, by using k ~ δ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-3</sup> log N samples which is optimal in the number of points N and compares well with the optimal distortion dependency δ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-2</sup> . Our optimal embedding result applies in the regime log N ≲ n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/3</sup> . 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.
BibTeX
@inproceedings{icassp2017_nearoptimalsampl,
title = {Near-optimal sample complexity bounds for circulant binary embedding},
author = {Samet Oymak and Christos Thrampoulidis and Babak Hassibi},
booktitle = {ICASSP 2017},
year = {2017}
}