Euclidean distance compression via deep random features

Motivated by the problem of compressing point sets into as few bits as possible while maintaining information about approximate distances between points, we construct random nonlinear maps varphiℓ that compress point sets in the following way. For a point set S, the map varphiℓ:ℝd → N-1/2-1,1N has the property that storing varphiℓ(S) (a sketch of S) allows one to report pairwise squared distances between points in S up to some multiplicative (1± ε) error with high probability as long as the minimum distance is not too small compared to ε. The maps varphiℓ are the ℓ-fold composition of a certain type of random feature mapping. Moreover, we determine how large N needs to be as a function of ε and other parameters of the point set. Compared to existing techniques, our maps offer several advantages. The standard method for compressing point sets by random mappings relies on the Johnson-Lindenstrauss lemma which implies that if a set of n points is mapped by a Gaussian random matrix to ℝk with k =Theta(ε-2log n), then pairwise distances between points are preserved up to a multiplicative (1± ε) error with high probability. The main advantage of our maps varphiℓ over random linear maps is that ours map point sets directly into the discrete cube N-1/2-1,1N and so there is no additional step needed to convert the sketch to bits. For some range of parameters, our maps varphiℓ produce sketches which require fewer bits of storage space.