## G. Cormode, C. Dickens, and D. P. Woodruff.
Leveraging well-conditioned bases: Streaming and distributed
summaries in minkowski *p*-norms.
In *International Conference on Machine Learning, (ICML)*,
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 *l*_{2}.
We study other
*l*_{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* infinite, and (3) can be
implemented in both
distributed and streaming environments. We apply our results to *l*_{p}-regression,
entrywise *l*_{1}-low rank approximation,
and approximate matrix multiplication.

[ bib |
poster |
.pdf ]
Back

*This file was generated by
bibtex2html 1.92.*