Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets

MaRDI QIDQ6268384zbMATH OpenFDO

Authors Samet Oymak, Benjamin Recht

Publication date 14 December 2015

Abstract: We study embedding a subset $K$ of the unit sphere to the Hamming cube ${-1,+1}^m$. We characterize the tradeoff between distortion and sample complexity $m$ in terms of the Gaussian width $omega(K)$ of the set. For subspaces and several structured sets we show that Gaussian maps provide the optimal tradeoff $msimdelt{a}^{-2}omeg{a}^2(K)$, in particular for $delta$ distortion one needs $mapproxdelt{a}^{-2}d$ where $d$ is the subspace dimension. For general sets, we provide sharp characterizations which reduces to $mapproxdelt{a}^{-4}omeg{a}^2(K)$ after simplification. We provide improved results for local embedding of points that are in close proximity of each other which is related to locality sensitive hashing. We also discuss faster binary embedding where one takes advantage of an initial sketching procedure based on Fast Johnson-Lindenstauss Transform. Finally, we list several numerical observations and discuss open problems.

This page was built for publication: Near-Optimal Bounds for Binary Embeddings of Arbitrary Sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6268384)