93 citations · 426 across the 43 of their papers we have counts for
53 papers
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…
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…
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…
Algorithm-agnostic low-rank approximation of operator monotone matrix functions
David Persson, Raphael A. Meyer, Christopher Musco
Low-rank approximation of a matrix function, , is an important task in computational mathematics. Most methods require direct access to , which is often considerably mo…
Structured Semidefinite Programming for Recovering Structured Preconditioners
Arun Jambulapati, Jerry Li, Christopher Musco +3
We develop a general framework for finding approximately-optimal preconditioners for solving linear systems. Leveraging this framework we obtain improved runtimes for fundamental p…
Simple Analysis of Priority Sampling
Majid Daliri, Juliana Freire, Christopher Musco +2
We prove a tight upper bound on the variance of the priority sampling method (aka sequential Poisson sampling). Our proof is significantly shorter and simpler than the original pro…
Moments, Random Walks, and Limits for Spectrum Approximation
Yujia Jin, Christopher Musco, Aaron Sidford +1
We study lower bounds for the problem of approximating a one dimensional distribution given (noisy) measurements of its moments. We show that there are distributions on th…
Dimensionality Reduction for General KDE Mode Finding
Xinyu Luo, Christopher Musco, Cas Widdershoven
Finding the mode of a high dimensional probability distribution is a fundamental algorithmic problem in statistics and data analysis. There has been particular interest in effi…
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 …
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…
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…
Active Learning for Single Neuron Models with Lipschitz Non-Linearities
Aarshvi Gajjar, Chinmay Hegde, Christopher Musco
We consider the problem of active learning for single neuron models, also sometimes called ``ridge functions'', in the agnostic setting (under adversarial label noise). Such models…
A Tight Analysis of Hutchinson's Diagonal Estimator
Prathamesh Dharangutte, Christopher Musco
Let be a matrix with diagonal and let be with its diagonal set to all zeros. We sho…
Fast Regression for Structured Inputs
Raphael A. Meyer, Cameron Musco, Christopher Musco +2
We study the regression problem, which requires finding that minimizes for a matrix $\mathbf{A}\in\mat…
Low-memory Krylov subspace methods for optimal rational matrix function approximation
Tyler Chen, Anne Greenbaum, Cameron Musco +1
We describe a Lanczos-based algorithm for approximating the product of a rational matrix function with a vector. This algorithm, which we call the Lanczos method for optimal ration…
Active Linear Regression for Norms and Beyond
Cameron Musco, Christopher Musco, David P. Woodruff +1
We study active sampling algorithms for linear regression, which aim to query only a few entries of a target vector and output a near minimizer to $\min_{x\in\mat…
Dynamic Trace Estimation
Prathamesh Dharangutte, Christopher Musco
We study a dynamic version of the implicit trace estimation problem. Given access to an oracle for computing matrix-vector multiplications with a dynamically changing matrix A, our…
How to Quantify Polarization in Models of Opinion Dynamics
Christopher Musco, Indu Ramesh, Johan Ugander +1
It is widely believed that society is becoming increasingly polarized around important issues, a dynamic that does not align with common mathematical models of opinion formation in…
Error bounds for Lanczos-based matrix function approximation
Tyler Chen, Anne Greenbaum, Cameron Musco +1
We analyze the Lanczos method for matrix function approximation (Lanczos-FA), an iterative algorithm for computing when is a Hermitian matri…
Correlation Sketches for Approximate Join-Correlation Queries
Aécio Santos, Aline Bessa, Fernando Chirigati +2
The increasing availability of structured datasets, from Web tables and open-data portals to enterprise data, opens up opportunities~to enrich analytics and improve machine learnin…