A Rademacher-Like Random Embedding with Linear Complexity

Authors: Baiyu Chen, Wenjian Yu
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords: Random Embedding, Randomized Singular Value Deomposition, Randomized Arnoldi Process, Machine Learning, Linear Complexity

Abstract:
Random embedding assumes an important role in representation learning. Gaussian embedding and Rademacher embedding are two widely used random embeddings. Although they usually enjoy robustness and effectiveness, their computational complexity is high, i.e. $O(nk)$ for embedding an $n$-dimensional vector into $k$-dimensional space. The alternatives include partial subsampled randomized Hadamard (P-SRHT) embedding and sparse sign embedding, which are still not of linear complexity or cannot run efficiently in practical implementation. In this paper, a fast and robust Rademacher-like embedding (RLE) is proposed, based on a smaller Rademacher matrix and several auxiliary random arrays. Specifically, it embeds an $n$-dimensional vector into $k$-dimensional space  in just $O(n)$ time and space (assuming $k$ is not larger than $O(n^{\frac{1}{2}})$). Our theoretic analysis reveals that the proposed RLE owns most of desirable properties of the Rademacher embedding while preserving lower complexity. To validate the practical efficiency and effectiveness, the proposed RLE is applied to single-pass randomized singular value decomposition (single-pass RSVD) for streaming data, and the randomized Arnoldi process based on sketched ordinary least-squares. Numerical experiments show that, with the proposed RLE the single-pass RSVD achieves 1.7x speed-up on average while keeping same or better accuracy, and the randomized Arnodli process enables a randomized GMRES algorithm running 1.3x faster on average for solving $Ax=b$ than that based on other  embeddings.

Decision: reject
Reviewer scores: 3, 5, 5, 1

Reviews and discussion:
<thread>
creation date:
1730005424912

thread_type:
official_review

<thread_object>
creator: reviewer_86dx

<content>
summary:
This work considers the construction of structured random projections which can be applied very quickly to a vector for the purpose of solving least squares linear regression and quickly computing Arnoldi iterations for SVD. The construction of the random projection involves some combination of hashing into buckets and random signs, which are classic ideas in this literature. Experiments show that the proposed method offers faster application and lower approximation error than Gaussian embeddings and sparse embeddings.

strengths:
The experimental results suggest that the authors’ methodology may have some promising applications in practice.

weaknesses:
The theoretical analysis of the proposed random embedding only analyzes the expected squared norm of the embedding, and provides no insight into how the dimension $k$ of the embedding should scale with respect to the desired error level, success probability, or the space of vectors which are being preserved. Usually, these random embeddings have guarantees of the form “if the dimension $k$ is at least […], then the random map $S$ preserves the $\ell_2$ norm of all vectors $x$ in a set $X$ up to a factor of $(1+\epsilon)$ with probability at least $1-\delta$“ (see, e.g., Woodruff 2014).

Furthermore, this paper is missing important comparisons to prior work that is highly related to the ideas described in this paper. For example, CountSketch is a related construction which uses hashing and random signs that have applications to quickly solving low rank approximation and linear regression https://arxiv.org/abs/1207.6365. 

The presentation is also quite poor, and I could not follow the precise definition of the proposed random embedding in Section 3.2.

questions:
- Why do you specifically consider Arnoldi iterations for sketching SVD? There are many other methods for using sketching ideas in the context of low rank approximation: see, e.g., https://arxiv.org/abs/1207.6365 and https://arxiv.org/abs/1504.05477
- How do you choose the value of $k$ in your experiments? Your theorems don’t provide insight into how this parameter should be chosen.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730210593743

thread_type:
official_review

<thread_object>
creator: reviewer_paok

<content>
summary:
The paper points out an interesting property of the Rademacher matrix: each pair of its rows has half of the column coordinates sharing the same sign, and the other half sharing different signs. This characteristic enables random embedding to efficiently compute only one row, with the result for the other row being readily inferable from the sign information.  To explicitly  determine the column coordinates sharing the same (and different) signs, the paper introduces a special matrix generation method, which allows random embedding implemented in linear complexity.

strengths:
Compared to the original Rademacher matrix-based embedding, the proposed embedding method reduces computational costs, without accuracy loss on the RSVD and the randomized Arnoldi process.

weaknesses:
1) The proposed matrix generation method is not easy to understand, as the presentation in section 3.2 lacks clarity and precision. Several crucial terms and symbols, such as "inner bucket," $w$, $ζ$, and $ k’$, remain undefined or unexplained. This section requires substantial improvement prior to publication.

2) The complexity (and stability) of the proposed matrix should heavily depend on several key parameters outlined in Algorithm 3, including $ξ$, $ζ$, $ω$, and $k’$. Regrettably, this relationship has been neglected, resulting in a theoretical shortcoming in the paper.

questions:
1)  In the theoretical aspect, the authors focus on deriving the property of $E(\||y\||^2)=E(\||x\||^2)$  in Theorem 2. However, within the field of random embedding/projection, this property is already recognized as being applicable to random matrices with zero mean and unit variance. For details, see the reference:  Dimitris Achlioptas. 2001. Database-friendly random projections. In Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS '01).

2) Line 396: The authors emphasize that the generated matrix is Rademacher-**like**. What distinguishes it from a traditional Rademacher matrix in mathematics? Both matrices take the values of $\pm 1$ with equal probabilities, appearing identical in this respect.

3) By the proposed method, how many rows can we potentially derive their values after computing just *one* row？ I think  this should be closely tied  to the parameters $ξ$, $ζ$, $ω$, and $k’$.  It is crucial to elucidate their relationships both  theoretically and practically.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730217925947

thread_type:
official_review

<thread_object>
creator: reviewer_aqrb

<content>
summary:
To reduce the complexity of the traditional Rademacher random embedding, this paper proposes a fast and stable Rademacher-like random embedding (RLE) that reduces the complexity from $O(kn)$ to $O(n)$ in time and space. Numerical experiments show that RLE enhances the efficiency and accuracy of single-pass randomized singular value decomposition (RSVD) and randomized Arnoldi process.

strengths:
This study introduces a novel and interesting approach to reduce the complexity of  Rademacher  embedding, by exploring the inherent correlations between the rows of random Rademacher  matrices.

weaknesses:
1)  The proposed method for matrix generation  is interesting, yet challenging to grasp due to its current presentation lacking of of vital details. As I see it, the authors intend to identify column indexes that share the same and distinct signs across **two** (or **more**?) rows during matrix generation. If the focus is solely on **two** rows, the proposed method  is **not** a necessity. Instead, we can simply generate a Rademacher matrix, and subsequently divide  its rows to  pairs. The column sign differences between each pair of rows can  then be easily identified.




2) Throughout the paper, the authors consistently stress the importance of the **stability** of random embedding matrices, which should be reflected in  the variance $Var(\||y|\|)$ given that  $E(\||y\||)=E(\||x\||)$. Nevertheless,  the variance  $Var(\||y|\|)$ is not explored in the paper. The authors restrict their attention to proving   $E(\||y\||)=E(\||x\||)$, a property already known  to hold for the random matrices with elements distributed symmetrically about zero.

questions:
1) The method described in Section 3.2 is unclear and ambiguous, as it lacks detailed descriptions for the crucial parameters $\xi$, $\zeta$,  $k'$ and  $\omega$. For easier understanding, the introduction of the method  should be accompanied with the example illustrated in Figure 1. Furthermore, the example  needs to be modified to explicitly depict the relationships among  $\xi$, $\zeta$,  $k'$ and  $\omega$. 

2) It is unclear how to determine the optimal values of $\xi$, $\zeta$,  $k'$ and $\omega$. To tackle this issue, it is suggested to investigate  the effects of these parameters on the complexity and stability of the Rademacher-Like random embedding.

3) The proposed matrix achieves linear complexity $O(n)$  when $k<\sqrt{n}$, which is equivalent to a compression ratio $k/n<1/\sqrt{n}$.  This condition implies that the  method is only applicable in cases of very low compression ratios, i.e. $k/n=1/100$ for $n=10000$. However, random embedding typically performs poorly in these scenarios due to significant information loss and instability. In summary, the condition  $k<\sqrt{n}$ may restrict the practical application of the proposed method.

4) It appears that the proposed method does not support parallel computation, given its row-by-row operation mechanism.




There are many minor errors in the paper, and here is a small selection of them.

Line 112: the dimensions of $x$ and $\theta$ 

Line 158: the sketching process of ?

Line 230: two row of $y$

Line 250: the term “inner buckets” emerges without definition.

Line 254: in each outer buckets



Line: 262: each entries



Line 633: theoretical result

Line 779: outer 2 buckets
</content>
</thread_object>

</thread>
<thread>
creation date:
1730565384860

thread_type:
official_review

<thread_object>
creator: reviewer_qhmq

<content>
summary:
The authors have proposed a novel random projection algorithm from a $n$-dimensional vector to $k$-dimensional vector, where the implicitly implemented random projection matrix is Rademacher-like in the sense that each entry is in $\\{-1, +1\\}$ and its computational complexity is $O(n+k^2)$, not $O(nk)$.

strengths:
1. The explanation of the background and motivation of the area is clear. It is designed so that even readers not in the random embedding can understand the motivation. 
2. The novelty and significance of the proposed method are also clearly presented.
3. Non-triviality is not necessary for machine learning papers in general. Having said that, it is notable that one would not easily come up with the essence of the trick used in this paper to avoid explicit matrix multiplication operations. Hence, this paper has the potential to be an essential building block of future innovative papers.
4. The base idea of avoiding explicit random matrix generation to avoid $O(nk)$ complexity is intuitively explained in Section 3.1. This helps readers understand the non-trivial phenomenon achieved by the proposed algorithm.
5. The numerical experiments have successfully shown that what the proposed algorithm sacrificed is not practically problematic.

weaknesses:
Overall, most parts of the paper are excellent, but the core explanation of the algorithm could be refined, which is the main reason for my current low score.
1. Section 3.2. did not make sense to me. Possible reasons are that words like "inner buckets" or "outer buckets" do not help intuitive understanding. If there is no analogue between the algorithm and the daily usage of the buckets, it would rather be better to use specific mathematical symbols instead. Specifically, it would be better to explain each operation in Section 3.2. using symbols appearing in Algorithms 3 and 4, e.g., $R,C,P,E$ or entries in those matrices.
2. I could not understand Figure 1, either. A possible reason is that readers cannot understand from figures what each ball or curve connecting two balls means. I encourage the Authors to explain the algorithm using specific numerical examples instead of Figure 1.
3. The current manuscript does not clarify what the proposed algorithm sacrifices. If I understand it correctly, the entries in an implicit project matrix generated by the proposed algorithm are pairwisely independent but not mutually independent, while the entries in a naive Rademacher projection matrix are always mutually independent. Clarifying this sacrifice (perhaps as a limitation) must benefit readers. At least it helps readers understand why the proposed embedding is called "Rademacher-**like**," not "Rademacher." If the proposed algorithm did not sacrifice anything theoretically from naive Rademacher random projection, numerical experiments would not be needed. 
4. The Authors emphasise that the proposed algorithm is "linear". This is not ideal, since naive Rademacher random embedding is also linear with respect to each of $n$ or $k$. My brain cannot come up with a better natural language word, but you might want to emphasize the mathematical difference between $O(nk)$ and $O(n+k^2)$. At least, the expression of $O(n+k^2)$ should appear somewhere.
5. Most parts of the mathematical explanation in the paper are clear, but the lack of the definition of $d$ makes Section 2.1 hard to understand.

Typos:
- $x \\in \\mathbb{R}$ -> $x \\in \\mathbb{R}^n$ in line 112.

---
**After discussion period**:
In the discussion with Reviewer 86Dx, we have found that the current proof of Theorem 6 uses mutual independence while it is not the case in the proposed Rademacher-like representations. Regrettably, I have lowered the score.

questions:
1. Could you clarify the definition of $d$?
2. Could you explain each step of the algorithm using specific numeric examples and associate each step with entries in $R, C, P, E$? The unclarity of this part is the main reason for the current low score.
3. Comment: Theorem 3 states that entries in $\\Theta$ are pairwisely independent. We should leave the current expression of Theorem 3 also since readers might not know the phrase "pairwise independent," but including the phrase "pairwise independent" would help you clarify what the proposed algorithm sacrifices compared to the naive Rademacher random embedding, whose projection matrix's entries are mutually independent, not only pairwise independent.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732508655780

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
First of all, We sincerely thank all reviewers for their helpful comments. With the help of those comments, we have done **a major revision** on our manuscript and we believe our manuscript has been greatly improved. All modifications in the original manuscript are marked in ``BLUE``. The modifications can be summarized as follows.

1. We have replaced most expressions of linear complexity or $O(n)$ in the paper with $O(n+k^2)$ complexity, because the latter is a more rigorous presentation. We also emphasize that if $k$ is not large than $O(\sqrt{n})$, it is just $O(n)$ complexity.

2. We have rewritten Section 3.2 to better explain the proposed Rademarcher-like embedding (RLE) approach, with a new Figure 1 replacing the old one. Figure 1 is served as an example for explaining RLE. This explanation is closely based on the algorithm for the execution phase of RLE, and discards the vague expressions of buckets and random sequences. Due to the limit of space, Alg. 3 (for the setup phase) and Lemma 1 (which is less relevant) in the original paper are removed. The setup phase is straightforward, and is now explained by the second to last paragraph of Section 3.2.




3. Theoretical analysis on the proposed RLE is reorganized and largely modified in Section 3.2. Now there are six theorems, where Theorem 3 extends that in the original paper and Theorem 6 on the oblivious subspace embedding bound is totally new.


4. An ablation study on the three parameters ($\xi, \zeta, \omega$) is added with the results presented by Fig. 5 in Appendix A.4.
And, a discussion on how to parallelize RLE is presented at the end of the main text.


5. The Appendix is also reorganized, with irrelevant content removed and new contents like the proof of Theorem 6 and result of  ablation study added.


6. Finally, 4 references are added, and the whole manuscript is carefully proofread.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper aims to develop theoretical guarantees for random projection where the projection matrix moves away from Rademacher. Authors proposed an approach that reduces the computational time while almost preserving approximation guarantees.

Reviewers agree that this work is interesting, and the generalization beyond Rademacher is important.

However, reviewers also found that the paper requires a major revision to improve the presentation, and that some theoretical results are questionable.