Fast Similarity Search via Optimal Sparse Lifting
Similarity search is a fundamental problem in computing science with various applications and has attracted significant research attention, especially in largescale search with high dimensions. Motivated by the evidence in biological science, our work develops a novel approach for similarity search. Fundamentally different from existing methods that typically reduce the dimension of the data to lessen the computational complexity and speed up the search, our approach projects the data into an even higher-dimensional space while ensuring the sparsity of the data in the output space, with the objective of further improving precision and speed. Specifically, our approach has two key steps. Firstly, it computes the optimal sparse lifting for given input samples and increases the dimension of the data while approximately preserving their pairwise similarity. Secondly, it seeks the optimal lifting operator that best maps input samples to the optimal sparse lifting. Computationally, both steps are modeled as optimization problems that can be efficiently and effectively solved by the Frank-Wolfe algorithm. Simple as it is, our approach has reported significantly improved results in empirical evaluations, and exhibited its high potentials in solving practical problems.
The paper studies the method of hashing a vector inspired by the "fly algorithm" where flies apparently lift an input vector in the olfactory system (after mean shift)  into a higher dimensional space and then sparsify the resulting lifted vector by taking its top k coordinates. Earlier work[ 8] shows that the fly algorithm is a strong alternative to random hyperplane based LSH for similarity search. In this work they provide an algorithm to compute the optimal projection matrix instead of using a random one so that the similarity matrix preserved after the lift. They show experimentally that it outperforms autoencoder, random non optimized fly algorithm, standard LSH for similarity search.  The approach is intriguing and the inspiration from fly visual cortex is very interesting. But the theme of the paper overlaps with the previous work [8] and the main novelty here is the optimization of the projection matrix. The writing and flow of the presentation could  use some improvement.  First to convey the value of the fly algorithm it would be useful to briefly state the exact gains from [8] of this algorithm over standard LSH early on rather than the reader having to reach the experiment section.  Randomized vs optimal lifting: I am also curious if the fly's cortex is believed to use random or "trained" lifting-projection matrix W. If the intent here is to learn a better W to improve upon a random one then you should mention this point up front.  In section 4.2, I found the experimental evaluation metric and the ground truth G to be a bit confusing.  Why is resizing the images using cubic interpolation the right baseline? Shouldn't you instead check something like how well the output hash can predict the digit. Also, what was the value of k that was used?  In comparing autoencoder, LSH and optimal lift/fly, you should also take into account the total number of bits used to represent the final hash values: Besides the number of  hashes you also need to take into account the number of bits required for each hash. For your algorithm it will be log_2(d'). How much was it for LSH.  I couldn't find where \mathcal{Y} was defined: is it the set of k-sparse vectors?