93 citations · 388 across the 44 of their papers we have counts for
58 papers
CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs
Meher Chaitanya, Cameron Musco, Aristides Gionis
Graph-data workloads such as diffusion estimation, ranking, semi-supervised learning, and network optimization often solve many Laplacian or symmetric diagonally dominant M-matrix…
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…
Spectral density estimation for normal matrices
Cameron Musco, Christopher Musco, Rikhav Shah +2
The spectral density estimation problem asks for an algorithm that, given an matrix , outputs a probability measure that is a good approximation to the uniform distr…
Private Adaptive Covariance Estimation via Gaussian Graphical Models
Cecilia Ferrando, Miguel Fuentes, Brett Mullins +2
We propose PACE-GGM, a data-adaptive differentially private method for covariance estimation that concentrates its privacy budget on the most informative entries of the empirical c…
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…
Distance Adaptive Beam Search for Provably Accurate Graph-Based Nearest Neighbor Search
Yousef Al-Jazzazi, Haya Diwan, Jinrui Gou +3
Nearest neighbor search is central in machine learning, information retrieval, and databases. For high-dimensional datasets, graph-based methods such as HNSW, DiskANN, and NSG have…
Quasi-optimal hierarchically semi-separable matrix approximation
Noah Amsel, Tyler Chen, Feyza Duman Keles +4
We present a randomized algorithm for producing a quasi-optimal hierarchically semi-separable (HSS) approximation to an matrix using only matrix-vector products wit…
Improved Spectral Density Estimation via Explicit and Implicit Deflation
Rajarshi Bhattacharjee, Rajesh Jayaram, Cameron Musco +2
We study algorithms for approximating the spectral density of a symmetric matrix that is accessed through matrix-vector product queries. By combining a previously studied Cheby…
Sharper Bounds for Chebyshev Moment Matching, with Applications
Cameron Musco, Christopher Musco, Lucas Rosenblatt +1
We study the problem of approximately recovering a probability distribution given noisy measurements of its Chebyshev polynomial moments. This problem arises broadly across algorit…
Near-optimal hierarchical matrix approximation from matrix-vector products
Tyler Chen, Feyza Duman Keles, Diana Halikias +3
We describe a randomized algorithm for producing a near-optimal hierarchical off-diagonal low-rank (HODLR) approximation to an matrix , accessible only thou…
Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits
Haya Diwan, Jinrui Gou, Cameron Musco +2
There has been significant recent interest in graph-based nearest neighbor search methods, many of which are centered on the construction of navigable graphs over high-dimensional…
Sublinear Time Low-Rank Approximation of Toeplitz Matrices
Cameron Musco, Kshiteej Sheth
We present a sublinear time algorithm for computing a near optimal low-rank approximation to any positive semidefinite (PSD) Toeplitz matrix , given no…
Fixed-sparsity matrix approximation from matrix-vector products
Noah Amsel, Tyler Chen, Feyza Duman Keles +3
We study the problem of approximating a matrix with a matrix that has a fixed sparsity pattern (e.g., diagonal, banded, etc.), when is accessed only by ma…
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco +3
Let satisfy , where is the all ones matrix and is the spectral norm. It is well-kno…
On the Unreasonable Effectiveness of Single Vector Krylov Methods for Low-Rank Approximation
Raphael A. Meyer, Cameron Musco, Christopher Musco
Krylov subspace methods are a ubiquitous tool for computing near-optimal rank approximations of large matrices. While "large block" Krylov methods with block size at least …
No-regret Algorithms for Fair Resource Allocation
Abhishek Sinha, Ativ Joshi, Rajarshi Bhattacharjee +2
We consider a fair resource allocation problem in the no-regret setting against an unrestricted adversary. The objective is to allocate resources equitably among several agents in…
Nearly Optimal Approximation of Matrix Functions by the Lanczos Method
Noah Amsel, Tyler Chen, Anne Greenbaum +2
Approximating the action of a matrix function on a vector is an increasingly important primitive in machine learning, data science, and statistics, wit…
Weighted Minwise Hashing Beats Linear Sketching for Inner Product Estimation
Aline Bessa, Majid Daliri, Juliana Freire +4
We present a new approach for computing compact sketches that can be used to approximate the inner product between pairs of high-dimensional vectors. Based on the Weighted MinHash…
Toeplitz Low-Rank Approximation with Sublinear Query Complexity
Michael Kapralov, Hannah Lawrence, Mikhail Makarov +2
We present a sublinear query algorithm for outputting a near-optimal low-rank approximation to any positive semidefinite Toeplitz matrix . In particu…
Near-Linear Sample Complexity for Polynomial Regression
Raphael A. Meyer, Cameron Musco, Christopher Musco +2
We study polynomial regression. Given query access to a function , the goal is to find a degree polynomial such that, for a giv…