Inspired by the advances in biological science, the study of sparse binary projection models has attracted considerable recent research attention. The models project dense input samples into a higher-dimensional space and output sparse binary data representations after Winner-Take-All competition, subject to the constraint that the projection matrix is also sparse and binary. Following the work along this line, we developed a supervised-WTA model when training samples with both input and output representations are available, from which the optimal projection matrix can be obtained with a simple, efficient yet effective algorithm. We further extended the model and the algorithm to an unsupervised setting where only the input representation of the samples is available. In a series of empirical evaluation on similarity search tasks, the proposed models reported significantly improved results over the state-of-the-art methods in both search accuracy and running time. The successful results give us strong confidence that the work provides a highly practical tool to real world applications.
The paper takes the binary projection framework used for LSH-type applications (based on Dasgupta et al. 2017) and given training data from that framework, shows an efficient closed-form solution update for the "projection" matrix, and also derives an alternating minimization algorithm for when training data are not available (note that these are not training data in a typical supervised learning sense, i.e., they are not data features, but rather the output of a projection of the very specific type discussed in the paper).
The idea is interesting, and the recent literature suggest that the overall idea works well. This new paper seems to work much better than recent literature (and a lot faster than some), which is very encouraging. The derivation of the closed-form updates is clever and seems to be correct.  Overall, I am quite favorable for this paper.
My chief critical comment is that given the complexity of the model, is is feasible to compare to PCA-based projections as well. That is, usually PCA is not compared with these methods since a random projection method is faster. But this paper proposes data-dependent projection matrices, which is exactly what PCA does.  This paper has been implicitly assuming d << n and trying to avoid the O(n^2) cost of nearest neighbor search. Given that d << n, the complexity of the algorithm in the paper is, roughly (avoiding some logs), O((#iter) d^2 n ), since the constant "c" depends on d, and presumably d' also scales linearly with d. The (#iter) refers to the number of iterations of the alternating minimization. The actual constants are small, but it is still quadratic in d.  PCA takes O(d^2n + d^3) operations when d<n, so therefore PCA is of roughly the same complexity, and thus I'd expect you to compare to it in the numerical comparisons.
With a valid response to the issue of PCA, I would probably "strongly accept" this paper.
(Another note on comparisons: it seems Johnson-Lindenstrauss projections would be applicable, so I'd suggest running a Fast Johnson-Lindenstrauss (Ailon and Chazelle) to compare with also).
Minor notes:
- In section 3.3, how do you get complexities like d log(c) for finding the top c entries? Please cite an algorithm textbook. I might be rusty on this, but the algorithms I can think of to do this are O(  min( d log(d), d c )) operations. Same for the  d' log(k).
- A good number of sentences were grammatically incorrect or sounded awkward, e.g., paragraph 2, "people's much attention"; second sentence in section 2.2, the phrase "; while the rest get inhibited and remain silent" is not a complete phrase by itself (maybe change the semicolon to a comma). Overall, another round of proof reading would help.