  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 apply our results to
$\ell_p$-regression, entrywise $\ell_1$-low rank approximation, and approximate
matrix multiplication.
