2 citations · 2 across the 9 of their papers we have counts for
10 papers · 1 filter
John Ellipsoids via Lazy Updates
David P. Woodruff, Taisuke Yasuda
We give a faster algorithm for computing an approximate John ellipsoid around points in dimensions. The best known prior algorithms are based on repeatedly computing the le…
Ridge Leverage Score Sampling for Subspace Approximation
David P. Woodruff, Taisuke Yasuda
The subspace approximation problem is an NP-hard low rank approximation problem that generalizes the median hyperplane (), principal component analysis (), a…
Coresets for Multiple Regression
David P. Woodruff, Taisuke Yasuda
A coreset of a dataset with examples and features is a weighted subset of examples that is sufficient for solving downstream data analytic tasks. Nearly optimal constructio…
Reweighted Solutions for Weighted Low Rank Approximation
David P. Woodruff, Taisuke Yasuda
Weighted low rank approximation (WLRA) is an important yet computationally challenging primitive with applications ranging from statistical analysis, model compression, and signal…
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming
Gregory Dexter, Petros Drineas, David P. Woodruff +1
Sketching algorithms have recently proven to be a powerful approach both for designing low-space streaming algorithms as well as fast polynomial time approximation schemes (PTAS).…
Improved Algorithms for Low Rank Approximation from Sparsity
David P. Woodruff, Taisuke Yasuda
We overcome two major bottlenecks in the study of low rank approximation by assuming the low rank factors themselves are sparse. Specifically, (1) for low rank approximation with s…