Sparse similarity-preserving hashing
Authors: Alex M. Bronstein, Guillermo Sapiro, Pablo Sprechmann, Jonathan Masci, Michael M. Bronstein
ICLR 2014

Abstract: In recent years, a lot of attention has been devoted to efficient nearest neighbor search by means of similarity-preserving hashing. One of the plights of existing hashing techniques is the intrinsic trade-off between performance and computational complexity: while longer hash codes allow for lower false positive rates, it is very difficult to increase the embedding dimensionality without incurring in very high false negatives rates or prohibiting computational costs. In this paper, we propose a way to overcome this limitation by enforcing the hash codes to be sparse. Sparse high-dimensional codes enjoy from the low false positive rates typical of long hashes, while keeping the false negative rates similar to those of a shorter dense hashing scheme with equal number of degrees of freedom. We use a tailored feed-forward neural network for the hashing function. Extensive experimental evaluation involving visual and multi-modal data shows the benefits of the proposed method.


Peer review:
[Review]:
The authors propose to use a to use a sparse locally sensitive hash along with an appropriate hashing function. The retrieval of sparse codes has different behaviour then dense code, which results in better performance then other other methods especially at low retrieval radius where computation is cheaper.

Novelty: Good (as far as I know). 
Quality: Good, clearly explained except few details (see below), with experimental evaluation.

Details:
- How do you define retrieval at a given radius for sparse codes? With two bit flips say, there are the same number of neighbours whether the code is dense or sparse. With the encoding proposed you don't have a guaranteed that only k values will be nonzero - it is not a strict bound. How do you define the neighbours - as only those that have the same or lower sparsity? 
 
- Is formula (4) correct, specifically line 2? I assume it should be more like the line 2 of eq. (3).

- In the experiments, how did you calculate neighbours of such large radii - the number of neighbours grows as Choose(m, r). 

- There are a lot of hyper parameters: eq.4: lambda, alpha, M + eq. 5 mu_1, mu_2. How did you choose these? If your answer is 'cross validation' - how theses are a lot of parameters to cross validate. Do you have any good ways to set these?

- Even though this is basic it would be good to explain in section 2(Efficient Retrieval) how is the retrieval defined - what is the situation?