170 citations · 876 across the 146 of their papers we have counts for
19 papers · 1 filter
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes
Quang Minh Hoang, Trong Nghia Hoang, Hai Pham +1
We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained f…
Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators
David P. Woodruff, Samson Zhou
In the adversarially robust streaming model, a stream of elements is presented to an algorithm and is allowed to depend on the output of the algorithm at earlier times during the s…
Reduced-Rank Regression with Operator Norm Error
Praneeth Kacham, David P. Woodruff
A common data analysis task is the reduced-rank regression problem: where and $B \in \mathbb{R}^{n \times d…
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra
Nadiia Chepurko, Kenneth L. Clarkson, Lior Horesh +2
We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression that are comparable to their quantum analogues. De…
Hutch++: Optimal Stochastic Trace Estimation
Raphael A. Meyer, Cameron Musco, Christopher Musco +1
We study the problem of estimating the trace of a matrix that can only be accessed through matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which…
WOR and 's: Sketches for -Sampling Without Replacement
Edith Cohen, Rasmus Pagh, David P. Woodruff
Weighted sampling is a fundamental tool in data analysis and machine learning pipelines. Samples are used for efficient estimation of statistics or as sparse representations of the…