Oblivious Sparse Norm-Approximating Projections (OSNAP) for Fast Numerical Linear Algebra

For any orthonormal basis U in R^{n x d} of a d-dimensional subspace W subset R^n and an OSNAP Pi with s = 1 non-zero per column (the CountSketch / Thorup-Zhang sketch) specified by a pairwise-independent hash h : [n] -> [m] and 4-wise independent signs sigma in {-1, +1}^n, the Gram error matrix S - I = (Pi U)^* (Pi U) - I_d has entries (S - I)_{k,k'} = sum_{r=1}^m sum_{i != j} delta_{r,i} delta_{r,j} sigma_{r,i} sigma_{r,j} u_i^k u_j^{k'} (Eq. 3), diagonal variance E[(S - I)_{k,k}^2] <= 2/m, and off-diagonal variance E[(S - I)_{k,k'}^2] = (1/m)*sum_{i != j} ((u_i^k)^2 (u_j^{k'})^2 + u_i^k u_i^{k'} u_j^k u_j^{k'}) <= 1/m (since sum_{i != j} u_i^k u_i^{k'} u_j^k u_j^{k'} = -sum_i (u_i^k)^2 (u_i^{k'})^2 <= 0 by orthogonality <u^k, u^{k'}> = 0), yielding E||S - I||_F^2 <= (d^2 + d)/m and guaranteeing via Weyl's inequality (Theorem 2) that all singular values of Pi U lie in [1 - varepsilon, 1 + varepsilon] with probability >= 1 - delta for m >= delta^{-1}*(d^2 + d)/(2*varepsilon - varepsilon^2)^2 = O(d^2 / (delta * varepsilon^2)) (Theorem 3).

For general OSNAPs with s > 1, expanding the even trace moment E[tr((S - I)^ell)] (Eq. 6-7) over 3-layered multigraphs G in G with even bond multiplicities in MR(G) and recursively reducing each induced Eulerian dot-product multigraph G_hat via minimum 2-edge cuts into 4-edge-connected components possessing two edge-disjoint spanning trees T_1, T_2 (Theorem 6, Corollary 7, Lemmas 10-11, Eq. 15-19) bounds the graph product by y! * d^{y - w + 1} and E[tr((S - I)^ell)] <= e*d*ell^{4.5} * max_{2 <= b <= ell} (b^3 / s)^{ell - b} * ((b^4 / e)*sqrt(d/m))^b (Eq. 20); this proves that all singular values of Pi U lie in [1 - varepsilon, 1 + varepsilon] with probability >= 1 - delta either for m = Omega(d * log^8(d/delta) / varepsilon^2) and s = Theta(log^3(d/delta) / varepsilon) (Theorem 9) or for m = Omega(d^{1 + gamma} / varepsilon^2) and s = Theta(1/varepsilon) for any constant gamma > 0 using only Omega(log(d/delta))-wise independent hash functions (Theorem 12).

Plugging OSNAPs into randomized numerical linear algebra pipelines yields (1 +- varepsilon) approximation of all n leverage scores of a rank-r matrix A in O_tilde(nnz(A)/varepsilon^2 + r^omega * varepsilon^{-2*omega}) time (Theorem 14), (1 + varepsilon)-approximate least-squares regression min_x ||Ax - b||_2 in O(nnz(A) + d^3 log(d/varepsilon)/varepsilon^2) time via Theorem 3 (Theorem 15) or O(nnz(A)*((log r)^{O(1)} + log(n/varepsilon)) + r^omega*(log r)^{O(1)} + r^2 log(1/varepsilon)) time via Theorem 9 (Theorem 16), and (1 + varepsilon) Frobenius-norm rank-k approximation in O(nnz(A) + O_tilde(n*k^2 + n*k^{omega-1}*varepsilon^{-1-omega} + k^omega*varepsilon^{-2-omega})) or O(nnz(A)*log^{O(1)} k + O_tilde(n*k^{omega-1}*varepsilon^{-1-omega} + k^omega*varepsilon^{-2-omega})) time (Theorems 17-18).