The Sparse Matrix-Based Random Projection:  A Study of Binary and Ternary Quantization
Authors: Weizhi Lu
Zhongzheng Li
Mingrui Chen
Weiyu Li
Venue: Accepted by TMLR ()

Abstract: Random projection is a simple yet  effective technique for dimension reduction,  widely used in various machine learning tasks. Following the projection step, quantization is often  applied to  further reduce the complexity of  projected data. In general, quantized projections are expected to approximately preserve the pairwise distances between the original  data points, to avoid significant performance degradation in subsequent tasks.  While this distance preservation property has been investigated for  Gaussian matrices,  our work further extends the analysis to hardware-friendly $\{0,1\}$-binary matrices, particularly focusing on cases where the projections are quantized into   two types of low bit-width codes: $\{0,1\}$-binary codes  and $\{0,\pm1\}$-ternary codes. It is found that  the distance preservation property tends to be better maintained, when the binary projection matrices exhibit sparse structures. This  is validated through classification and clustering  experiments, where extremely sparse binary matrices, with only one nonzero entry per column, achieve superior or comparable  performance   to other denser binary matrices and Gaussian matrices. This presents an opportunity to significantly reduce the computational and storage complexity of the quantized random projection model, without compromising, and potentially even improving its  performance.

Published in Transactions on Machine Learning Research (02/2025)
The Sparse Matrix-Based Random Projection: A Study of Binary and Ternary Quantization
Weizhi Lu
waku@sdu. edu.
School of Control Science and Engineering, Shandong University Key Laboratory of Machine Intelligence and System Control, Ministry of Education
Zhongzheng Li
lkchonghhnng@mmiilsdh.. edu.cn
School of Control Science and Engineering, Shandong University
Mingrui Chen
mrchen&@miiledde edu.ccm
School of Control Science and Engineering, Shandong University
Weiyu Li
liwesyy Bertiiyu@sdd..mmm edu.cc
Zhongtai Securities Institule for Financial Studies, Shandong University
National Center for Applied Mathematics in Shandong
Reviewed on OpenReview: https: // openreview. net/ pdfp id= dJJmJJbbhM
Abstract
Random projection is a simple yet effective technique for dimension reduction, widely used in various machine learning tasks. Following the projection step, quantization is often applied to further reduce the complexity of projected data. In general, quantized projections pected to approxinately preserve the pairwise distances between the original data points, to avoid significant performance degradation in subsequent tasks. While this distance preser- vation property has been investigated for Gaussian matrices, our work further extends the analysis to hardware- hardware-friendly {0, 1ibbinary matrices, particularly focusing on cases where the projections are quantized into two types of low bit-width codes: {0, 1}-binary codes and {0, -te-renarry codes. It is found that the distance preservation property tends be better maintained, when the binary projection matrices exhibit sparse structures. This is validated through classification and clustering experiments, where extremely sparse binary matricos, with only one nonzero entry per column, achieve superior or comparable perfor- mance to other denser binary matrices and Gaussian matrices. This presents an opportunity to significantly reduce the computational and storage complexity of the quantized random projection model, without compromising, and potentially even improving its performance.
ex-
1 Introduction
Random projection is an unsupervised dimension reduction technique (Johnson & Lindenstrauss 1984) that involves projecting a high-dimensional data vector R. to lower dimension via linear projection
Rx,
(1)
where E m is a random matrix, m < n. For random matrices following Gaussian distributions (aas-
gupta Gupta 1999). sparse {0, -dittttibbbisss (Achlioptas) 2003) and {0, 1}-distributions (Dasgupta et al. 2017 Li & Zhang 2022,, it has been proved that the distance between any two original data points can be approximately preserved with high probability by their projections x'. This property of maintain- ing pairwise distances ensures the approxinate preservation of the original data structure, making random projection widely applicable in various machine learning tasks without compromising significant performance.
*Corresoondngg author.

---

Published in Transactions on Machine Learning Research (02/2025)
To further reduce the complexity of random projections, it is common practice to apply an element-wiss quantization operation f(x'), such as the widely-used (0,1aabi or --. quantization, to the projection z' of original data z. This results in a quantized random projection model, which finds applica- tions in various domains like the large-scale retricval [Charikar 2002) and doep network quantization (Wan et al. 2018: Qin el a 2020). For the effective application of quantized random projection models, the major concern remains on the prescrvation of pairwise distances. Specifically, provided two data points u, v E R" along with their projections v', o' R", one needs to identify a random matrix R E R=** that = ||u e or equivalently f(u') u uJv for normalized data, with high probability. While this distance preservation property f(u') f(v') = uTT has been studied for Gaussian matrices [Charikar 2002 Li et al. 2014), it has not been explored for sparse {0, + - or {0, 1 J-binaary matrices. In iraclice, however, sparse matrices are favored due to their simpler structures. To simplify the structure of sparse matrices, there is considerable interest in estimating their sparsest form, specifically the minimum number of nonzero entrics needed, while maintaining the distance preservation property described earlier. This presents discrete optimization problem, which seems challenging to address using the proba- bility analysis method commonly employed for Gaussian matrices. In the paper, we demonstrate that this problem can be effectively tackled, if the data for projection exhibit sparse distributions.
holds the relation of
Sparse distributions in data are commonly encountered in signal processing and machine learning. For in- stance, it is well-known that natural data, such as images and sounds, usmally contain coherent structures and redundant information over spatial or time domains (Ruderman] 1994 Simoncelli 1999: Weiss & Free- man 2007; Kotz et al.) 2012 Iyer & Burge 2019 and thus allow to be sparsified via globally or locally linear transforms, such as the discrete cosine transform (DCT) (Rao & Yip 2014 Fude et al., 1994), the dis- crete wavelet transform (DWT) (Mallat) 2009), the deep convolutional neural networks (CNN) (Krizhevsky et al. 2012), and so on. In general, these sparse transforms will provide more discriminative features for classification, especially when zeroing out the mmall-mag feature elements caused by high-frequency noise (Zarka et al.) 2020). Furthermore, the feature discrimination could be improved further, as the re- maining large feature elements are quantized to the values of 11 or 1 through appropriate ternary or binary quantization (Lu et al. 2023). This suggests that employing low bit-width binary and ternary quantization on sparse features is advantageous for classification in terms of both complexity and accuracy. Then for the quantized random projection of sparse features, instcad of the conventional distance preservation property of (w')T [(v') u v. we propose to investigate the properly of s(u') [(v') = I (v), i.e. preserving the distance between the quantization codes fu) of sparse features u, in order to allow the quantized projections f(u') to obtain more discriminative features from the quantized original data f(u).
With the quantized sparse features as input, the random projection model is somewhat similar to the com- pressod sensing model (Donoho, 2006). Inspired by the analysis of the sparse {0, 1]-binary matrix-basod compressed sensing (Mendoza-Smit, & Tanner, 2017 Lu et al. 2018), in the paper we investigate the pro- posed distance preservation property f(a') f(e)= f (w)f(e) for the sparse binary matrix-based random projection. By varying the matrix sparsity, we observe that the property tends to be better satisfied by extremely sparse matrices containing only one nonzero entry per column, compared to other denser matri- ces. As expected, theses extremely sparse matrices also perform better in both supervised and unsupervised learning tasks, specifically classification and clustering. This property is highly attractive for random pro- jection in terms of both complexity and accuracy. Overall, the major contributions of the paper can be summarized as follows.
For the binary matrix-based random projection, we for the first time study the impact of matrix sparsity on the performance of ternary (and binary) quantized projections in the conventional clas- sification and clustering tasks. It is found that extremely sparse binary matrices that contain only one nonzero entry per column tend to outperform other denser matrices, when the original data for projection consist of nomdonly-nsod sparse features, such as DWT and CNN features derived from the well-known datasets like YaleB (Georghiades et al. 2001 Tee el al. 2005), CIFAR10 (Krishevsky & Hinton 2009) and ImageNet (Deng et al. 2009).
To estimate the optimal matrix sparsity, we investigate how accurately the ternary (and binary) quantized projection can preserve the pairwise distance between the ternary (and binary) quanti-
2

---

Published in Transactions on Machine Learning Research (02/2025)
zation of original data, rather than directly between the original data conventionally studied. Compared to the conventional distance preservation property, our proposed property offers two key advantages. First, it allows the quantized projection to obtain more discriminative features from the original data, which are the sparse features as previonsly mentioned. Second, it facilitates casier analysis for the quantized, binary matrix-based random projection model, whereas the conventional distance preservation property poses greater challenges.
The rest of the paper is organized as follows. In the next section, we review the literature related to the quantized random projection model. In Section 3 we introduce the basic knowledge about the model and describe the proposed distance preservation property. Among the binary matrices with different sparsity, the one that better holds the proposed property is estimated Section [ The performance advantage of such matrix in classification and clustering is verified in Scction Section concludes the work.
2 Related work
The quantized random projection model has been studied in two research areas: local similarity hashing (LSH) [Charikar 2002 Boufounos & Rane 2013 Valsesia & Magli 2016) and compressed sensing (Jacques et al. 2013). The former aims to adopt quantized projections to build hash tables for information retrieval, and the latter aims to reconstruct original data from iuedtized projections. Different from our work, both of them, broadly speaking, require the quantized projection f(x') to preserve the pairwise distance (or sim- ilarity) between original data I, rather than between their quantization versions f(x). Furthermore, their studies are mainly focused on Gaussian matrices. For the classification on quantized projections, a system- atic evaluation has been presented in (Li al. 22014), which demonstrates that compared to unquantized projections, a slight performance reduction inclines be caused by 2-bit quantization, and the reduction becomes noticeable for 1-bit quantization. Recent empirical studies have demonstrated that the binary and ternary quantization can improve classification accuracy, when applied to commonly-used sparse features [Lu et al. 2023). Morcover, when classifying quantized projections of sparse fcatures, random projections based on extremely sparse (0, #1,#1)-matrid generally outperform those based on Gaussian matrices. This remarkable performance motivates us to conduct a thorough theoretical analysis to explore the impact of sparse matrices on the classífication of quantized projections.
For random projections based on sparse matrices, like {0, 1 matrices and (0, 1) 1)-binary matrices, existing research mainly explores the distance preservation property for the linear model ( without quan- tization considered. Specifically, the l distance preservation property of ternary matrices has been studied in [Li et al. 2006), which demonstrates that the property can be well satisfied when the matrix has the proportion of nonzero entries greater than 1/ In (Daguupta et al. 2017), the f2 distance preservation is analyzed for binary matrices, and empirically the matrices tend to reach a stable performance for nearest neighbors search when containing more than about 10% nonzero entries. In contrast, our study demon- strates that for the quantized projections of sparse features, binary matrices can generally achieve the best classification performance when containing only one nonzero entry per column.
3 Problem Formulation
In the paper, we study the random projection model ( which has the original data R" sparsely distributed and has the random matrix R E (0, 1)mxn binary distributed. To improve the classification on the quantization of projected data, we present a novel distance preservation property that maintains the pairwise distance between the quantization of original data, rather than between the original data themselves, and then investigate the probability that the property holds for the binary matrix with varying matrix sparsity. In this section we provide the basic knowledge about the study, including the distribution of binary matrices R, the distribution of original data x, the quantization functions f(-), as well as the distance preservation property.
3

---

Published in Transactions on Machine Learning Research (02/2025)
3.1 Binary matrices
For a random binary matrix R E {0, 1jmx,, we assume it contains d (< m) nonzero entries per columm, or say having column degree d. This parameter measures the matrix sparsity, whose impact on distance preservation will be the core of our rescarch. We denote Ra, E R as the entry at the i-th row and j-th column, R E R" the j-th column vector, R, E g the i-th row vector, R E Rixiøl the intersection of the i-th row and the columns indexed by & C [n], [m] := (1.2...,,)) and R. E RRmx dl the set of the columns indexed by Φ. Moreover, inspired by the analysis of the binary matrix-based compressed sensing (Donoho, 2006), in Definition | we model the adjacency relation between the binary matrix's rows and columns, which corresponds to the mapping relation between the coordinates of original data and projected data a'. The relation will be explored in the following distance preservation analysis.
Definition 1 (Adjacency relation between the binary matrix's rows and columns).. Consider the binary matrix R& E {0, 1jmxn with its columns and rows indexed by the variables j and i, respectively. For the matrix's j-th column, define its adjacent row set as NNi) = {i: Rag * 0, E [m]]; and subsequently, for a subset of the columns J C [nl, define its adjacent row set as (N)) = (U, NG).j E [J]]. Similarly, for the matrix's i-th row, define its adjacent column set as Mii) = [j Ra, + 0.j [n]]. Notice that the matrix's columns and rows correspond respectively to the element coordinates of the original data and projected data x', and so the adjacency relation defined above can be used to describe the mapping relation between the coordinates of the two kinds of data.
3.2 Original data
The analysis of the quantized random projection is related to the distribution of the original data x (21, ;I,) E RR. In the paper, we propose to study the data with approximately sparse exactly sparse distributions, as specified in Definitions aand
Definition 2 (Approximately sparse data). A data vector x E RR is called approximately sparse, if its element--maguituul--ree
version x' = (oi, xx)) follows an exponential decay relation: |01+1//|=|1 s e -8 where 3 is an arbitrary positive constant; and the larger the value of 3, the faster the decaying speed.
Definition 3 (Exactly sparse data). A data veclor æ E R is called k sparse, or having sparsity k, if it contains exactly (< n)) nonzero entries, or say having the support size (supp(z) = k, supp(z) = {i :2: # 0,1 E [n]].
The approximately sparse data are prevalent in various classification tasks, such as the features ex extracted with DCT, DWT, CNN and so on. It is known that these features have approximately sparse distributions, and can be modeled with exponential decay functions (Weiss & Freeman, 2007 Kotz al., 2012). Moreover, they can be further transformed to exactly sparse structures by zeroing out the elements of small magnitude. Compared to approximately sparse structures, exactly sparse structures have three advantages. First, it can reduce the computation complexity of the downstream random projection operation. Second, as studied in [Lu et al.) )023), it tends to improve feature discrimination, favorable for classification. Third, as detailed later, is easier to analyze due to ils simpler distributions, and allows us to simply set the projection's 's quantization threshold to a constant value, zero, to achieve the desired performance. Therefore, in the final experiments we will pay more attention to the performance of exactly sparse features.
3.3 Quantization functions
We investigate two fundamental, element- wise quantization operations: the binary and ternary quantization. The lernary quantization is formulated
+
>
fx1)
-
1,
Fi -
(2)
0,
others
where the threshold parameter 5 2 empirically determined to regulate the sparsity of the quantization (+( for the vector "R. We treat f+(+) as an element-wise function and express the vector's quantization
4

---

Published in Transactions on Machine Learning Research (02/2025)
f+(x)= - (f (xx))) Similarly, the {0, 1--bnarry quantization can be formulated using single threshold parameter т. For brevity, the following analysis will focus on ternary quantization, but the results can be easily extended to binary quantization.
3.4 Distance preservation property
Consider the random projection model I which has two original data E R" and corresponding projections v', v' E R".. We aim to determine the distribution of the binary matrix R that holds the following distance preservation property
=a (a (1)
(3)
with high probability, where is positive constant, and the threshold parameters T; of the quantization functions f(-) will be determined by analysis. Notice that for the convenience of analysis, the parameter is introduced to define relative distance preservation, whose value varying does not affect the classification of projected data; and the exact distance preservation namely the case of a = 1, can be easily obtained by scaling the element values of random matrices.
Different from the traditional quantized random projection model that requires preserving the distance between two original data and v, our proposed distance preservation model (3) maintains the distance between the two original data's quantization codes, fr, (u) and (v). This proposal is inspired by the recent finding (Lu et al. 2023) that the quantization of sparse features (i.e. our original data) can produce more discriminative features for classification. Then compared to the conventional distance preservation, the proposed distance preservation 3 allows the projection to capture more discriminative features of the original data; and moreover, the proposed method easier to analyze, since its quantization operations simplify the modcling of data distributions.
4 Distance preservation analysis
For the projection matrix E {0, 1)mxn with varying column degree in this section we estimate the
optimal column degree d that ensures the proposed distance preservation property (3) holding with high probability. For ease of analysis, we first describe the desired matrix structure that holds the property (3) for two given data x E R", and then derive the probability that the desired matrix structure holds for two arbitrary data & E R", The analysis results are presented in Theorems 3 with comprehensive proofs outlined in Appendices A.3 For brevity, we mainly analyze the ternary quantized projections (x"),
and the analysis can be straightforwardly extended the binary case.
4.1 Distance preservation for two given data
Given two original data points u, v E IR" with deterministic structures, we evaluate the distance preserva- tion property in Theorems D and respectively for two different data distributions: exactly sparse and approximately sparse, specified in Definitions 3 and 2 On the whole, both theorems demonstrate that the proposed distance preservation property 3 will be achieved, if the submatrix R.,s of the binary matrix R, indexed by the support union of the two quantization codes fr, (u) and fr. (v) corresponding to the two original data points, has orthogonal columns. The details are discussed in their respective remarks.
Theorem (Exactly sparse data). Consider the random projection model [ which has two projected data u', vf e _ generated from two exactly sparse data u, u E R" with sparsity k1, h2s provided a random matrix R (0, 1]mxx with column degree (< m). Let & supp(u) U supp(v), then [ø] S k h2. If R R..s d[ where [ooi denotes the identity matrix of size (0), we have
so(u') So(v') d fo(u) fn()),
(4)
where fo(-) is the ternary quantization function 2 with parameter T == 0.
Remark of Theorem 1. For the theorem, there are several noteworthy points. (i) The orthogonal R., required by the theorem will be obtained, as the support union size of two original data is less than the
5

---

Published in Transactions on Machine Learning Research (02/2025)
matrix's row size, that is |0| & m. With given column degree d, statistically, the orthogonal Rx,0 is more likely to be obtained when its row size m is large, and the column size is small, corresponding to lower data sparsity kG (ii) Exactly sparse data with small sparsity K can be obtained by zeroing out the small- magnitude clements of sparse features. As previously mentioned, this sparsifying operation can improve Teature discrimination, beneficial for classification (Lu et al. 2023). (iii) The four lernary functions in ① all simply fix their threshold parameter to need of parameter tuning. (iv) Since the sparsity of exactly sparse data remains unchanged after ternary or binary quantization,
for both the original data and projected data, climinating the
can directly use their quantization codes for projection, without affecting the final projection results (4). This suggests that Theorem [ holds for the random projection model where both the original data and projected data are quantized into ternary or binary codes.
Theorem 2 (Approximatcly sparse data). Consider the random projection model which has two projected data w', v' E IR" generated from two approximately sparse data u, v E IR", provided a ran- dom matrix R. {0. 13 1mmxn with column degree d. For u and v, assigning two ternary functions f+) with T1 [ui, +2! and T = T2 1ig +1 respectively, such that supp(fr. (u)) k1 and supp(S>, (v)) k2, where ot, denotes the ki-th largest element of in magnitude and v%, is defined sim- ilarly. Let Φ = supp (J= (u)) U su)p(s=-())), then (0) S ki + k2- If R. Ras = dl and u, v have their decaying parameter 2 In(2 + v3), we can derive that
2
2
(ra(0) d fr
(u) fz(().
Remark of Theorem 2 (i) The results we have derived for approximately sparse data are similar to those obtained for exactly sparse data by Theorem D One of major differences between them is the choice of the threshold parameter for ternary functions. As discussed in Section 3.4 we need to select proper T to produce data sparsity k that can improve feature discrimination when transforming to J (u), thus leading to better classification performance. As shown in (Lu et al. 2023), the desired sparsity l can be empirically determined. Without loss of generality, we assume two different sparsity values ki, k2 (corresponding to and 72) for the two original data points u, V, in order to obtain the desired quantization performance. In practical applications, for simplicity, we suggest to select a same sparsity i for the two data, since they are generally obtained from the same scene and share similar distributions. (ii) Moreover, it is worth noting that besides the orthogonal constraint on the submatrix R., the derivation of (5) also imposes constraint on the distribution of the original sparse data: the data should have its decaying parameter 3 2 In(2 + v3), and roughly speaking, the data needs to decay sufficiently fast. Notice that the lower bound for B is a sufficient but not necessary condition, and empirically our optimal matrix estimation is not sensitive to the lower bound of B and tends to achieve the desired classification performance even for the sparse features with smaller 3.
4.2 Distance preservation for two arbitrary data
To generalize the distance preservation property (3) from two fixed data to arbitrary data, we should extend the condition of orthogonal Re,s from a fixed column set supp (fr, (u)) U (u)p(f) to an arbitrary set & C [n], |6| k + l/2 < m. For a randomly generated binary matrix R E 10,1) jmmx,, however, it is hard
to ensure its cach submatrix R. to have orthogonal columns. In Theorem we analyze the probability of having orthogonal R.,s under the varying column degree d.
Theorem 3. Given a random matrix R E {0, mmx with column degree d. Consider its submatrix R. with ø C [n]. Denote Pr. = d'lo) } as the probability that R Ba,s = d4|0 holds for any & C [m].
with |6] 2 2 and d|ø) < m. Provided m and o, we have the probability
[Im d)!](=1
Pr( Rr dl
(6)
(ml) lold)
101-1 (m -
1=0
(7)
ml
which has the value of 6 monotonically decreasing with the column degree d, and has the equality of attained at d =
7
6

---

Published in Transactions on Machine Learning Research (02/2025)
DC TO DIATO
101
BN-4
k/m
0.01%, m/n 10%
(b) k/n 0.1%, m/n 10%
(c) k/n 1%, m/n 10%
(d) k/n 10% m/n 10%
DM/70
-0-03-T0
-0- GM
BM-
(e) k/nn = 0.01%, m/n ha= = 50%
(1) k/nn = 0.1%, m/n 50%
(g) h/n = 1%, m/n 50%
(h) k/n = 10%, m/n /n 50%
Figure 1: Distance variation rate for the ternaay--uantized (TQ) (and non-quantized) projections the generated data, with four different feature spansity ratios k/n 0.01%, 0.1%, 1% and 10%, using two projection matrices: the Gaussian matrix (GM) and the binary matrix (BM) with varying column degree BM-d C [1, 10), under two projection ratios m/n 10% and 50%. Note the smaller the distance variation rate, the better the distance preservation.
Remark of Theorem 3. (i) The theorem demonstrates that the probability (6) of having orthogonal R. will increase with the decreasing of column degree d. It suggests that the distance preservation property should be satisfied with higher probability by the binary matrix with smaller column degree d. Then it is reasonable to conjecture that when applied to the common classification or clustering tasks, quantized projections can achieve the best performance with very sparse binary matrices, i.e. the ones with column degree as small as = 1, as verified our experiments. (ii) Morcover, it is worth noting that besides the column degree d, the probability (6) is also related to the size of ø. For the probability derived with d = 1 in 7 easy to see that the smaller the |o| value, the higher the probability. This means that the sparser features I (with smaller sparsity k) should result in the better distance preservation property (3 This relation is similar to the condition of compressed sensing [Donoho 2006
4.3 Extension to binary quantization
In Theorems 1 and 2 only investigate the ternary quantization (2) for the distance preservation property From the proofs of the two thcorems, it can be seen that their results can be directly extended to the case of binary quantization, with the same threshold values тæ. Then by Theorem 3 we can predict that the binary quantization of projected data will achieve its best classification performance when using very sparse binary matricos. This verified in our experiments. In the paper, we pay more attention to ternary quantization than to binary quantization, the latter generally performs worse due discarding more feature elements [Lu et al. 2023
4.4 Numerical validation
In this part, aim to validate the main result of Theorem 3 that is the proposed distance preservation property 3 should be satisfied with higher probability by binary matrices with smaller column degrees d, when the sparsity k of the quantization (x) of original data x is sufficiently small, as required in Theorems and 2 For this purpose, we directly investigate the distance variation before and after random projections through numerical simulation. Based on the distance preservation property (3), we introduce the concept of the distance variation rote, which quantifies the relative change in pairwise distance between quantized projected data compared to the distance between quantized original data. Specifically, it is defined
N (u(00)))) (r,0000) - Il.r,, (u(i) fro (v(0))2 1| (u(()) fr (o(0))12
(8)

---

Published in Transactions on Machine Learning Research (02/2025)
where ul), a00) R" are a pair of original data points, 1 1 i S N, and aty, v00 E R are their projections over random matrix R E [0, with column degree d. Note that all the quantized data (+((+) in ( are pre-normalized using l2 norm, in order to eliminate the magnitude discrepancy between before and after random projections. It is evident that the smaller the distance variation rate (8), the better the distance preservation property (3).
By Theorems D and 2 given column degree d, a better distance preservation property 3 tends to be achieved with smaller sparsity ratio k/n in the quantization fr, (u()) of original data ul and larger projection ratio m/n for random matrices. To generate the original data u(9) flexibly with any given k. namely having supp(s>,(u())) = k, we simply set r = 0 and ensure the number of nonzero entries in u(t) equal to k. Considering the specific values of the nonzero entries do not affect the distance preservation property, as demonstrated in Theorems [ and [ we set u(") E {0, =1]" in the case of ternary quantization (.) for easy simulation. Moreover, we set the number of data pairs N = 10000, the original data dimension n 10000, the data sparsity ratio k/n E (0.01%, 0.1%, 1%, 10%), the matrix's column degree d E [1, 10), and the projection ratio m/n E (10%, 50%3.
The simulation results are provided in Figure 1 For comparison, the results for the popular Gaussian matrix-based random projection are also provided. Figure [ illustrates that as expected in Theorem 3 the distance variation rate of random binary matrices inclines to increase with the column degree d. This indicates a decline in distance preservation capability. This trend is particularly evident, when the sparsity ratio k/n of original data is relatively small, such as k/n < 1%. This is consistent with our theoretical analysis. As the sparsity ratio k/n increases, binary matrices tend to exhibit similar distance preservation performance across different column degroes d. Compared to Gaussian matricos, binary matrices can often achieve lower distance variation rates, indicating better distance preservation performance, especially for small values of k/n. As k/n increases, two kinds of matrices tend to exhibit comparable distance preservation performance. These trends are also observed in the case of binary quantization, where both the original and projected data are quantized to (0, 1)-binary values, as detailed in Appendix [A.4.]] Figure 7 Notably, the above performance trends regarding distance preservation are corroborated in the subsequent experiments conducted on classification and clustering, providing further validation of our theoretical findings.
5 Experiments
5.1 Settings
In this section, we investigate the performance of the ternary and binary-quantizer projections of sparse data in both supervised and unsupervised learning tasks, specifically classification and clustering. Random projections are implemented using random binary matrices with different column degrees. Our goal is to find the column degree that leads to the best classification or clustering performance. For comparison, the performance is also examined for the popular Gaussian matrix- based random projections and for the non- quantized projections. Considering both the ternary and binary-quantized projections commonly exhibit similar performance trends with the varying of the column degree of binary matrices, we will maïnly discuss the results of ternary projections and defer the results of binary projections to Appendix A.4
5.1.1 Classification and clustering algorithms
To directly reflect the impact of the distance between projected data on classification and clustering, we employ linear similarity metrics-based algorithms for both tasks. Specifically, classification is implemented with two fundamental classifiers: the K-nearest neighbor (KNN) classifier based on cosine distance (Peterson, 2009) and the support vector machines (SVM) with linear kernel (Cortes & Vapnik 1995). Both classifiers have performance fully dependent on the distance between data, without involving additional operations to further improve data discrimination. Empirically, the two classifiers tend to show similar performance trends as the column degree of binary matrices varies. For brevity, we will focus on the results of KNN and present the results of SVM (Cortes & Vapnik 1995) in Appendix A.4 Clustering is implemented with the k-means algorithm based on cosine distance (MacQueen et al. 1967p. To evaluate clustering accuracy, we follow the strategy adopted in (Xu et al. 2004). Given a set of labeled data, we first remove their labels to
8

---

Published in Transactions on Machine Learning Research (02/2025)
run the clustering algorithm, then label each resulting cluster with the majority class according to the labels of original data, and calculate the proportion of the data samples correctly classified by each cluster.
5.1.2 Data
The sparse data intended for projection are generated from the datasets YaleB (Georghiades et al. 2001 Lee
et al. 2005), CLEARIO (Krizhessyy & Hinton 2009) and Mini-lmageNNet (Vinyals et al. 2016), respectively
via the feature transforms DWT (Mallat) 2009), : AlexNet Conv5 (Krizhevsky et al. 2012) and VGG16 Conv5 3 (Simonyan & Zisserman 2014]. To provide relatively good classification performance, we assign more advanced feature transforms to more complex datasets. The datasets are briefly introduced as follows. YaleB contains the face images of 38 persons, with about 64 samples per person. From the datasct, we randomly select 9/10 samples for training and the rest for testing. CIFARIO consists of 10 classes of color images, with 6000 samples per class. Mini-ImageNet is a subset of ImageNet (Deng et al.) 2009), which consists of 100 classes of color images, each class having 600 samples. For the latter two datasets, we use their default training and testing samples, with the ratio of 5/1. For the three datasets, we normalize the feature vectors with zero mean and unit variance, and reduce the vector dimensions several times to the order of thousands for casier simulation. The dimension roduction may decrease the classification or clustering accuracy but not influence our comparative study. To validate Theorems and 2 we evaluate two kinds of sparse data that have approximately and exactly sparse distributions, respectively, as specified in Definitions 2 and 3 The approximately sparse ones are the original sparse features generated with DWT and CNN, and the exactly sparse ones are obtained by further sparsifying the features with given sparsity ratios of k/n = 1%, 5%, 10% and 20%. Compared to the original, approximately sparse features, as mentioned earlier, the resulting exactly sparse features are usually more favorable for classification (Lu et al., 2023 For the random projection model [I. we test two different projection ratios: m/n 10% and 50%.
5.2 Classification results
The classification rosults are provided in Figures 2 and Figure i respoctively for the exactly sparse features and the approximately sparse features. In each figure, the first and second rows correspond respectively to the random projection cases of projection ratios m/n = 10% and 50%, and the four subfigures in each row correspond to the exactly sparse features with sparsity ratio k/n = 1%, 5%, 10% and 20%. Considering the fact that exactly sparse features gencrally outperform approximately sparse features, and ternary quantiza- tion outperforms binary quantization (Lu el al. 2023). for brevily, we mainly analyze the classification on the ternary quantized projections of exactly sparse features, as illustrated in Figures 4 focusing on the following aspects.
5.2.1
Binary matrices with different column degrees
By the remark of Theorem 3 the proposed distance preservation property 13p tends to hold with higher probability, when binary matrices have smaller column degree d. Then, the classification accuracy of quantized projections is expected to decrease with the increased column degree d. This performance trend is basically verified by the results illustrated in Figures 24 see the x-marked, solid lines for the classification of the ternary quantized projections of the exactly sparse features with different sparsity ratios k/n = 1%, 5%, 10% and 20%. It can be seen that the performance declining speed differs with different data types, and it seems that the easier the data for classification, such as the DWT features of YaleB shown in Figure 2 the more evident the performance advantage of d = 1 becomes compared to other larger d values. An exception worth mentioning is the case of k/n- 1%, shown in Figures 2 and g where d = performs slightly worse than d = 2. This deviation should be attributed to the gap between theory and practice: the classification of quantized projections relates not only to the distance preservation property studied here, but also to other factors out of our scope, such as feature discrimination. Despite the imperfect, our theoretical ostimation is generally supported by the results of Figures 2 the column degree tends to provide projections
better or comparable performance to other larger d, in the classification of the of exactly sparse features.
9

---

Published in Transactions on Machine Learning Research (02/2025)
BOSTQ GM
BV
TM
TAV
R//n 1%, m/n 10%
(b) k/n 5%, m/n 10%
(c) k/n 10%. m/ 10%
(d) k/nn 20% m m//n 10%
BM -0-CU-TO
(0) k/n 1%, m/n 50%
(1) k/Y1 5%, m/n 50%
(g) k/n 10%, m/n 50%
(b) k/n 20%, m/n 50%
Figure 2: Clussification accuracy for the ternary-quantized (TQ) (and non-quantize)) projections the exactly spanse features of YaleB (DWT), with four different feature sparsity ratios k/n 1%, 5%, 10% and 20%, using two projection matrices: the Gaussian matrix (GM) and the binary matrix (BM) with varying column degree BM-d [1, 10). under two projection ratios m/n = 10% and 50%.
-O-GH
Accuree
-y PM
SM
R/nn 1%, m/n 10%
(h) k/n 5%, m/n 10%
(c) k/n 10%, m/n 10%
(d)
k/nn
20% m m/n 10%
HI -0-04-00
1or -0-03000
(0) k/no 1%, m/n 50%
(1) k//1 5%, m/n 50%
(g) k/n 10%, m/n n 50%
(b) k/n 20%, m/n 50%
Figure 3: Clussification accuracy for the ternary-quantized (TQ) (and non-quantized) projections of the exactly spanse features of CIFAR10 (AlexNet), with four different feature sparsity ratios k/n = 1%, 5%, 10% and 20%, using two projection matrices: the Gaussian matrix (GM) and the binary matrix (BM) with varying column degree BM-d E [1, 10), under two projection ratios
m/n = 10% and 50%.
5.2.2 Quantized vs. non-quantized projections
By (Lu et al. 2023), quantized projections can provide better classification performance than non-quantized projections, if both the original data and random matrix have sufficiently sparse distributions, and the quantization threshold for projected data properly selected. This performance property also observed in our experiments. Comparing the classification results provided in Figures for the ternary-quantized projections (x-marked, solid lines) and non-quantized projections (x-marked, dashed lines), it can be seen that the former tends to achieve better performance than the latter, when the column degree d of binary matrix and the sparsity ratio k/n of original data (i.c. the exactly sparse fcatures) both bocome smaller, such as the case of d=1 and k/n = 1%. Note that by Theorem 1 we here simply set the quantization threshold as r = 0, and a better performance for quantized projections should be obtained the threshold is more carefully selected with can obtain better classification performance on quantized projections than on non-quantized projections. This result is highly attractive both in terms of complexity and accuracy.
[Lu al.) 2023). Overall, the above results indicate that the sparse binary matrix
10

---

Published in Transactions on Machine Learning Research (02/2025)
IM
205-0
B/nn 1%, m/n 10%
(b) k/n 5%, m/n 10%
(c) k/n 10%, m/n 10%
(d) k/nn 20% m/n 10%
BM -0-CU-T0
3M
(0) k/T 1%, m/n 50%
(1) k/Y1 5%, m/n 50%
(g) k/n 10%, m/n 50%
(b) k/n 20%, m/n 50%
Figure Clussifiationn accuracy for the ternary-quantized (TQ) (and non-quantized) projections of the exactly spanse features of Mini-ImageNet (VGG16), with four different feature sparsity ratios k/n = 1%, 5%, 10% and 20%, using two projection matrices: the Ganssian matrix (GM) and the binary matrix (BM) with varying column degree BM-d E [1, 10), under two projection ratios m/n 10% and 50%.
DT 197
851
+ 0z
-O CV
BHd
k/m 1% m/n 10%
bb) k/n 5%, m/n 10%
(c) k/n 10%, m/n 10%
(d) k/n 20% m/ n 10%
moco Cakaro
KC CM
BM CM
BMd
B16
(8) k/n 1%, m/n 50% (1) k/n 5%, m/n = 50%
(8) k/n 10%, m/n = 50%
(b) k/n 20%, m/n 50%
Figure Classification accuracy the binary-quantized (BQ) (and non-quantized) projections the exactly sparse features of YaleB (DWT), with different feature sparsity ratios k/n 1%, 5%, 10% 20%, using two projection matrices: the Gaussian matrix and the binary matrix with varying columnn degree BM-d E [1, 10), under two projection ratios m/n = 10%
and 50%.
5.2.3 Binary matrices Gaussian matrices
Figures demonstrate that binary matrices (x-marked solid lines) lend to outperform Gaussian matrices (circle-marked solid lines), as the column degree d binary matrix and the sparsity ratio k/n of original data both become smaller, such as the case of d=1 and k/n 1%. The superior performance of binary matrices should be attributed to its advantage in distance preservation, demonstrated in Section 1.4 this case, we encouraged to replace Gaussian matrices with sparse binary matrices, for improvements both in complexity and accuracy.
5.2.4 Binary quantized projections
By the discussion in Section 4.3 the theoretical properties of binary matrices we derive with ternary quan- tized projections Theorems should also hold with binary quantized projections. In other words, the performance trends derived in Figures 4 for ternary projections, should be also achievable for binary pro- jections. To verify this, examine the classification binary projections in Figure 5 see Appendix A.4.2
11

---

Published in Transactions on Machine Learning Research (02/202))
Accerncy
BM CoL-TO
BY
YaleB, m/n 10%
(b) CIFARIO, m/n 10%
(c) Mini-mmageNet, m/n 10%
Accuray
-0-D4-70
(d) YaleB, m/n 50%
(e) CIFARIO, m/n 50%
(I) Mini-ImageNet, m/n 50%
Figure Classification accuracy for ternary-quantized (TQ) (and non-quantized) projections of the original, approximately sparse features: YaleB (DWT), CIFARIO (AlexNet), Mini-ImageNNet (VCG16), using two projection matrices: the Caussian matrix (GM) binary matrix (BM) with varying column degree BM-d [1, 10]. under two projection ratios m/n
and 50%.
for more results. Figure 5 shows that similarly as the classification of ternary projections, in the classification of binary projections the binary matrix with column degree d = 1 exhibits better comparable performance than other denser matrices. Moreover, it is worth mentioning that binary quantization often performs worse than ternary quantization, observed in [Lu et al. 2023), due to discarding more feature elements.
5.2.5 Approximately sparse features
In Figure we provide the classification results on the ternary quantized projections of the original features, which have approximately sparse structures. As theoretically expected, binary matrices with d = 1 achieve better or comparable performance to other denser matrices. Empirically, these approximately sparse features do not precisely align with the decay speed specified Theorem 2 This suggests that our theoretical results demonstrate strong universal applicability, showing relatively little sensitivity the sparsity of the original data. With the increasing of k/n, illustrated in Figures 6 the performance advantage of binary matrices over Gaussian matrices will become less evident in the classification of quantized projections. This performance trend is consistent with the distance preservation property illustrated in Figure [ Finally, recall that the original, approximately sparse features lend to achieve higher classification accuracy, if being further simplified to exactly sparse structures (Lu et al. 2023 Then for both better classification and casier computation, we are motivated to transform theses features to exactly sparse structures before conducting random projections on them.
5.3 Clustering results
Due to space limitations, we provide the clustering results for the ternary and binary quantized projections in respectively. Similarly to classification, the extremely sparse binary matrix with column degree d = 1 cxhibits several analogous properties in clustering. Specifically, 1) it can achieve superior or comparable performance to other denser binary matrices with larger values, as well as Gaussian matrices; 2) its performance on quantized projections is often better than on non-quantized projections; 3) these performance advantages can endure even when the feature sparsity ratio k/n increases from 1% 20%, gradually deviating from the theoretical condition we impose on feature sparsity.
Appendix A.4.3, specifically in Figures II 13 and Figures 14 16
12

---

Published in Transactions on Machine Learning Research (02/2025)
6 Conclusion
For the binary matrix-based random projection, where the projected data are further quantized to binary ternary values, we have investigated how the sparsity of binary matrices influences the ability of the quantized projections to preserve pairwise distances between the quantized original data. Our analysis indicates that binary matrices with sparser structures tend to better maintain pairwise distances, when the original data intended for projection exhibit sufficiently sparse structures. This performance trend has been validatod through classification and clustering experiments on quantized projections of typical data features, including DWT features of YaleB and CNN features of CIFARI0 and ImageNet, all demonstrating approximately sparse structures. Experiments show that extremely sparse binary matrices with only one nonzero entry per column can achieve superior or comparable classification performance compared to other denser binary matrices and Gaussian matrices. The extremely sparse matrix structure allows us to significantly reduce the complexity of the quantized random projection models, such as the large-scale retricval model (Charikar, 2002). Moreover, it noleworthy that our research contributes to underslanding and analyzing the sparse structures inherent in other advanced models that incorporate quantized random projections, like deep quantization networks (Wan et al.] 2018 Qin et al. 2020), well as biological neuron models (Dasgupta)
et al. 2017
Acknowledgements
We sincerely thank the editors and anonymous reviewers for their invaluable time and constructive feedback. Furthermore, gratefully acknowledge the support provided by the National Key Research and Develop- ment Program of China (Grant Nos. 2022YTB3206900 and 2023YTA1008701) and the National Natural Science Foundation of China (Grant Nos. 61991412, 61801264, and 12001318).
References
D. Achlioptas. Database-friendy) random projections: Johnson Lindenstrauss with binary coins. J. Comput. Syst. Sci., 66(4):671-68) 2003.
Petros Boufounos and Shantanu Rane. Efficient coding of signal distances using universal quantized embeddings. In Data Compression Conference, pp. 251 260, 2013.
Moses S Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry- Sourth annual ACM symposium on Theory of compuling, pp. 380-388, 2002.
Corinna Cortes and Vladimir Vapnik. Support-vector networks. Machine learning, 20(3):273 297, 1995.
S. Dasgupta and A. Gupta. An elementary proof of the Johnson Lindenstrauss lemma. Technical Report, UC Berkeley, (99-006), 1999.
Sanjoy Dasgupta, Charles F Stevens, and Saket. Navlakha. A neural algorithm for a fundamental computing problem. Science, 358(636)):793 796, 2017.
J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: A Large-Scale Hierarchical Image Database. In IEEE Conference on Computer Vision and Pattern Recognition, 2009.
D.L. Donoho. Compressed sensing. IEEE Transactions Information Theory, 52(4):1289 1306, 2006.
Thierry Eude, Richard Grisel, Hocine Cherifi, and Roland Debrie. On the distribution of the det coefficients. In IEEE International Conference on Acoustics, Speech and Signal Processing, pp. V-365. IEEE, 1994.
A. Georghiades, P. Belhumeur, and D. Kriegman. From few to many: Illuiination cone models for face recognition under variable lighting and pose. IEEE Trans. PAMI, 23(6):643 660, 2001.
Arvind Iyer and Johannes Burge. The statistics of how natural images drive the responses of neurons.
Journal of vision, 19(13):4-4 2019.
13

---

Published in Transactions on Machine Learning Research (02/2025)
Laurent Jacques, Jason N Laska, Petros T Boufounos, and Richard G Baraniuk. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectios. IEEF Transactions on Information Theory, 59(4): 2082 2102, 2013.
W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math., 26:189-206, 1984.
Samuel Kotz, Tomasz Kozubowski, and Krzystof Podgorski. The Laplace distribution and generalizations: a revisil with applications communiications, economics, engineering, and fonance. Springer Science Business Media, 2012.
A. Krishevsky and G. Hinton. Learning multiple layers of features from tiny images. Muster's thesis, Department of Computer Science, University of Toronto, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convolutional neural networks. In Advances in Neural Information Processing Systems, 2012.
K. Leo, J. Ho, and D. Kriegman. Acquiring linear subspaces for face recognition under variable lighting. IEEE Trans. PAMI, 27(5):684 698, 2005.
P. Li, T. J. Hastie, and K. W. Church. Very sparse random projections. in Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and dala mining, 2006.
Ping Li, Michael Mitzenmacher, and Anshumali Shrivastava. Coding for random projections. In International Conference on Machine Learning, pp. 676 684. PMLR, 2014.
Wen-Ye Li and Shu-Zhone Zhang. Binary random projections with controllable sparsity patterns. Journal of the Operations Research Society of China, 10(3)=507-528, 2022.
Weizhi Lu, Weiyu Li, Wei Zhang, and Shu-Tao Xia. Expander recovery performance of bipartite graphs with girth greater than 4. IEEE Transactions Signal and Information Processing over Networks, 5(3): 418 427, 2018.
Weizhi Lu, Mingrui Chen, Kai Guo, and Weiyu Li. Quantization: Is il possible to improve classification? Data Compression Conference, pp. 318 327. IEEE, 2023.
James MacQueen et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, volume 1, pp. 281 297. Oakland, CA, USA, 1967.
Stphane Mallat. A Wavelet Tour of Signal Processing, Third Edition: The Sparse Way. Academic Press, Inc., Orlando, FL, USA, 3rd edition, 2009.
Rodrigo Mendoza-Smith and Jared Tanner. Expander lo-docoding. Applied and Computational Harmonic Analysis, March 2017. ISSN 1063-5203.
Leif E Peterson. K-nearest neighbor. Scholarpedia, 4(2):1883, 2009.
Haotong Qin, Ruihao Gong, Xianglong Liu, Xiao Bai, Jingkuan Song, and Nicu Sebe. Binary neural networks: A survey. Pattern Recognition, 105:107281, 2020.
K Ramamohan Rao and Ping Yip. Discrete cosine transform: algorithms, advanlages, applications. Academic press, 2014.
Daniel L Ruderman. The statistics of natural images. Network: computation in newral systems, 5(4):517-545 5488 1994.
Ecro Simoncelli. Modeling the joint statistics of images the wavelet domain. In Wavelet Applications in Signal and Image Processing VII, volume 3813, pp. 188-195. International Society for Optics and Photonics, 1999.
14

---

Published in Transactions on Machine Learning Research (02/2025)
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint Xrxi::1400 1556, 2014.
Diego Valsesia and Enrico Magli. Binary adaptive embeddings from order statistics of random projections. IEEE Signal Processing Letters, 24(1):111-115, 2016.
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for shot learning. Advances in neural information processing systems, 29, 2016.
Diwen Wan, Fumin Shen, Li Liu, Fan Zhu, Jie Qin, Ling Shao, and Heng Tao Shen. TBN: Convolutional neural network with ternary inputs and binary weights. In Proceedings of the European Conference on Computer Vision, pp. 315-332, 2018.
Yair Weiss and William T Freeman. What makes good model of natural images? In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1-8. IEEE, 2007.
Linli Xu, James Neufeld, Bryce Larson, and Dale Schuurmans. Maximum margin clustering. In L. Saul, Y. Weiss, and L. Bottou (eds.), Advances in Neural Information Processing Systems, volume 17. MIT Press, 2004.
John Zarka, Louis Thiry, Tomas Angles, and Stephane Mallat. Deep network classification by scattering and homotopy dictionary learning. In International Conference on Learning Representations, 2020.
A Appendices
A.1 Proof of Theorem 1
Proof. For the two exactly sparse data points u, v E R", suppose their support intersection &b supp(u) supp(v). Then we can write
0
fo(u) folu) = fo(us)
(9)
Recall that fo(-) is an clement-wise function. Similarly, for the two projected points u', v E Rm, we define their support union and intersection as ø' = supp(u') U supp(v') and e' = supp(u') supp(v'), and then can write
((w')To()))) Σ fo(u()fo(o)).
(10)
In the sequel, we aim to prove that 10) can be linearly transformed to 19 The analysis of 11) requires us to first determine the support intersection w between projected data. To achieve this, we examine the value of each clement fu(u)) of fo(u'), which for case of analysis is divided into two groups on the basis of e -N(sup(u)) or not. Notice that the analysis will require us to frequentty explore the adjacency relation between the random matrix's columns and rows, say the mapping relation between the original data and projected data, specified in Definition I rj E supp(u), and then can write
For the case of & (ssup((u)) by Definition [ we have Rag 0,
So(u)) = fo
Rijju
(11)
jE(n]((eupp(()
=0
15

---

Published in Transactions on Machine Learning Research (02/2025)
since u, = 0, vij E [n]] supp(u); otherwise, can derive
[o(u() - fo
Σ Rigus
jEsupp(u)
_ fo (Eeupp(u)nu((()
Σ
Ri
(12)
3 fo ((j=supp(()))11)
* 0
for the case i (sspp((u)) The derivation of [12 is detailed as follows: (i) The first equation results from the definition of supp(u), u), which holds u, # 0 for i supp(u) (); and otherwise, * (ii) The second equation is deduced by Definition 1 that is E (i), if Rag # O. (iii) By the structure of R E {0, 11mxmxxm with column supp(u) U supp(v), it is easy to see that. the columns of R.. are
degree d and with R__ R. dī orthogonal to each other, and equivalently, N ((ii) = 0, Vii # j2 and j1, J2 E á (or E supp(u) C Φ); the orthogonality property suggests that there cxists only one column index j E (V(i) O supp(u) (and satisfying R., = 1), Vi E (supp(uu) and this yields the third equation. (iv) The fourth equation easily derived by " 00, supp(u).
Combing the results of 11 and 12 it follows that =upp(t"==((supp(u))) which indicates that the support of the projected data u' is the adjacent set of the support of the original data Similarly, the same result can also be derived for the other pair of data v, v', that is (app((")=<(supp((0) Then the support intersection ot' of the two projected data u', v' can be expressed as
w 1 supp(u') n supp(v')
2 N (supp(u)) NW (supp(u)) (suup(())
(13)
2 N (supp(u) supp(y))
N(w)
which has the third equation derived by the orthogonality of R. implying W(h) (N((2)) 0, Vjn. j2 E ò = supp(u) supp(v). The result indicates that the support intersection o' of projected data w', of is identical to the adjacent set of the support interscction v of original data u,
Given & = ((bb in 13 we can further formulate
10 as
((w')To(u))
1 Σ fol1)So(o))
2
fo(u))f((v))
JEW (EN()
Σ
Σ
fo(uz))o(u,)
(14)
JEV (ENG)
4 d
Σ So(u,)So(v,))
JEV
8 d So(u) To(v))
(i) The second equation is derived by the result of 13 that is v/ = (w = U N((), with N(i 0, Vj1 # je and jı, j2 E o. (ii) The third equation results from the uniqueness of A(1i) supp(u), provided A(j), j E d C supp(u); and the details can be found in the analysis of the third equation of (12). (iii) The fourth equation is derived by A(j) d. The proof is complete.
for which the derivation is detailed as follows.
16

---

Published in Transactions on Machine Learning Research (02/2025)
A.2 Proof of Theorem 2
Proof. The proof similar to that of Theorem [ First, we divide the element coordinates of the original data vectors u, into two groups in terms of their element quantization fr, (ux), (ry) equal zero not, in order to define the support union o supp(fr, (u)) U supp(fr,(t) (+)) and the intersection v supp(fr, (u)) n supp(fr, (v)). In the similar way, further define the support union ø' and interscction of for the projected data u', v'. Then need to identify the relation between v/ and tb. To achieve this, as in [1ib and (12). we propose to determine the value of fr, (u{) in terms of i E <sssupp(f (u))) or not. For the case of i (supp(ff (u))), we have
(n,( =
Σ
Ragus
(15)
jelmnkouppi(-, (a))
=0
since by the summation formula for geometric series, can be deduced that 7i "i, - is greater than the absolute vale of the function input, under the condition of ///4 s e- and 2 In(2 + v and for the other case of i & N (supp(Sr, (u))) we can derive
2
fr (u,)
1 fm
Σ
Ri
Σ
R
jEsupp(Jr, (w)
je(m]) (us))
2 fn
Σ jEin|) (we)
Rigu
(16)
3 Jn
4 * 0
which has the third equation resulting from the relation of () [jEln]Xeupp(is (o.)) R T1, while the relation can be derived using the same method for 15p. The above two results 115 and [16] are the major characteristies of the proof of Theorem and the subsequent proof will proceed similarly in Theorem I omitted here for brevity.
A.3 Proof of Theorem 3
Proof. The condition of R.T Ra dl means that RT,,, R,, = for V j1. Φ. J1 + j2. In other words, the nonzero entries of any columns of R. have no coordinate overlapped. By the distribution of the nonzero entries, we can express the probability as
Cd Cd
Odd m (16) 1)d
Pr(RT = dl
m-d
(C'd ml
|oo|
[mm d)!]lol
(m!) |0 lold)!
17

---

Published in Transactions on Machine Learning Research (02/2025)
Given and o, define g(d: m, m, = Pr(R. Ru,o dl Then it can be derived that
(1 d]]]
g(d; m, ②) g(d. + 1;m,
(mr])lrr [mm (id))
(ml) 91 - (d4-(d+1))))
(m d)l0)
(17)
111 (m 100 E)
2=
> 1
since m-lold-2 > 1, given [0] 2 and 0 <
| 1. This indicates that g(d; m, Φ) is a monotonically decreasing function with respect to d, with its maximum value attained at d d= 1. Specifically, this maximum value is given by
(m 1)!
g(d: m, 0) ml (m 1o
(18)
| 0 (m 2
778 (b
The proof is complete.
18

---

Published in Transactions on Machine Learning Research (02/2025)
A.4 Other experimental results
A.4.1 Distance preservation
we calculate the distance variation rale by ( for binary quantized projections. The results are consistent with our theoretical prediction: the distance variation rate of binary matrices tends increase with the column degree d, particularly when the sparsity ratio k/n of original data is sufficiently small.
In Figure 7
(M
+
0 0
-0-
GM
k/ 0.01%, m/n 10%
(b)
k/n
0.1%, m / 10%
(c) k/n 1%, m/n 10%
(d) k/n 10% m/n 10%
+ BM
O GM
GM
0
0
0
0
0
-
0
0
-2
BM-d
(8) h/n = 0.01 %, m/n 50%
(I) k/n 0.1%, m/n = 50%
(g) k/n = 1%, m/n 50%
(h) k/n = 10%, m/n = 50%
Figure Distance variation rate for the binary-quantized (BQ) (and non-quantized) projections of the generated data, with four different feature spansity ratios k/n 0.01%, 0.1%, 1% and 10,, using two projection matrices: the Gaussian matrix (GM) and the binary matrix (BM) with varying column degree BM-d [1, 10), under two projection ratios m/n 10% and 50%. Note smaller distance variation rate, the better distance preservation.
A.4.2 Classification
In Figure we conduct the SVM classification on the ternary-quantized projections of YaleB (DWT). and conduct the KNN classification on the binary-quantized projections of CIFAR10 (AlexNet) and Mini- ImageNet (VGG16), respectively, Figures g and 10 The classification results in Figures 10 demonstrate performance trend that aligns with our theoretical prediction: the extremely sparse binary matrix with column degree d 1 can achieve superior comparable performance to other denser matrices with larger
d values.
A.4.3 Clustering
In Figures 11 and Figures 14 16 we respectively examine the k-mcans clustering performance on the ternary and binary-quantized projections of YaleB (DWT), CIFARIO (AlexNet) and Mini-ImageNel (VGG16). The results align with our theoretical prediction: the extremely sparse binary matrix with column degree d = can achieve superior or comparable performance to other denser matrices with larger d values.
19

---

Published in Transactions on Machine Learning Research (02/2025)
Accums
Accurtcy
Accurscy
TM
RM
O-0M
O-OM TO
BNd
BMd
k/m 1%, m/n 10%
(b) k/n 5%, m/n 10%
(c) k/n 10%, m/n 10%
(d) k/
20% n 10%
-H-GM-T
Accuray
Accuracy
EXCAN
--OXTT
C3-T0 0 GM
OK
- GM
Bdd
(e) k/n 1%, m/n 50%
(f) k//n 5%, m/n 50%
(g) k/n 10%, m/n 50%
(h) k/n 20% m/n 50%
Figure 8: SVM classification accuracy for the lernary-quantived (TQ) (and non-quantized) projections of the exactly spanse features of YaleB (DWT), with four different feature spansity ratios k/n 1%, 5%, 10% and 20%, using projection matrices: the Gaussian matrix (GM) and the binary matrix (BM) with varying column degrec BM-d [L, 10), under two projection ratios m/n 10% and 50%.
Accursty
Accuray
201
TM
IM
- TM
BHd
BMd
BN
BM-d
k/n 1%, m/n
10%
(b) k/n 5% m 10%
(c) k/n 10%, / 10%
(d) k/n 20% /v 10%
Accuncy
Accurnyy
Accurecy
G-GM-B0
-G-COIIC
G3
+O-GH GH
-O+ GSI
(8) k/ m/n- 50%
(1) k/n 5%, m/n 50%
(g) k/n 10%, m/n 50%
(h) k/n 20% m/n 50%
Figure 9: Classification accuracy for the binary-quantized (BQ) (and non-quantized) projections of the exactly sparse features of CIFAR10 (AlexNet), with four different feature sparsity ratios k/n 1%, 5%, 10% and 20% using two projection matrices: the Gaussian matrix (GM) and the binary matrix (BM) with varying column degree BM-d E [1, 10), under two projection ratios m/n 10% and 50%.
20

---

Published in Transactions on Machine Learning Research (02/2025)
Accuncy
Accuncy
Accuncy
Accuncy
RM GM
--B1--0 GM
+ GM
O.GM
Bdd
/// //2 1%, m/
10%
(b) k/n 5%, m/n 10%
(c) k/n 10%, m/n 10%
(d) k/n 20% m/n 10%
Acnny
Accurry
Accorey
DM TM
155-11 7M1
BM -0--0000
* BM
-0GM50
0- -M-BO
BHd
BMd
BN
BM-d
(0) k/n 1%, m/n 50%
(1) l//n 5%, m/n 50%
(g) k/n 10%, m/n 50%
(h) k/n2 20% m/n 50%
exactly sparse features of Mini-ImageNet (VGG16), with four different feature sparsity ratios k/n = 1%, 5%, 10% and 20%, using two projection matrioes: the Gaussian matrix (GM) and the binary matrix (BM) with varying column degree BM-d E [1, 10), under two projection ratios m/n = 10% and 50%.
Figure 10: Classification accuracy the binary-quantized (BQ) (and non-quantized) projections
134-70 -0-CN--T OO
Accunny
Accurac
-- RV
2M
PM
-0-GS-T
k/
1%, m/n 10%
(b) k/n 5%, m/n 10%
(c) k/n 10%, m/n
(d) k/nn 20%, m/n 10%
-0-03 TV
696-
BM4
(6) k/n = 1%, m/n 50%
(1) k/n 5%, m/n = 50%
(g) k/n 10%, m/n 50%
(b) k/n 20% m/n /n 50%
Figure 11: Clustering accuracy for the ternary-quantizee (TQ) (and non-quantizel) projections of the exactly sparse features of YaleB (DWT), with four different feature sparsity ratios k/n 1%, 5%, 10% and 20%, using two projection matrices: the Gaussian matrix and the binary matrix with varying column degree BM-d E [1, 10), under projection ratios m/n 10% and 50%.
21

---

Published in Transactions on Machine Learning Research (02/2025)
301
08
1O GH
Accussy
x
-0-CATO
Q-C0-TO
866
BN-
B954
BMd
8/ 1%, m/n 10%
(b) f/n 5% m/n 10%
k/n
10% m/n
10%
(d) k//
20%
m/n 10%
Acconey
Actumey
2M OV
Q--33-11 .Oh GM
-Q-U20-11
.Oh OM
696
BMd
(0) k/n1 1%, m/n 50%
(1) k/Y1 5%, m/n 50%
(g) k/n 10%, m/n 50%
(b) k//n 20%, m/n 50%
Figure 12: Clustering accuracy for the ternary-quantieed (TQ) (and non-quantized) projections of the exactly sparse features of CIFAR10 (AlexNet), with four different feature sparsity ratios k/n = 1%, 5%, 10% and 20%, using two projection matrices: the Gaussian matrix and the binary matrix with varying column degree BM-d E (1, 10,, under two projection ratios m/n = 10% and 50%.
SMC
331
58
-D-MM -O- CaL
BM4
BHd
k//n 1%, m/n 10%
(b) A/n 5%, m/n 10%
(c) k/n 10%, m/n 10%
(d) k// 20% m/n 10%
RACTO 3NC
GM
BMd
BM-
BH4
BH4
(0) k/n = 1%, m/n 50%
(E) k/nn 5%, m/n a 50%
(g) k/n 10%, m/n = 50%
(h) k/n 20%, m/n n 50%
Figure Clustering accuracy the ternary-quantived (TQ) (and non-quantized) projections of the exactly sparse features of IiageNee (VGG16), with different feature sparsity ratios k/n 1%, 5%. 10% and 20%, using two projection matrices: the Gaussian matrix and the binary matrix with varying column degree BM-d E [1. 10), under two projection ratios m/n = 10% and 50%.
22

---

Published in Transactions on Machine Learning Research (02/2025)
1M B-005-0
TM
IM
BM -O GM
Accumay
Accuncy
Accumay
BHd
k//m 19, m//1 10%
(b) k/n 5%, m/n 10%
(c) k/n 10%, m/n 10%
(d) k/n 20%, m/re 10%
9-020-0 BQ
O--34-00 DQ HO-
accurayy
Accurmes
B15
BM4
(0) k/n = 1%, m/n 50%
(1) k/mn 5%, m/n n 50%
(g) k/n 10%, m/n n 50%
(h) k/n 20%, m/n /n 50%
Figure Clustering accuracy for the binary-quantized (BQ) (and non-quantized) projections of the exactly spanse features of YaleB (DWT), with four different feature sparsity ratios k/n 1%, 5%, 10% and 20%, using two projection matrices: the Gaussian matrix and the binary matrix with varying column degree BM-d E [1, 10), under two projection ratios m/n = and 50%.
ALCUNCy
secumny
CNLRO
O
O
BHd
k/n 1%, m/n 10%
k/n 5%, m/ 10%
(c) k/n 10% m/n 10%
(d) k/n 20% m/n 10%
Accumtt
Accomry
IIA30 -0-Gal O Ok
18
BHd
BMd
BX44
(e) k/n 1%, m/n 50%
(f) k/n 5%, m/n 50%
(g) k/n 10%, m/n 50%
(h) k/n 20%, m/n 50%
Figure 13: Clustering accuracy for the binary-quantized (BQ) (and non-quantized) projections of the exactly sparse features of CIEAR10 (AlexNet), with four different feature sparsity ratios k/n = 1%, 5%, 10% and 20%, using two projection matrices: the Gaussian matrix and the binary matrix with varying column degree BM-d E [1, 10', under two projection ratios m/n n = 10%
and 50%.
23

---

Published in Transactions on Machine Learning Research (02/2025)
BAY CUA-O
<an BM
BM
-8-0M00
-0-G35-00
334
BHd
BM4
BH4
BH4
1%, m. n 10%
(b) R/ n 5%, m/n 10%
(c) k/n 10%, m/n 10%
(d) k//1 20% m/n /n 10%
Tx 100
- mM
-O- GM
-Ō-
-O- GOL
(8) h/n 1%, m/n 50%
(1) k/Yn 5%, m/n 50%
(g) k/n 10%, m/n 50%
(h) k/n 20% m/n / 50%
Figure 16: Clustering accuracy for the binary-quantized (BQ) (and non-quantized)) projections of the exactly sparse features of Mini-ImageNet (VGG16), with four different feature sparsity ratios k/n 1%. 5%, 10% and 20%, using projection matrices: the Gaussian matrix and the binary matrix with varying column degree BM-d E [1. 10), under two projection ratios m/n 10% and 50%.
24


Reviews:
[{"review_id": "o82aPss86B", "reviewer": "Reviewer_oRdZ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \nThe theoretical results seem correct.\n\nWeaknesses:\nIn my opinion, the setting is too simplistic. \n\nAs per TMLR policy:\nAre the claims made in the submission supported by accurate, convincing and clear evidence?\nYes.\nWould at least some individuals in TMLR's audience be interested in knowing the findings of this paper?\nMaybe, I don't know.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Edited review:\n\nThis paper aims to study the preservation of inner products after a random projection and subsequent quantization of the input and output signal. The inner product is preserved because the random projection matrix is very specific: it has at most one 1 per row and exactly d 1s per column. \n\nThe second result is an adaptation to a setting where the signal decays and the threshold in the quantization is adapted to the decay of the signal. I didn't check the proof details but I believe it's correct.\n\nThe third result studies a random matrix's probability of having the specific property described above. \n\nNote:\nIn a previous version of this review, I asked about a possible counter-example to the main theorem. The counter-example was incorrect due to a misunderstanding of the Theorem's hypothesis.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Release a github repository with the code to the experiments.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "1sVoCsgmzt", "reviewer": "Reviewer_MZJT", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength\n\n- Analyzing this new notion of distance preservation is novel\n\n- The proof sketch is intuitive and well-explained\n\n- The experiments support the claim and the theory\n\n\nWeaknesses\n\n- The proposed study would be relevant only for the settings where the quantization of the original input data f(x) is not too far from x. This limits the scope of the proposed projection.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies random projection with quantization using a binary matrix. The key motivation behind the setting is possible hardware accelerations due to the binary structure of the random projection matrix and the quantized embedding. Analyzing distance preservation before and after projection and quantization under random projection is standard. However, the paper analyzes preserving the distance between the quantized version of the input and the projection. The paper demonstrates that this new notion of distance preservation will be satisfied for projection matrices with sub-orthogonal matrices and then analyzes conditions under which a random binary matrix satisfies that property, concluding that sparser projections are better suited for distance preservation.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Based on the empirical results, the binary random projection matrix has accuracy comparable to the Gaussian matrix. It would be interesting to demonstrate the computational advantages of the binary projection in some real-world experiments. How much computational cost does the binary matrix buy in practice for classification?\n\n- In the introduction, the contribution of Lu et al. 2023 should be discussed and contracted with the correct work because there seem to be some overlaps that can be explained.\n\n- How does the sparse binary projection work for input vectors x that are not sparse and easily quantizable? It would be good to discuss potential regimes in which the new notion of distance preservation might not lead to preserving the original distance between data points.\n\n- Since both the projection matrix and the data are very sparse, there is a risk of getting all zero outputs. Is this a valid concern?", "broader_impact_concerns": "There are no broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ve9gaC4VF3", "reviewer": "Reviewer_ov56", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Paper is well structured and progression in the reasoning is clear and easy to follow\n- Theoretical results on distance preservation are interesting and promising\n- Rigorous analysis of the classification results, as the paper gives insights on each components of the method presented (e.g. Binary vs Gaussian matrices, quantized vs not quantized data)\n\nWeaknesses:\n- I believe that the paper's main weakness is its scope and methodology choice: the main results are on the distance preservation properties of Random Projections with quantized data, while the empirical experiments are done on classification algorithms. It feels that the reason experiments are being done on classification is because of distance based algorithms such as KNN - yet this is also true for a number of  other models and tasks. Therefore there is very little empirical analysis on distance preservation itself and the extensive work on classification seems peripheral.\n- A second weakness of the paper is the absence of a tradeoff / limits discussion section: Although the paper highlights the benefits of sparse binary and ternary random projections for classification tasks, it does not delve deeply into the trade-offs involved, e.g. robustness or exposure to outliers. Therefore the paper lacks nuance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the distance preservation properties of Random Projections on sparse quantized data. More specifically, it analyzes the case of projecting sparse feature data on which binary or ternary quantization was applied. On this later point, it differs from the current literature that mainly analyzed either random projections without quantization, or applying quantization after the projection.\n\nFirst providing a theoretical analysis leading to estimating the optimal conditions and sparsity parameters (i.e. number of nonzero coefficients of the binary / ternary random projection matrix) to ensure distance preservation with high probability, the paper goes on to showing the results of some classification experiments run on benchmark datasets such as YaleB and CIFAR10.\nThese experiments demonstrate that sparse binary and ternary random projection matrices, when properly optimized, lead to comparable if not improved classification performance over denser matrices, all while offering reductions in computational and storage complexity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses section. In short, I believe the paper should refocus the Experiment part on showcasing the distance preservation properties in practice - e.g. with analyzing distance matrices. The classification experiments can then be added as a use case but - as explained before - should not be the center of the empirical study. The paper could also study other Machine Learning tasks where distance based methods are popular to show the distance preservation properties in different settings.\n\nFollowing the second weakness point, another requested change is adding more nuance in the analyses presented and discuss the limitations of quantization and random projections.\n\nFinal requested change: add code for reproducibility.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is on topic for TMLR, given that it applies a variation of a key tool (sparse random projections), and evaluates for some distance-based ML problems.  The paper includes technical analysis, and empirical evidence that the proposed approach is successful.  While there were some (relatively minor) concerns from the reviewers, the authors have addressed them in the updated paper.
Decision: Accept (poster)