1.9k citations · 2.8k across the 40 of their papers we have counts for
Showing 2013Show all
2 papers · 1 filter
cs.DS2013★ 94 cited
The Noisy Power Method: A Meta Algorithm with Applications
Moritz Hardt, Eric Price
We provide a new robust convergence analysis of the well-known power method for computing the dominant singular vectors of a matrix that we call the noisy power method. Our result…
cs.DS2013★ 11 cited
Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk +3
We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional sqrt{n} x sqrt{n} grid. Our algorithms are analyzed f…