170 citations · 876 across the 146 of their papers we have counts for
23 papers · 1 filter
Sublinear Time Numerical Linear Algebra for Structured Matrices
Xiaofei Shi, David P. Woodruff
We show how to solve a number of problems in numerical linear algebra, such as least squares regression, -regression for any , low rank approximation, and kernel…
Dimensionality Reduction for Sum-of-Distances Metric
Zhili Feng, Praneeth Kacham, David P. Woodruff
We give a dimensionality reduction procedure to approximate the sum of distances of a given set of points in to any "shape" that lies in a -dimensional subspace. Here,…
Robust and Sample Optimal Algorithms for PSD Low-Rank Approximation
Ainesh Bakshi, Nadiia Chepurko, David P. Woodruff
Recently, Musco and Woodruff (FOCS, 2017) showed that given an positive semidefinite (PSD) matrix , it is possible to compute a -approximate relative-error l…
Pseudo-deterministic Streaming
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty +1
A pseudo-deterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Clas…
Regularized Weighted Low Rank Approximation
Frank Ban, David Woodruff, Qiuyi Zhang
The classical low rank approximation problem is to find a rank matrix (where has columns and has rows) that minimizes the Frobenius norm of . Altho…
Graph Spanners in the Message-Passing Model
Manuel Fernandez, David P. Woodruff, Taisuke Yasuda
Graph spanners are sparse subgraphs which approximately preserve all pairwise shortest-path distances in an input graph. The notion of approximation can be additive, multiplicative…