4 papers
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…