David P. Woodruff

activity

20082023

most citedFast approximation of matrix coherence and statistical leverage

170 citations · 876 across the 146 of their papers we have counts for

collaborators

Showing 2018Show all

18 papers · 1 filter

cs.DS2018★ 11 cited

Learning Two Layer Rectified Neural Networks in Polynomial Time

Ainesh Bakshi, Rajesh Jayaram, David P. Woodruff

Consider the following fundamental learning problem: given input examples $x \in R^{d}$ and their vector-valued labels, as defined by an underlying generative neural network…

cs.DS2018★ 6 cited

Towards a Zero-One Law for Column Subset Selection

Zhao Song, David P. Woodruff, Peilin Zhong

There are a number of approximation algorithms for NP-hard versions of low rank approximation, such as finding a rank- $k$ matrix $B$ minimizing the sum of absolute values of differ…

cs.DS2018

Testing Matrix Rank, Optimally

Maria-Florina Balcan, Yi Li, David P. Woodruff +1

We show that for the problem of testing if a matrix $A \in F^{n \times n}$ has rank at most $d$ , or requires changing an $ε$ -fraction of entries to have rank at most $d$ , there is…

cs.DS2018★ 11 cited

Sublinear Time Low-Rank Approximation of Distance Matrices

Ainesh Bakshi, David P. Woodruff

Let $P = {p_{1}, p_{2}, \dots p_{n}}$ and $Q = {q_{1}, q_{2} \dots q_{m}}$ be two point sets in an arbitrary metric space. Let $A$ represent the $m \times n$ …

cs.DS2018★ 4 cited

Strong Coresets for k-Median and Subspace Approximation: Goodbye Dimension

Christian Sohler, David P. Woodruff

We obtain the first strong coresets for the $k$ -median and subspace approximation problems with sum of distances objective function, on $n$ points in $d$ dimensions, with a number…

cs.DS2018

Perfect $L_{p}$ Sampling in a Data Stream

Rajesh Jayaram, David P. Woodruff

In this paper, we resolve the one-pass space complexity of $L_{p}$ sampling for $p \in (0, 2)$ . Given a stream of updates (insertions and deletions) to the coordinates of an underlyin…