WorksMathematics
Approximate Matrix Multiplication through Joint Leverage Score Sampling
Abstract
In this paper, we investigate approximate matrix multiplication through random sampling. Specifically, we propose using a non-uniform sampling distribution constructed from the leverage scores of the two matrices, and characterize the associated approximation error in terms of the matrix spectral norm; which is well-known to better characterize the downstream error when the matrix product operator is applied to an input vector. We provide the probability error bounds for the proposed algorithm are also given, and discuss connections to data-oblivious approximate matrix multiplication, and graph sparsification algorithms.
Introduction
Matrix multiplication is one of the key underlying operations used in algorithms developed in numerical analysis, scientific computing, engineering, statistics, computer science, data science and machine learning. In many applications, e.g. training contemporary machine learning and statistical inference models, this operation is executed hundreds or thousands of times, making it a bottleneck and an impediment in large scale computations.
Considering square matrices of order , naive matrix multiplication (MM) requires operations. More elegant algorithms exist, which require operations, for [61, 21, 38, 6, 32]. The smallest known MM exponent , was recently achieved in [65]. A drawback of these faster algorithms though, is that the hidden constants in their asymptotic analysis are excessively large, making them impractical.
In this paper, we utilize ideas from the “-subspace embedding” problem, to devise a novel approximate matrix multiplication algorithm. We propose a randomized approach that judiciously subsamples pairs of rows from and , to approximate the matrix product
where and , for an explicit sketching matrix with . For our proposed , we define a sampling distribution based on the left leverage scores of both and , which we call ‘joint leverage scores distribution’, and is a generalization of the matrix leverage scores distribution. These scores reveal influential pairs of rows across the two matrices. It is surprising that even though leverage scores are the main technique and tool used to study and devise subspace embeddings; and have been utilized in many applications, they have not been been used for the most common operation in linear algebra; matrix multiplication. A non-exhaustive list of where they have been utilized are the block Kaczmarz method [50, 39], low-rank approximations [27, 23], and -means clustering [8, 9, 11].
The proposed algorithm is similar to the BasicMatrixMultiplication approximate matrix multiplication (AMM) algorithm [24, 25], and is motivated by the leverage score sampling algorithm for -subspace embedding [30, 31, 45, 18]. For reasons that will become clear, we will refer to BasicMatrixMultiplication as –MM. Both –MM and leverage score sampling have been extensively studied in the literature of randomized numerical linear algebra (RandNLA) [41, 63]. The only difference between our algorithm and –MM, is the sampling distribution.
A benefit of sampling according to leverage scores, is that it permits the derivation of a spectral bound on the approximation error of the AMM, analogous to that of the -subspace embedding method [31, 63, 41]. Such spectral guarantees have not been derived for the general case of –MM, whose error has been quantified in terms of the Frobenius norm. One can use similar techniques to ours to derive a spectral bound for the –MM algorithm for the case where , though the resulting sampling complexity could be very high. We discuss this in Subsection 3.1. The special case where [31, 41] has been studied. This motivates our work, in which we propose an importance sampling algorithm similar to –MM, which is also used to derive a spectral bound guarantee for –MM. It is worth noting that leverage scores have also been used in graph sparsification algorithms [59, 28], and that block variants of sampling sketching algorithms have also been extensively studied [51, 64, 16, 20, 66 NL23a].
Our work on AMM is closely related to that of [17]. Specifically, they give a similar spectral AMM characterization to ours, both of which imply the same spectral error bound (Lemma 5). The work of [17] focuses on the so-called “oblivious subspace embeddings” (OSE) and their implications; that satisfy certain moment bounds, which they argue (using a “black box theorem”) yields an AMM with optimal properties. However, they do not give an explicit AMM algorithm. Similar results have also been derived independently in [57, 37, 44], which primarily deal with OSEs and give guarantees in terms of the matrices’ stable rank. In contrast, instead of relying on OSE black box arguments and the “-moment property”, we take a more direct approach by using a generalization of the “-subspace embedding property” to characterize the accuracy of our proposed AMM algorithm.
As in [37, 17], any AMM sketching matrix which satisfies our condition, is a -subspace embedding sketching matrix. This is achieved by simply applying it to the case where , in which case we transition from to the least squares objective function . For the algorithm we propose; which is not data-oblivious2, the resulting embedding is the leverage score -subspace embedding sketch [31].
Before transitioning to the main section of this paper, we briefly discuss the importance of sketching, which has been well-studied over the past two decades. Sketching and RandNLA is an interdisciplinary field that exploits randomization as a computational resource; to develop improved algorithms for large-scale linear algebra problems, while as a technique lies in the intersection of theoretical computer science and information theory. Primarily studied through the computer science community; sketching is used to compress information, which is the primary objective of information theory and source coding. This gives two vastly different perspectives to the problem of data compression. Furthermore, sketching has been studied in various applications, e.g. matrix and tensor algorithms [LWM⁺07, MD09, CLM⁺15, GGMW20, HH21, CJ21, MS21, CPH24], graph algorithms [36 ACK⁺16, 1, 4, 35], and of course AMM [24, 25, 26, 53, 64, 66]. Furthermore, exact MM has also been studied extensively through different perspectives, e.g. [61, 22, 54, 62, 38, 5 MNS⁺18, 6 BCG⁺23, 65, 32].
The paper is organized as follows. In § 2 we first recall the notion of leverage scores, and the –MM algorithm. Next, we describe our sampling approach to AMM; which we call ‘joint leverage score sampling’. Then, we present our AMM algorithm. Our spectral characterization of AMM is derived in Subsection 2.3. In Subsection 2.4 we present the theory behind our approach, and our spectral guarantees. In § 3 we discuss other extensions of our approach, which suggest worthwhile future work. We conclude this paper with § 4.
Joint Leverage Score Multiplication
Preliminaries
We first recall the –MM approximation algorithm. Consider the two matrices and , for which we want to approximate the product . It is known that the product may be approximated by subsampling with replacement (w.r.) row pairs from and , where the sampling probabilities are proportional to their -norms [24]. That is, we sample with replacement pairs 3 for and , with probability
for , and sum a rescaling of the samples’ outer-products:
where is the multiset consisting of the indices (possibly repeated) of the sampled pairs, i.e. .
Denote the corresponding sketches of and in –MM by and respectively. The approximation (1) satisfies . Further details on this algorithm can be found in [24, 25, 26, 63, 41, 19 NL23b]. We summarize what is known about the –MM algorithm in Theorem 1.
Theorem 1 ([41] Section 3.2). The estimator from (1) is unbiased, while the sampling probabilities minimize the variance, i.e.
and is an -multiplicative error approximation of the matrix product, with high probability. Specifically, for and the number of sampling trials which take place:
for any .
The special case where in the – algorithm has also been studied, as it appears in numerous applications. This restriction allows us to use statements from random matrix theory [52], to get stronger spectral norm bounds. One such bound is presented in Theorem 2.
Theorem 2 ([31, 41]). Let with , and approximate the product through –. Let be an accuracy parameter, and assume that . If
for , then
The left leverage scores of are defined as the diagonal entries of the projection , i.e. . Equivalently, considering the reduced left singular vectors matrix of , we have . A sampling distribution is defined over the rows of by normalizing the scores , where each row of has respective probability of being sampled . It is a known fact that
We note that methods for approximating the leverage scores are available [29, 55, 59], which do not require directly computing the left orthonormal basis . Furthermore, any orthonormal basis of the column-space of would suffice to deduce the leverage scores. We will be working with the left singular vectors matrix, to simplify certain expressions.
Lastly, we recall the following noncommutative Bernstein matrix inequality, which we use to prove the spectral characterization of our AMM algorithm. We slightly paraphrase the theorem, to better suit our notation.
Joint Leverage Score Sampling
We define the joint leverage score of the pair as the geometric mean of corresponding leverage scores, i.e.
where and are respectively the and leverage score of and .4 By and we denote the reduced left singular vectors matrices of and , with respective rows and . By the definition of leverage scores, it follows that
Let denote the vector of ’s diagonal entries, and the vector comprised of the positive square roots of ’s entries. For and the respective projection matrices of and , the vectors and are comprised of the square roots of the leverage scores of and , hence and . Let . By the Cauchy–Schwarz inequality and (6):
In this work we sample pairs of rows of the same index, and do not consider pairs for . Hence, we only consider the joint leverage scores , which we normalize to determine the sampling probabilities
Similar to the – and leverage score sampling algorithms, we construct a sketching matrix to reduce the effective dimension from to , and approximate the product:
Once the sketches are known, computing requires operations through naive MM. The pseudocode of our approach is presented in Algorithm 1.
Note that any algorithm that approximates leverage scores [29, 55, 59] could be used to speed up the computation of , as determining them exactly is a cumbersome task. The guarantees we give will assume that the sampling distribution used in Algorithm 1 is approximate.
Algorithm 1: Joint Leverage Score Sampling AMM
Input: , ,
Output: Approximate product
Initialize:
Determine: approximate distribution to (8)
for to do
sample w.r. from , according to
end
return
Using probabilities exactly equal to is an overkill. Similar guarantees hold if we instead use approximate probabilities that are “close” in the following sense: for all , where is a misestimation factor. This factor quantifies how far is from . If we sample according to the approximate distribution, the same embedding result will follow, if we modify the sampling complexity by a factor of , i.e. we oversample. The key point here is that it is essential not to underestimate high joint leverage score row pairs too much. It is however acceptable if we overestimate and thus oversample some low score pairs, as long as it is not done excessively. Throughout this paper, we will denote the resulting sketching matrices of Algorithm 1 by and , when sampling takes place according to and respectively.
Spectral Characterization for AMM
Next, we recall the basic notion of a -subspace embedding for the column-space of a matrix , which is a powerful hammer for solving least squares regression.
Definition 4 ([63]). A sketching matrix is a -subspace embedding of the column-space of for and ; with a reduced orthonormal basis such that , if it satisfies
for , with high probability.
In this subsection, we derive an analogous characterization for AMM, in order to quantify the error of our approximation. Considering the reduced SVDs of and , an AMM sketching matrix ought to satisfy
Hence, a sufficient condition that implies is , which can be formulated as
for a small constant. We denote , and
Lemma 5. If satisfies (10), then .
Proof. This is a direct application of the submultiplicativity property of the -norm to (11). □
Remark 6. If , the sampling probabilities are equal to the normalized leverage scores of , and condition (10) results in the -subspace embedding property (9). Furthermore, would be the same sketching matrix as that of the leverage score -subspace embedding sampling algorithm. Additionally, for , both orthonormal matrices, the output of Algorithm 1 is the same as that of the CR−MM algorithm.
Proposition 7. Any algorithm that constructs a sketching matrix which satisfies (10), can be used to construct a -subspace embedding sketch of .
Proof. Assume we have an algorithm that when given and , produces which satisfies (10). Further assume it is only given as an input, and let . This algorithm then constructs for the case where . Thus , and the resulting satisfies (9). □
Approximation Guarantees
In this subsection, we present our theoretical results of Algorithm 1. Unlike the guarantees of the algorithm for , whose error is quantified in terms of the Frobenius norm; the guarantee we give is in terms of the spectral norm. Specifically, we show that (10) is achieved with a high probability.
To prove our main theorem, we first need to determine the expectation; and bound the spectral norm and variance of appropriately defined matrix random variables. Once these quantities are determined, we can directly apply Theorem 3.
For , which denotes the index of the sampled pair at the sampling trial of Algorithm 1, we define
The matrices are independent copies of the matrix random variable we are considering, since we are sampling with replacement. Note that the realizations of correspond to ; i.e. for , with .
Lemma 8. For as defined in (12), we have and .
Proof. A straightforward computation gives us
thus . For the second part of the lemma, we have
for which we observe that
and
By combining these two observations, we conclude that
where in the last inequality we invoked (7).
In order to upper bound the variance parameter of the random matrix variable defined in (12), we define the matrices
where and . Furthermore, to simplify our notation, let for each . We note that and are respectively linearly dependent spanning sets of both the column and row spaces of and respectively, when . This prohibits us from explicitly computing the spectral norms of and , though an upper bound suffices for our purposes.
Lemma 9. For as defined in (12); and , we have and .
Proof. By a straightforward computation
where in the second equality we used the fact that
Let , and . It follows that
By the triangle inequality, and the fact that , we conclude that
An analogous calculation yields that .
Lemma 10. Considering any and , we have: and .
Proof. Recall that , for and the dimensional -sphere, i.e. . It follows that
which proves the first claim. The bound on is proven similarly.
We now have everything we need in order to prove our main result regarding Algorithm 1. By combining Lemmas 9 and 10, we get that
We can carry over this bound on the variance in our analysis, though the resulting expressions are not helpful to understanding the value of our method, as the variance is also an artifact of the matrices and . To simplify our statement and presentation, we therefore assume that and satisfy
which implies that . It is also evident in our results that the relative sizes and also play a role, something which does not occur when nor when considering -subspace embeddings.
Theorem 11. Let , and assume that (13) holds. Then, the sketching matrix of Algorithm 1 with sampling according to meets condition (10) with probability at least , for .
Proof. Under the assumption that (13) holds for the pair of matrices and , we know that for all random sampling trials of Algorithm 1. The corresponding argument of (10) for , is equal to for realizations of (12). By substituting , and the bounds , in the exponent of the bound in Theorem 3, we get
Assume for now that . It follows that
By taking the complementary event, we deduce that
Now, under the assumption that , the same calculation yields
By combining (14) and (15), we complete the proof.
As was briefly discussed in Subsection 2.2, the only difference in sampling according to approximate joint leverage scores and the exact scores , is that with the former we need to oversample by a factor of . We see this explicitly through their guarantees in terms of the error defined in Lemma 5, provided in Proposition 12 and Corollary 13 respectively.
Proposition 12. For , , and , the sketching matrix of Algorithm 1 with sampling according to , satisfies
Proof. Let . By Lemma 5 we know that , so by our choice of we have
By Theorem 11; for the case where , it follows that
for .
Corollary 13. Let , , , and consider sampling according to the joint leverage scores distribution , for which Algorithm 1 produces the sketching matrix . We then have
Proof. If we sample according to the exact distribution , it follows that . By Proposition 12, the statement is immediate.
A drawback of the above results is that the largest singular value of both matrices appear in the sampling complexities. Note though that if we made an analogous assumption to Theorem 2; that , this would not be a concern.
To make a fair comparison with the – guarantee of Theorem 2, let us assume that , and that the sampling complexities for the two algorithms are the same. For Algorithm 1 we would then have for , , and we would get the same probability of error when the accuracy parameters are selected such that . Moreover, what we presented holds true for the product of any pair of distinct matrices and , while Theorem 2 only considers the Gram matrix of .
We conclude this section by restating that the result presented in Theorem 11, is a more general result of the guarantee obtained by the leverage score sampling sketch for a -subspace embedding. Specifically, by considering , we recover the following theorem as a corollary.
Theorem 14 ((DMMS11, Woo14)). The leverage score sampling sketch with approximate sampling distribution according to for which of matrix and , then is a -s.e. of . Specifically, for fixed and , a reduced orthonormal basis of , and , satisfies (9) with probability at least .
Implications on other Approximation Algorithms
In this section, we discuss how the analysis of the proposed AMM through joint leverage scores can be used to derive spectral guarantees for other similar AMM algorithms, and show how it can be utilized for spectral sparsification of ‘intersection graphs’. In Subsection 3.1 we derive a spectral guarantee for –, and in Subsection 3.2 we briefly discuss how our proposed AMM can be utilized by first applying a random projection and then performing uniform random sampling on the transformed matrices’ row pairs. In Subsection 3.3, we discuss the connection to graph sparsification.
CR-MM through Approximate Joint Leverage Scores
A pitfall of our algorithm, is that it requires knowledge of a singular value or QR decomposition for each and , in order to calculate the joint leverage scores. We therefore need operations to compute . Instead, more efficient leverage score approximation algorithms could be used [29, 55, 59], that do not require directly computing a left orthonormal basis of each matrix. This is part of the reason Theorem 11 and Proposition 12 are presented in terms of an approximate distribution . The sampling procedure of the – algorithm on the other hand, can be done efficiently with only additional storage space, by the pass-efficient SELECT algorithm [41 page 13].
In Proposition 16, we quantify an AMM spectral bound for –, by using the distribution of – as a surrogate to . In many practical cases, we empirically observed that the two distributions were relatively close to each other, for a close to 1. What Lemma 15 says is that the oversampling parameter when performing Algorithm 1 with the sampling distribution of – (2.1), is .
Lemma 15. For all , we have .
Proof. Recall that ; for . Consider the reduced QR factorization of , where matches , and is an upper triangular matrix. It follows that for also an upper triangular matrix, and
Similarly, one can show that . By combining the two bounds, we get
which completes the proof.
Proposition 16. Let and . For , , the resulting sketching matrix of – satisfies
Proof. This follows directly by taking ; based on the conclusion of Lemma 15, and using as an approximate distribution to in Theorem 11. Furthermore, the constant lies in , as all its terms are positive; and , are both valid sampling distributions.
Data-Oblivious AMM through Joint Leverage Scores
Recall that the ‘Subsampled Randomized Hadamard Transform’ (SRHT) [31] is comprised of three matrices: a uniform sampling (with replacement) and rescaling matrix of rows, the normalized Hadamard matrix for , and with i.i.d. diagonal Rademacher random entries. The structured sketching matrix of a matrix , flattens the leverage scores of before performing sampling through , the leverage scores of are approximately equal [2, 31].5 Hence, once we apply the randomized transform to , we can sample rows of uniformly at random with replacement (which is done through ) without directly utilizing any information from ; to get an oblivious -subspace embedding sketch .
Now, consider two distinct matrices and . By applying to each of them the above randomized transform we get and , both of which have approximately uniform leverage scores. Hence, the joint leverage scores distribution of the pair is also approximately uniform. From this, the conclusion of Theorem 11 directly applies to the approximate product
where for the index of the sampled pair :
and all other entries of are zero. Furthermore, random Gaussian or orthonormal matrices could also be considered in place of the transform , as these also flatten the leverage scores of the matrices; and additionally provide security of the information stored in and [CMPH22, ZWL08]. The main drawback of these approaches, is that they are slower than the SRHT; which can compute the sketch in time through Fourier methods.
Corollary 17. Let be a random matrix which with high probability flattens the leverage scores of and , i.e. the leverage scores of and are approximately uniform. Then, after applying uniform sampling on the row vector pairs of with rescaling according to from (16) in Algorithm 1, we obtain an estimator
which satisfies (10) with overwhelming probability.
Proof. By the assumption on , we know that with high probability the leverage scores distributions of and of are both approximately uniform, i.e.
for every pair . Consequently, with high probability the joint leverage scores distribution
of the pair is also close to uniform. Let be the misestimation factor which quantifies how far from uniform is the distribution . By directly applying Theorem 11 to the pair with sampling trials, we complete the proof.
Graph Spectral Sparsifiers
A seemingly unrelated object, which has many applications in data science, is the graph Laplacian. Graphs are often used to model phenomena in which there is a flow around a network with high and low conductance regions; e.g. electrical circuits, and are prevalent in many domains of modern computer science and engineering. Due to the large size of the networks considered, a sparser version is preferred for its more efficient storage and processing requirements. This gives rise to the notion of a graph spectral sparsifier [60, 59, 10], which requires that the Laplacian quadratic form of the sparsifier approximates that of the original. In [10], it was shown how can be utilized to produce minimum variance unbiased additive and multiplicative spectral sparsifiers. The AMM algorithm proposed in this paper can be viewed as a generalization of the well-known effective resistance sampling approach, which is the state-of-the-art in spectral sparsification through edge sampling [59].
The state-of-the-art approach to spectral sparsification of a weighted graph is to sample edges according to ‘effective resistances’, which has connections to the leverage scores of the graph’s boundary matrix , for [28, 58, 59]. This approach leads to a nearly-linear time algorithm that produces high-quality sparsifiers, by approximating ’s Laplacian which is defined as the outer-product of its boundary matrix; i.e. . That is, we get a sparser graph with Laplacian .
Definition 18. An -spectral sparsifier for of with Laplacian , is a sketched graph whose Laplacian for all , satisfies with high probability
The benefit of using the bound of Theorem 11, is that it can be applied to directly approximate the intersection of two different graphs on ; say and , which has found applications in areas such as image segmentation. The intersection of these two graphs is defined as , where and for each (w.l.o.g., we assume that the indices of the edges are the same in and ).
We can use AMM through joint leverage scores to directly approximate , for the boundary matrices of the two graphs.6 This results in the Laplacian of a sparsified version of . The techniques of [59] on sampling according to effective resistances do not directly apply to the intersection of graphs without explicitly extracting information from , though through what was proposed in this paper; one can extend the work of [59] to consider ‘joint effective resistances’ defined across the two graphs. The main benefit is that we can sparsify , without constructing it explicitly.
The orientation of an edge , is represented in the incidence vector ; for the standard basis vectors of . Let , for each . Then, the effective resistance of is defined as . Denote the effective resistances of and the corresponding individual leverage scores of by and respectively, for each . Considering the aforementioned distinct matrices and , we can define their joint effective resistances as
for each .
According to the Sparsify algorithm proposed in [59]; in order to obtain a sparse graph of , we sample edges from with replacement according to the distribution
for a total of random sampling trials. Each time is sampled, its weight in the new sparsified graph is increased by . The physical interpretation of the increase in an edge’s weight, is an increase in its conductance.
Corollary 19. Suppose is the intersection of graphs and on ; for which , and consider an that satisfies . Then, the sampling procedure described above with trials, produces an -spectral sparsifier , of the intersection graph . Moreover, we have .
Proof. The proof is a direct application of the results in [59] to the intersection graph , whose Laplacian is . By [59 Theorem 1], [59 Lemma 4] and what was defined in this subsection, the fact that is an -spectral sparsifier of is immediate. The expectation on the number of edges retained in follows from [59 Theorem 12].
Concluding Remarks and Future Work
The main contributions of this paper are the following. First, we connected ideas from two distinct RandNLA algorithms to (i) define a new generalized notion of leverage scores; which when results in the leverage scores of , and (ii) developed an AMM algorithm for which a spectral guarantee was provided. Our algorithm produces a low-rank approximation, which is more efficient to work with in terms of storage and computation. In order to provide a guarantee for our algorithm, we proposed a condition for AMM which is similar to the -subspace embedding property. We also gave a connection to graph sparsifiers, and presented a generalized notion of effective resistances, which is worth investigating further.
Another area which could be benefit from joint leverage score sampling, is that of tensor products and decompositions; where analogous notions could potentially be defined. It would be interesting to see what other optimization problems and applications can benefit from utilizing sampling according to the joint leverage scores distribution. We believe our technique could be incorporated in a distributed optimization setting for least squares regression, in which there are two parties who have distinct features of a dataset, but never share information with each other. Furthermore, the study of leverage scores through information theory and how they relate to the notion of entropy, is worthwhile future work. This may provide insight to what other applications and approximation algorithms could benefit from similar sampling techniques.
References
- [1]Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. Graph Clustering using Effective Resistance. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 41:1–41:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.arxiv.org/abs/1711.06530
- [2]Nir Ailon and Bernard Chazelle. Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In Proceedings of the 38th annual ACM symposium on Theory of computing, pages 557–563, 2006.
- [4]Sepehr Assadi, Michael Kapralov, and Sanjeev Khanna. A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:20, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
- [5]Josh Alman and Virginia Vassilevska Williams. Further Limitations of the Known Approaches for Matrix Multiplication. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), volume 94 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.arxiv.org/abs/1712.07246
- [6]Josh Alman and Virginia Vassilevska Williams. A Refined Laser Method and Faster Matrix Multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539. SIAM, 2021.
- [8]Christos Boutsidis, Anastasios Zou zias, Michael W. Mahoney, and Petros Drineas. Randomized Dimensionality Reduction for k-means Clustering. IEEE Transactions on Information Theory, 61(2):1045–1062, 2014.
- [9]Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu. Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 163–172, 2015.
- [10]Neophytos Charalambides and Alfred Hero. Graph Sparsification by Approximate Matrix Multiplication. In 2023 IEEE Statistical Signal Processing Workshop (SSP), pages 180–184. IEEE, 2023.
- [11]Neophytos Charalambides. Dimensionality Reduction for k-means Clustering. arXiv preprint arXiv:2007.13185, 2020.arxiv.org/abs/2007.13185
- [12]Neophytos Charalambides. Coding Theory and Randomized Sketching for Distributed Optimization. PhD thesis, University of Michigan, 2023.DOI
- [16]Neophytos Charalambides, Hessam Mahdavifar, Mert Pilanci, and Alfred Hero. Iterative Sketching for Secure Coded Regression. arXiv preprint arXiv:2308.04185, 2023.arxiv.org/abs/2308.04185
- [17]Michael B. Cohen, Jelani Nelson, and David P. Woodruff. Optimal Approximate Matrix Product in Terms of Stable Rank. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016.
- [18]Neophytos Charalambides, Mert Pilanci, and Alfred Hero. Weighted Gradient Coding with Leverage Score Sampling. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5215–5219. IEEE, 2020.arxiv.org/abs/2002.02291
- [19]Neophytos Charalambides, Mert Pilanci, and Alfred Hero. Approximate Weighted CR Coded Matrix Multiplication. In ICASSP 2021 - 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5095–5099, 2021.arxiv.org/abs/2011.09709
- [20]Neophytos Charalambides, Mert Pilanci, and Alfred O. Hero. Gradient Coding With Iterative Block Leverage Score Sampling. IEEE Transactions on Information Theory, 70(9):6639–6664, 2024.arxiv.org/abs/2308.03096
- [21]Don Coppersmith and Shmuel Winograd. Matrix multiplication via arithmetic progressions. In Proceedings of the 19th annual ACM symposium on Theory of computing, pages 1–6, 1987.
- [22]Don Coppersmith and Shmuel Winograd. Matrix Multiplication via Arithmetic Progressions. Journal of Symbolic Computation, 9(3):251–280, 1990. Computational algebraic complexity editorial.
- [23]Agniva Chowdhury, Jiasen Yang, and Petros Drineas. Structural conditions for projection-cost preservation via randomized matrix multiplication. Linear Algebra and its Applications, 573:144–165, 2019.arxiv.org/abs/1705.10102
- [24]Petros Drineas and Ravi Kannan. Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. In Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, pages 452–459, 2001.DOI
- [25]Petros Drineas, Ravi Kannan, and Michael W. Mahoney. Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication. SIAM Journal on Computing, 36(1):132–157, 2006.DOI
- [26]Petros Drineas, Ravi Kannan, and Michael W. Mahoney. Fast Monte Carlo Algorithms for Matrices II: Computing a Low-Rank Approximation to a Matrix. SIAM Journal on computing, 36(1):158–183, 2006.DOI
- [27]Petros Drineas and Michael W. Mahoney. Relative-error CUR matrix decompositions. SIAM Journal on Matrix Analysis and Applications, 30(2):844–881, 2008.arxiv.org/abs/0708.3696
- [28]Petros Drineas and Michael W. Mahoney. Effective Resistances, Statistical Leverage, and Applications to Linear Equation Solving. arXiv preprint arXiv:1005.3097, 2010.arxiv.org/abs/1005.3097
- [29]Petros Drineas, Malik Magdon-Ismail, Michael W. Mahoney, and David P. Woodruff. Fast approximation of matrix coherence and statistical leverage. Journal of Machine Learning Research, 13(Dec):3475–3506, 2012.
- [30]Petros Drineas, Michael W. Mahoney, and Shan Muthukrishnan. Sampling Algorithms for ℓ₂ Regression and Applications. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1127–1136, 2006.DOI
- [31]Petros Drineas, Michael W. Mahoney, Shan Muthukrishnan, and Tamás Sarlós. Faster Least Squares Approximation. Numerische mathematik, 117(2):219–249, 2011.
- [32]Ran Duan, Hongxun Wu, and Renfei Zhou. Faster Matrix Multiplication via Asymmetric Hashing. In 2023 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS’23), page to appear. IEEE, 2023.arxiv.org/abs/2210.10173
- [35]Yael Hitron, Nancy Lynch, Cameron Musco, and Merav Parter. Random Sketching, Clustering, and Short-Term Memory in Spiking Neural Networks. In Thomas Vidick, editor, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:31, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.DOI
- [36]Dmitry Kogan and Robert Krauthgamer. Sketching Cuts in Graphs and Hypergraphs. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS ’15, page 367–376, New York, NY, USA, 2015. Association for Computing Machinery.arxiv.org/abs/1409.2391
- [37]Anastasios Kyrillidis, Michail Vlachos, and Anastasios Zouzias. Approximate Matrix Multiplication with Application to Linear Embeddings. In 2014 IEEE International Symposium on Information Theory, pages 2182–2186, 2014.arxiv.org/abs/1403.7683
- [38]François Le Gall. Powers of tensors and fast matrix multiplication. In Proceedings of the 39th international symposium on symbolic and algebraic computation, pages 296–303, 2014.DOI
- [39]Jackie Lok and Elizaveta Rebrova. A subspace constrained randomized kaczmarz method for structure or external knowledge exploitation. Linear Algebra and its Applications, 698:220–260, 2024.arxiv.org/abs/2309.04889
- [41]Michael W. Mahoney. Lecture Notes on Randomized Linear Algebra. arXiv preprint arXiv:1608.04481, 2016.arxiv.org/abs/1608.04481
- [43]Malik Magdon-Ismail. Row Sampling for Matrix Algorithms via a Non-Commutative Bernstein Bound. arXiv preprint arXiv:1008.0587, 2010.
- [44]Youssef Mroueh, Etienne Marcheret, and Vaibahava Goel. Co-occurring directions sketching for approximate matrix multiply. In Artificial Intelligence and Statistics, pages 567–575. PMLR, 2017.arxiv.org/abs/1610.07686
- [45]Ping Ma, Michael W. Mahoney, and Bin Yu. A statistical perspective on algorithmic leveraging. The Journal of Machine Learning Research, 16(1):861–911, 2015.
- [50]Deanna Needell and Joel A. Tropp. Paved with good intentions: analysis of a randomized block Kaczmarz method. Linear Algebra and its Applications, 441:199–221, 2014.DOI
- [51]Urvashi Oswal, Swayambhoo Jain, Kevin S Xu, and Brian Eriksson. Block CUR: Decomposing Matrices Using Groups of Columns. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 360–376. Springer, 2018.arxiv.org/abs/1703.06065
- [52]Roberto Oliveira. Sums of random Hermitian matrices and an inequality by Rudelson. Electronic Communications in Probability, 15:203–212, 2010.arxiv.org/abs/1004.3821
- [53]Rasmus Pagh. Compressed Matrix Multiplication. In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, ITCS ’12, page 442–451, New York, NY, USA, 2012. Association for Computing Machinery.
- [54]Ran Raz. On the Complexity of Matrix Product. In Proceedings of the 34th annual ACM symposium on Theory of computing, pages 144–151, 2002.
- [55]Alessandro Rudi, Daniele Calandriello, Luigi Carratino, and Lorenzo Rosasco. On fast leverage score sampling and optimal learning. In Advances in Neural Information Processing Systems, pages 5672–5682, 2018.arxiv.org/abs/1810.13258
- [56]Benjamin Recht. A Simpler Approach to Matrix Completion. Journal of Machine Learning Research, 12(12), 2011.
- [57]Tamás Sarlós. Improved Approximation Algorithms for Large Matrices via Random Projections. In 2006 47ᵗʰ Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 143–152. IEEE, 2006.DOI
- [58]Daniel A. Spielman. Algorithms, graph theory, and linear equations in Laplacian matrices. In Proceedings of the International Congress of Mathematicians 2010 (ICM 2010) (In 4 Volumes) Vol. I: Plenary Lectures and Ceremonies Vols. II–IV: Invited Lectures, pages 2698–2722. World Scientific, 2010.DOI
- [59]Daniel A. Spielman and Nikhil Srivastava. Graph Sparsification by Effective Resistances. SIAM Journal on Computing, 40(6):1913–1926, 2011.
- [60]Daniel A. Spielman and Shang-Hua Teng. Spectral Sparsification of Graphs. SIAM Journal on Computing, 40(4):981–1025, 2011.
- [61]Volker Strassen. Gaussian elimination is not optimal. Numerische mathematik, 13(4):354–356, 1969.DOI
- [62]Andrew Vioreanu. On the Complexity of Matrix Multiplication. PhD thesis, Yale University, 2012.
- [63]David P. Woodruff. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014.
- [64]Yue Wu. A Note on Random Sampling for Matrix Multiplication. arXiv preprint arXiv:1811.11237, 2019.arxiv.org/abs/1811.11237
- [65]Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. New Bounds for Matrix Multiplication: from Alpha to Omega. arXiv preprint arXiv:2307.07970, 2023.arxiv.org/abs/2307.07970
- [66]Chuhan Yang and Christopher Musco. Efficient Block Approximate Matrix Multiplication. In 31ˢᵗ Annual European Symposium on Algorithms (ESA 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.