David P. Woodruff

activity

20232026

collaborators

8 papers

cs.DS2026

SVD Provably Denoises Nearest Neighbor Data

Ravindran Kannan, Kijun Shin, David Woodruff

We study the Nearest Neighbor Search (NNS) problem in a high-dimensional setting where data lies in a low-dimensional subspace and is corrupted by Gaussian noise. Specifically, we…

cs.DS2025

Guessing Efficiently for Constrained Subspace Approximation

Aditya Bhaskara, Sepideh Mahabadi, Madhusudhan Reddy Pittu +2

In this paper we study constrained subspace approximation problem. Given a set of $n$ points ${a_{1}, \dots, a_{n}}$ in $R^{d}$ , the goal of the {\em subspace approximation} pr…

cs.DS2024

Approximating the Top Eigenvector in Random Order Streams

Praneeth Kacham, David P. Woodruff

When rows of an $n \times d$ matrix $A$ are given in a stream, we study algorithms for approximating the top eigenvector of the matrix $A^{T} A$ (equivalently, the top right singula…

cs.LG2024

LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions

Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham +1

A central problem related to transformers can be stated as follows: given two $n \times d$ matrices $Q$ and $K$ , and a non-negative function $f$ , define the matrix $A$ as follows:…

cs.DS2024

Faster Algorithms for Schatten-p Low Rank Approximation

Praneeth Kacham, David P. Woodruff

We study algorithms for the Schatten- $p$ Low Rank Approximation (LRA) problem. First, we show that by using fast rectangular matrix multiplication algorithms and different block si…

cs.DS2024

High-Dimensional Geometric Streaming for Nearly Low Rank Data

Hossein Esfandiari, Vahab Mirrokni, Praneeth Kacham +2

We study streaming algorithms for the $ℓ_{p}$ subspace approximation problem. Given points $a_{1}, \dots, a_{n}$ as an insertion-only stream and a rank parameter $k$ , the $ℓ_{p}$ su…

cs.DS2024

Optimal Communication for Classic Functions in the Coordinator Model and Beyond

Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni +2

In the coordinator model of communication with $s$ servers, given an arbitrary non-negative function $f$ , we study the problem of approximating the sum $\sum_{i \in [n]} f (x_{i})$ up…

cs.DS2023

Lower Bounds on Adaptive Sensing for Matrix Recovery

Praneeth Kacham, David P Woodruff

We study lower bounds on adaptive sensing algorithms for recovering low rank matrices using linear measurements. Given an $n \times n$ matrix $A$ , a general linear measurement $S(A…