170 citations · 876 across the 146 of their papers we have counts for
14 papers · 1 filter
Sketching for Kronecker Product Regression and P-splines
Huaian Diao, Zhao Song, Wen Sun +1
TensorSketch is an oblivious linear sketch introduced in Pagh'13 and later used in Pham, Pagh'13 in the context of SVMs for polynomial kernels. It was shown in Avron, Nguyen, Woodr…
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?
Cameron Musco, David P. Woodruff
Low-rank approximation is a common tool used to accelerate kernel methods: the kernel matrix is approximated via a rank- matrix which can be stored i…
Approximation Algorithms for -Low Rank Approximation
Karl Bringmann, Pavel Kolev, David P. Woodruff
We study the -Low Rank Approximation Problem, where the goal is, given an matrix , to output a rank- matrix for which is minimized. Her…
Near Optimal Sketching of Low-Rank Tensor Regression
Jarvis Haupt, Xingguo Li, David P. Woodruff
We study the least squares regression problem \begin{align*} \min_{Θ\in \mathcal{S}_{\odot D,R}} \|AΘ-b\|_2, \end{align*} where is the set of for whic…
On Low-Risk Heavy Hitters and Sparse Recovery Schemes
Yi Li, Vasileios Nakos, David Woodruff
We study the heavy hitters and related sparse recovery problems in the low-failure probability regime. This regime is not well-understood, and has only been studied for non-adaptiv…
Fast Regression with an Guarantee
Eric Price, Zhao Song, David P. Woodruff
Sketching has emerged as a powerful technique for speeding up problems in numerical linear algebra, such as regression. In the overconstrained regression problem, one is given an $…