A Rademacher-Like Random Embedding with Linear Complexity
Random Embedding;Randomized Singular Value Deomposition;Randomized Arnoldi Process;Machine Learning;Linear Complexity
Yes
No ethics review needed.
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.
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.
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)$.
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.
Yes
No ethics review needed.
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
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.
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.
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.
Yes
No ethics review needed.
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.
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.
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.
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.
Yes
No ethics review needed.
- 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.
The experimental results suggest that the authors’ methodology may have some promising applications in practice.
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.
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.
@inproceedings{
anonymous2024a,
title={A Rademacher-Like Random Embedding with Linear Complexity},
author={Anonymous},
booktitle={Submitted to The Thirteenth International Conference on Learning Representations},
year={2024},
url={https://openreview.net/forum?id=u0L7djBiRw},
note={under review}
}
Random embedding assumes an important role in representation learning. Gaussian embedding and Rademacher embedding are two widely used random embeddings. Although they usually enjoy numerical stability and effectiveness, their computational complexity is high, i.e. $O(nk)$ for embedding an $n$-dimensional vector into $k$-dimensional subspace. 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 stable Rademacher-like random embedding (RLE) is proposed. Specifically, it embeds an $n$-dimensional vector into $k$-dimensional subspace  in just $O(n)$ time and space (assuming $k \le n^{\frac{1}{2}}$). The theoretical analysis is presented, which indicates the proposed RLE owns most of desirable properties of the Rademacher embedding while preserving $O(n)$ complexity. In fact, the proposed RLE approach implicitly generates the Rademacher-like embedding matrix, based on novel random structures called buckets. This makes the random embedding accelerated without loss of stability. 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 even 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 random embeddings.
I certify that there is no URL (e.g., github page) that could be used to find authors’ identity.
I acknowledge that I and all co-authors of this work have read and commit to adhering to the ICLR Code of Ethics.
Random Embedding Randomized Singular Value Deomposition Randomized Arnoldi Process Machine Learning Linear Complexity
I certify that there is no acknowledgement section in this submission for double blind review.
/pdf/8d02993b4fc075023fc9595f04a1cad99f5a4c2d.pdf
unsupervised, self-supervised, semi-supervised, and supervised representation learning
I understand the reciprocal reviewing requirement as described on https://iclr.cc/Conferences/2025/CallForPapers. If none of the authors are registered as a reviewer, it may result in a desk rejection at the discretion of the program chairs. To request an exception, please complete this form at https://forms.gle/Huojr6VjkFxiQsUp6.
I certify that this submission complies with the submission instructions as described on https://iclr.cc/Conferences/2025/AuthorGuide.
A Rademacher-Like Random Embedding with Linear Complexity
ICLR 2025 Conference Submission
ICLR.cc/2025/Conference/Submission