Leveraging Well-Conditioned Bases: Streaming & Distributed Summaries in Minkowski p-Norms

07/06/2018
by   Graham Cormode, et al.
0

Work on approximate linear algebra has led to efficient distributed and streaming algorithms for problems such as approximate matrix multiplication, low rank approximation, and regression, primarily for the Euclidean norm ℓ_2. We study other ℓ_p norms, which are more robust for p < 2, and can be used to find outliers for p > 2. Unlike previous algorithms for such norms, we give algorithms that are (1) deterministic, (2) work simultaneously for every p ≥ 1, including p = ∞, and (3) can be implemented in both distributed and streaming environments. We apply our results to ℓ_p-regression, entrywise ℓ_1-low rank approximation, and approximate matrix multiplication.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset