Sketching Faster than Dimension Times Update Time

In many applications of sketching, such as distributed computation, the input is available as a fixed vector or matrix rather than as a stream of updates. Let $d$ denote the ambient input dimension. In this offline setting, applying a streaming sketch by simulating coordinate updates can introduce unnecessary overhead: larsen2015time prove $\omega (1)$ update-time lower bounds for several natural turnstile streaming problems. In addition, achieving high success probability, say $1-1/d$, is often done by repetitions that introduce logarithmic overheads. We ask whether, given full access to a vector or matrix, one can apply an optimal-size linear sketch in truly linear time while retaining this high-success-probability regime. We show that this is possible for a range of basic sketching problems by composing standard sketching primitives in new ways. For ${\ell }_2$ estimation and ${\ell }_2$ heavy hitters, we give sketches with optimal sketching dimension, success probability at least $1-1/d$, and truly linear application time. We further combine this construction with ExpanderSketch to obtain fast decoding, and extend the same ideas to rank-one tensor sketches and ${\ell }_2$ sampling. We also obtain fast sketches for general ${\ell }_p$ estimation. For $p>2$, we use our heavy-hitters primitive to obtain a linear-time $F_p$ moment sketch with near-optimal $\tilde{O}(d^{1-2/p})$ dependence on dimension. Finally, we apply the same composition-and-selection template to linear regression and low-rank approximation. In the natural tall and wide regimes, respectively, these sketches have optimal or near-optimal sketch size and can be applied in input-sparsity time. Since all of our sketches are linear, the results apply directly in the coordinator model for distributed computation.