6 papers · 1 filter
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…
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…
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…
Stability of the Lanczos Method for Matrix Function Approximation
Cameron Musco, Christopher Musco, Aaron Sidford
The ubiquitous Lanczos method can approximate for any symmetric matrix , vector , and function . In exact arithmetic, the method's error after ite…
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…
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…