13 citations · 18 across the 6 of their papers we have counts for
5 papers · 1 filter
Faster Spectral Density Estimation and Sparsification in the Nuclear Norm
Yujia Jin, Ishani Karmarkar, Christopher Musco +2
We consider the problem of estimating the spectral density of the normalized adjacency matrix of an -node undirected graph. We provide a randomized algorithm that, with $O(nε^{-…
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…
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…
Dimensionality Reduction for k-Means Clustering and Low Rank Approximation
Michael B. Cohen, Sam Elder, Cameron Musco +2
We show how to approximate a data matrix with a much smaller sketch that can be used to solve a general class of constrained k-rank approximation p…
Single Pass Spectral Sparsification in Dynamic Streams
Michael Kapralov, Yin Tat Lee, Cameron Musco +2
We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions…