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


Charlie Dickens, Graham Cormode, David Woodruff ;
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1243-1251, 2018.


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 $\ell_2$. We study other $\ell_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 \geq 1$, including $p = \infty$, and (3) can be implemented in both distributed and streaming environments. We study $\ell_p$-regression, entrywise $\ell_p$-low rank approximation, and versions of approximate matrix multiplication.

Related Material