Part of Advances in Neural Information Processing Systems 37 (NeurIPS 2024) Main Conference Track
Brett Leroux, Luis Rademacher
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 φℓ that compress point sets in the following way. For a point set S, the map φℓ:Rd→N−1/2{−1,1}N has the property that storing φℓ(S) (a sketch of S) allows one to report squared distances between points up to some multiplicative (1±ϵ) error with high probability. The maps φℓ are the ℓ-fold composition of a certain type of random feature mapping. 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 and involves compressing point sets with a random linear map. The main advantage of our maps φℓ over random linear maps is that ours map point sets directly into the discrete cube N−1/2{−1,1}N and so there is no additional step needed to convert the sketch to bits. For some range of parameters, our maps φℓ produce sketches using fewer bits of storage space. We validate the method with experiments, including an application to nearest neighbor search.