Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The authors present a distance preserving embedding algorithm to reduce the dimensionality / encoding of a high dimensional Euclidean point-set. The proposed embedding is a combination of stable noise-shaping quantization and sparse Johnson-Lindenstrauss transformations. The proposed method requires O(m) time and space complexity. The main contribution of the paper is Theorem 1.1 where the authors prove a bound on the distortion of the proposed embedding. The (additive) distortion consist of two terms due to the quantization error and JL relative error.


Reasons for score:
Overall, I vote for a slightly below acceptable due to the following concerns: (a) after reading the paper it was not clear if the authors do assume that the input pointset are well-spread or not. Theorem 1.1 states that the input points are well-spread and moreover Algorithm 1 assumes (implicitly) that the input is normalized. (b) the time complexity of the embedding is O(m) for well-spread vectors. In the first sentence of Section 5, the authors state that well-spread vectors can be assumed after an fast JL transformation. Indeed, but then the running time is not O(m), right? To transform any point-set to well-spread position you need at least O(nlogn).

Strong points:
* Well written paper with a clear contribution statement
* Concise algorithm description and corresponding theoretical guarantees.

Concerns:
* References to input sparsity time embedding (see below) are missing. How does your results compare to these papers?
* Theorem 1.1: Is the main contribution here the quantization part of the statement? It is known that the input pointset can be efficiently projected to p dimensions. Is it possible to decouple your contribution on quantization with JL projections?
* Theorem 1.1: Isn't the assumption of well-spreadness too strong here? If the vectors are so well-spread, I believe that uniformly sampling of coodinates could also work. Please discuss it in the paper.

Minor comments:
*Introduction: what is an $\epsilon$-Lipschitz distortion? Do you mean (1+\eps) distortion?
*Introduction: You may want to compare/discuss your work with input sparsity embeddings by Woodruff and Clarkson "Low Rank Approximation and Regression in Input Sparsity Time" and relevant count-min sketch embeddings.
* Algorithm 1: does algorithm 1 requires scaled data points or is this required only for the analysis?
* Equation (20) is referenced quite early. Please consider introducing it earlier.
* Theorem 1.1: "with high probability" -> this can be made more explicit using the \delta parameter as in the appendix.
* In general, there are several forward looking references in the text ("Finally, Definition 2.3 shows..", "Equation (20)". Please minimize such forward references.
* Theorem 4.2: Isn't it better to fix \beta to be greater than O(ln |T| / \delta). Otherwise the probability statements involve negative probabilities.
* Section 5, first sentence: rephrase the "without of loss of generality" statement.
review_title: Fast Binary Embeddings

final_score: rating: 7: Good paper, accept
review_content: This paper proposes a scheme for fast distance-preserving binary embeddings of R^n into {-1/+1}^m. Guarantees are given for embedding l2-distance in the host space. Under certain assumptions about the input data both encoding and decoding can be done in O(m) time/space, which improves substantially upon the O(n log n) complexity from the previous work. Compared to the previous work by Huynh and Saab (2020) and Chou and Gunturk (2016) the key idea is to apply condensed JL transform instead of the Sigma-Delta quantization or other quantization methods used by the previous work. This is a very natural idea and it is somewhat surprising that this hasn’t been done before. 

The overall technical result is highly technical to state (Theorem 4.2) so I won’t attempt to fully reproduce it here. On a technical level the results in this paper are hardly too surprising for the JL community, but it is nice to see this analysis worked out in detail. The key weakness of this paper is that in order to get optimal time/space complexity strong assumptions on the input vectors are required. The well-spread assumption used in the paper roughly corresponds to saying that the input vectors look like +/- O(1) in most coordinates, which might be unrealistic in the case of inputs with a small number of large coordinates. Despite this shortcoming, I think the paper is still going to be of moderate interest to the theoretical community.\

Overall, the paper is clearly written and presents and contributions well within the landscape of the previous work.

Other comments:

-- Maybe I missed it but it might be useful to add some discussion regarding the optimality of the first term in the bound in Theorem 1.1, i.e. is this term required?

-- Enlarge images and font sizes in Figure 2

-- Experiments are done one small data (500 128x128 images) -- this is not very convincing for a big data paper.

-- Is MAPE the right metric for image compression?

review_title: A solid, but fairly incremental contribution

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper presents a new mapping of Euclidean vectors to bit vectors (quantization), along with a de-quantization method. The method is closely related to recent work by Huynh & Saab (2020), but instead of using a random rotation DBx on the input vector x, a sparse, Gaussian random projection is used. Under the assumption that the mass of x is "well spread out" this mapping also preserves Euclidean distances, but is quicker to compute (assuming random access to entries of x). After this mapping, a so-called Σ∆ quantization method is used, following Huynh & Saab.

The main issue I have with the paper is that there is no adequate comparison with quantization methods other than Σ∆ quantization. Notably, there is no comparison with product quantization (IEEE transactions on pattern analysis and machine intelligence, 2011). (Though it is presented as a data dependent method, it also makes sense as a data-independent method.) Also, LSH-based methods like simhash, and binarized E2LSH are not considered. It would also be helpful for the reader with a comparison to *data dependent* schemes, e.g. "Practical Data-Dependent Metric Compression with Provable Guarantees", NeurIPS 2017. Finally, there are related works in the theory literature that should probably be cited, e.g. "Optimal Compression of Approximate Inner Products and Dimension Reduction", FOCS 2017 (relevant for the case of normalized vectors).

Another claimed contribution, a speedup from O(n log n) to O(m) time, is not surprising (or new): It is known that for well spread vectors, even random sampling is an optimal dimension reduction method. (I think this goes back at least to Ailon and Chazelle.)

The writing can be made clearer. Even though I worked on related things, I found several parts of the paper hard to make sene of. For example:

- The abstract suggests that the results apply to all vectors that are not sparse, but in fact they apply only to vectors that satisfy a hard-to-satisfy L-infinity norm restriction.
- The abstract does not make clear that random access to the input vector is assumed, making it hard to understand how time less that O(n+m) is possible.
- Algorithms 1 and 2 in the introduction are impossible to understand without reading section 3 first. Maybe give a special case, with explicit details, and the general case later or in appendix?
- I suspect some assumption is missing in Theorem 1.1: The set of possible distances d_V(q_x,q_y) is finite, yet is supposed to be able to express the distance between arbitrary vectors x and y in R^n ...!
- The start of section 5 seems to imply that one can assume that vectors are well spread without loss of generality, by applying a random rotation. However, for random rotations the l-infinity norm will exceed the required norm by a factor sqrt(log n) with high probability.
- Is it important that L1 distance is used in algorithm 2, rather than L2 distance? After all, these distances are similar up to scaling for "spread out" vectors.
- Out of curiosity: Did you consider Kashin's representations of vectors?

review_title: Another binary embedding of Euclidean space, but inadequate comparison with existing methods

final_score: rating: 7: Good paper, accept
review_content: In this paper, the author proposed a fast, distant-preserving, binary embedding algorithm. This is in contrast with most binary embedding methods in mapping and recovery. Their method is fast and memory efficient, and accurate, so that the error is compared to that of a continuous valued Johnson-Lindenstrauss embedding plus a quantization error. In addition to theoretical results, the authors also test the proposed algorithm on nature images, showing strong performance of their method.

The strong points includes
+Proposing a new binary embedding algorithm
+Providing theoretical results of approximate error
+Empirical results supporting the superiority of the proposed method

The weak points includes
-Some parts not easy to follow
-Experiments could be remarkably improved

Overall, the technical part looks strong, but the presentation and experiment could be improved.

First, the introduction part is difficult to follow, since too many symbols are used in this paper while some of which are not explained at all. Besides, in Lemma 2.6, it is unclear where to use $s$.

Second, the proposed algorithm is tested on one real-world dataset based on distance reconstruction error, and compared with FJLT. It could be much convincing if more datasets, more metrics, and more baselines are considered. 
review_title: A new Algorithm with good theoretical guarantee, but the experiment is somewhat weak

final_score: rating: 6: Marginally above acceptance threshold
review_content: The paper studies binary embeddings that preserve Euclidean distances for the case when the vector mass is spread fairly evenly across the coordinates, which is a very common case in practice.

What the paper essentially does is a standard observation that uniform subsampling of coordinates (in spirit of Ailon -- Chazelle) of such dense vectors gives a Johnson--Lindenstrauss guarantee on the pairwise distances, and then it uses the quantization procedure developed earlier by Huynh and Saab.

To me the result sounds like a fairly straighforward ramification of the result of Huynh and Saab, but I can see it potentially being accepted, since the studied problem is extremely important.

I'm happy to revise the score if I got something wrong and the main resul is _not_ a straightforward variant of Huynh--Saab.
review_title: Seems to be a straightforward variant of the prior work, perhaps I'm missing something

Meta-review: The paper provides a new distance preserving embedding based on a recent result called sigma-delta quantization. The authors notice that in many realistic scenarios, the input vectors are well-spread and under assumptions regarding the spreadness provide a fast technique to convert the input vectors into binary vectors, possibly of lower dimension. For completeness, the authors analyze the setting where the vectors are not spread and show that by using a randomized Walsh-Hadamard transform, their results still apply.
The authors do not provide a completely novel approach, to quote R2 “On a technical level the results in this paper are hardly too surprising for the JL community, but it is nice to see this analysis worked out in detail”. That being said, they show that a natural idea indeed works out by providing both a theoretical analysis and experimental results. The experiments can be more thorough but do convey the point that the result indeed works and moreover is somewhat robust in that it works well even when the formal requirements do not entirely hold.
There are a few issues mentioned by the reviewers that should be addressed: A clearer exposition of the guarantees and assumptions, some comparison with previous papers. However given the responses and discussions these seem minor and fixable towards a camera ready version. I recommend accepting the paper

Decision: Accept (Poster)