4 citations · 15 across the 22 of their papers we have counts for
23 papers · 1 filter
A Tight Analysis of Khatri-Rao Oblivious Subspace Embeddings
Lorenzo Beretta, Cameron Musco
We study random sketching matrices with Khatri-Rao structure. In particular, we consider the Khatri-Rao product (i.e., column-wise tensor product) $A_1\odot\cdots\odot A_d \in \mat…
Sublinear Time Eigenvector Approximation via Column Sampling
Rajarshi Bhattacharjee, Cameron Musco, Dominic Rutkowski
We study sublinear time sampling methods for approximating the outlying eigenvectors of large matrices. Our main result is an algorithm that uniformly samples just $\tilde{O}(\log…
Fast Length-Squared Sampling for Positive-Semidefinite Matrices
Rajarshi Bhattacharjee, Ethan N. Epperly, Cameron Musco +1
We describe a simple rejection-sampling-based algorithm to perform length-squared sampling on an positive-semidefinite (psd) matrix: that is, to sample a column with p…
Sublinear Time Low-Rank Approximation of Hankel Matrices
Michael Kapralov, Cameron Musco, Kshiteej Sheth
Hankel matrices are an important class of highly-structured matrices, arising across computational mathematics, engineering, and theoretical computer science. It is well-known that…
A Note on Fine-Grained Quantum Reductions for Linear Algebraic Problems
Kyle Doney, Cameron Musco
We observe that any time algorithm (quantum or classical) for several central linear algebraic problems, such as computing , , or for an $n \t…
Query Efficient Structured Matrix Learning
Noah Amsel, Pratyush Avi, Tyler Chen +5
We study the problem of learning a structured approximation (low-rank, sparse, banded, etc.) to an unknown matrix given access to matrix-vector product (matvec) queries of the…