CountSketch Input-Sparsity Subspace Embedding and Regression

CountSketch Input-Sparsity Subspace Embedding and Regression is an oblivious sparse random projection and numerical linear algebra framework introduced by Clarkson and Woodruff (2013, 2017) that constructs an O(n)-column, t-row sketching matrix S = Phi D in R^{t x n} with exactly ONE nonzero entry per column (S_{h(i), i} = sigma_i in {-1, +1}, where h: [n] -> [t] and sigma: [n] -> {-1, +1} are random hash and sign maps) so that S A can be computed in true input-sparsity time O(nnz(A)) for any matrix A in R^{n x d}, where nnz(A) is the number of nonzero entries of A. Theorem 2.3 and Lemma 2.5 prove that for t = O(d^2 / epsilon^2) (or t = O(k^2 / epsilon^2) for a k-dimensional subspace), S is a (1 +/- epsilon)-l_2 subspace embedding satisfying ||S A x||_2 = (1 +/- epsilon)||A x||_2 simultaneously for all x in R^d by decomposing the basis U of range(A) into heavy rows (||u_i||_2^2 >= tau, which are isolated into distinct hash buckets without collision and preserved isometrically) and light rows (bounded via high-moment trace inequalities), yielding O(nnz(A) + d^3 epsilon^{-2} log(d/epsilon)) algorithms for (1+epsilon)-approximate overconstrained least-squares regression (Theorem 2.6) and O(nnz(A) + n poly(k/epsilon)) low-rank matrix approximation.