Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors
Sandeep Silwal, David P. Woodruff, Qiuyi Zhang
We study beyond worst-case dimensionality reduction for -sparse vectors. Our work is divided into two parts, each focusing on a different facet of beyond worst-case analysis: We…
cs.DS2023
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…