170 citations · 876 across the 146 of their papers we have counts for
12 papers · 2 filters
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…
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 $…
Algorithms for Low Rank Approximation
Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar +3
We consider the problem of approximating a given matrix by a low-rank matrix so as to minimize the entrywise -approximation error, for any ; the case is t…
Matrix Completion and Related Problems via Strong Duality
Maria-Florina Balcan, Yingyu Liang, David P. Woodruff +1
This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. Thi…
Relative Error Tensor Low Rank Approximation
Zhao Song, David P. Woodruff, Peilin Zhong
We consider relative error low rank approximation of with respect to the Frobenius norm: given an order- tensor , output a rank-$…
Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
Cameron Musco, Praneeth Netrapalli, Aaron Sidford +2
Understanding the singular value spectrum of a matrix is a fundamental task in countless applications. In matrix multiplication time, it is possible…
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
Cameron Musco, David P. Woodruff
We show how to compute a relative-error low-rank approximation to any positive semidefinite (PSD) matrix in sublinear time, i.e., for any PSD matrix , in $\tilde O(…
Embeddings of Schatten Norms with Applications to Data Streams
Yi Li, David P. Woodruff
Given an matrix , its Schatten- norm, , is defined as , where is the $i…
Communication-Optimal Distributed Clustering
Jiecao Chen, He Sun, David P. Woodruff +1
Clustering large datasets is a fundamental problem with a number of applications in machine learning. Data is often collected on different sites and clustering needs to be performe…