It is well known that $\R^N$ has subspaces of dimension proportional to $N$ on which the $\ell_1$ norm is equivalent to the $\ell_2$ norm; however, no explicit constructions are known. Extending earlier work by Artstein--Avidan and Milman, we prove that such a subspace can be generated using $O(N)$ random bits. more >>>

The Earth Mover Distance (EMD) between two equal-size sets of points in R^d is defined to be the minimum cost of a bipartite matching between the two pointsets. It is a natural metric for comparing sets of features, and as such, it has received significant interest in computer vision. Motivated ... more >>>