5 papers · 1 filter
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:…
Faster Algorithms for Schatten-p Low Rank Approximation
Praneeth Kacham, David P. Woodruff
We study algorithms for the Schatten- Low Rank Approximation (LRA) problem. First, we show that by using fast rectangular matrix multiplication algorithms and different block si…
High-Dimensional Geometric Streaming for Nearly Low Rank Data
Hossein Esfandiari, Vahab Mirrokni, Praneeth Kacham +2
We study streaming algorithms for the subspace approximation problem. Given points as an insertion-only stream and a rank parameter , the su…
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 servers, given an arbitrary non-negative function , we study the problem of approximating the sum up…