Before revision:  For the important case of p = 1, which corresponds to the more "robust" nuclear norm, we obtain O(nnz(A) + n \cdot poly(k/\epsilon)) time, which was previously only known for the Frobenius norm (p = 2).
After revision:  For the important case of p = 1, which corresponds to the more "robust" nuclear norm, we obtain O(nnz(A) + m \cdot poly(k/\epsilon)) time, which was previously only known for the Frobenius norm (p = 2).