  We give a simple algorithm to efficiently sample the rows of a matrix while
preserving the p-norms of its product with vectors. Given an $n$-by-$d$ matrix
$\boldsymbol{\mathit{A}}$, we find with high probability and in input sparsity
time an $\boldsymbol{\mathit{A}}'$ consisting of about $d \log{d}$ rescaled
rows of $\boldsymbol{\mathit{A}}$ such that $\| \boldsymbol{\mathit{A}}
\boldsymbol{\mathit{x}} \|_1$ is close to $\| \boldsymbol{\mathit{A}}'
\boldsymbol{\mathit{x}} \|_1$ for all vectors $\boldsymbol{\mathit{x}}$. We
also show similar results for all $\ell_p$ that give nearly optimal sample
bounds in input sparsity time. Our results are based on sampling by "Lewis
weights", which can be viewed as statistical leverage scores of a reweighted
matrix. We also give an elementary proof of the guarantees of this sampling
process for $\ell_1$.
