5 papers
Tight Sampling Bounds for Eigenvalue Approximation
William Swartworth, David P. Woodruff
We consider the problem of estimating the spectrum of a symmetric bounded entry (not necessarily PSD) matrix via entrywise sampling. This problem was introduced by [Bhattacharjee,…
Fast Sampling Based Sketches for Tensors
William Swartworth, David P. Woodruff
We introduce a new approach for applying sampling-based sketches to two and three mode tensors. We illustrate our technique to construct sketches for the classical problems of $\el…
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan +3
We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen kno…
Fast and Low-Memory Compressive Sensing Algorithms for Low Tucker-Rank Tensor Approximation from Streamed Measurements
Cullen Haselby, Mark A. Iwen, Deanna Needell +2
In this paper we consider the problem of recovering a low-rank Tucker approximation to a massive tensor based solely on structured random compressive measurements. Crucially, the p…
Optimal Eigenvalue Approximation via Sketching
William Swartworth, David P. Woodruff
Given a symmetric matrix , we show from the simple sketch , where is a Gaussian matrix with rows, that there is a procedure for approximating all eigen…