AAAI 2018

On the Optimal Bit Complexity of Circulant Binary Embedding

Saehoon Kim, Jungtaek Kim, Seungjin Choi

In this paper, to support promising empirical results of CBE, we extend the previous theoretical framework to address the optimal condition on the number of bits, achieving that CBE requires the same number of bits to approximate the angle up to epsilon-distortion under mild assumptions. We also provide numerical experiments to support our theoretical results.