120 citations · 253 across the 22 of their papers we have counts for
3 papers · 1 filter
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products
Tamas Sarlos, Xingyou Song, David Woodruff +2
Inspired by fast algorithms in natural language processing, we study low rank approximation in the entrywise transformed setting where we want to find a good rank approximation…
A Sparse Johnson--Lindenstrauss Transform
Anirban Dasgupta, Ravi Kumar, Tamás Sarlós
Dimension reduction is a key algorithmic tool with many applications including nearest-neighbor search, compressed sensing and linear algebra in the streaming model. In this work w…
Faster Least Squares Approximation
Petros Drineas, Michael W. Mahoney, S. Muthukrishnan +1
Least squares approximation is a technique to find an approximate solution to a system of linear equations that has no exact solution. In a typical setting, one lets be the num…