OSNAP: Faster numerical linear algebra algorithms via sparser subspace embeddings

Abstract

An "oblivious subspace embedding (OSE)" given some parameters eps,d is a distribution D over matrices B in R^{m x n} such that for any linear subspace W in R^n with dim(W) = d it holds that Pr_{B ~ D}(forall x in W ||B x||_2 in (1 +/- eps)||x||_2) > 2/3 We show an OSE exists with m = O(d^2/eps^2) and where every B in the support of D has exactly s=1 non-zero entries per column. This improves previously best known bound in [Clarkson-Woodruff, arXiv:1207.6365]. Our quadratic dependence on d is optimal for any OSE with s=1 [Nelson-Nguyen, 2012]. We also give two OSE's, which we call Oblivious Sparse Norm-Approximating Projections (OSNAPs), that both allow the parameter settings m = Õ(d/eps^2) and s = polylog(d)/eps, or m = O(d^{1+gamma}/eps^2) and s=O(1/eps) for any constant gamma>0. This m is nearly optimal since m >= d is required simply to no non-zero vector of W lands in the kernel of B. These are the first constructions with m=o(d^2) to have s=o(d). In fact, our OSNAPs are nothing more than the sparse Johnson-Lindenstrauss matrices of [Kane-Nelson, SODA 2012]. Our analyses all yield OSE's that are sampled using either O(1)-wise or O(log d)-wise independent hash functions, which provides some efficiency advantages over previous work for turnstile streaming applications. Our main result is essentially a Bai-Yin type theorem in random matrix theory and is likely to be of independent interest: i.e. we show that for any U in R^{n x d} with orthonormal columns and random sparse B, all singular values of BU lie in [1-eps, 1+eps] with good probability. Plugging OSNAPs into known algorithms for numerical linear algebra problems such as approximate least squares regression, low rank approximation, and approximating leverage scores implies faster algorithms for all these problems.

References in corpus (6)

• Fast approximation of matrix coherence and statistical leverage
• Randomized algorithms for matrices and data
• A Derandomized Sparse Johnson-Lindenstrauss Transform
• Low Rank Approximation and Regression in Input Sparsity Time
• Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform
• Sparsity Lower Bounds for Dimensionality Reducing Maps

Cited by in corpus (13)

• Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds
• Sketched Ridge Regression: Optimization Perspective, Statistical Perspective, and Model Averaging
• Towards More Efficient SPSD Matrix Approximation and CUR Matrix Decomposition
• Low-distortion Subspace Embeddings in Input-sparsity Time and Applications to Robust Linear Regression
• Principal Component Analysis and Higher Correlations for Distributed Data
• Sublinear Time Low-Rank Approximation of Distance Matrices
• ${\ell }_p$ Row Sampling by Lewis Weights
• Efficient Structured Matrix Recovery and Nearly-Linear Time Algorithms for Solving Inverse Symmetric $M$-Matrices
• Sparsity Lower Bounds for Dimensionality Reducing Maps
• Optimal Principal Component Analysis in Distributed and Streaming Models
• Sketching for Kronecker Product Regression and P-splines
• Efficient Non-oblivious Randomized Reduction for Risk Minimization with Improved Excess Risk Guarantee
• Sketching Transformed Matrices with Applications to Natural Language Processing