4 papers
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…
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 points in , the goal of the {\em subspace approximation} pr…
Approximating the Top Eigenvector in Random Order Streams
Praneeth Kacham, David P. Woodruff
When rows of an matrix are given in a stream, we study algorithms for approximating the top eigenvector of the matrix (equivalently, the top right singula…
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 matrices and , and a non-negative function , define the matrix as follows:…