We design a new distribution over @math matrices @math so that for any fixed @math matrix @math of rank @math , with probability at least 9 10, @math simultaneously for all @math . Such a matrix @math is called a . Furthermore, @math can be computed in @math time, where @math is the number of non-zero entries of @math . This improves over all previous subspace embeddings, which required at least @math time to achieve this property. We call our matrices @math . Using our sparse embedding matrices, we obtain the fastest known algorithms for @math -approximation for overconstrained least-squares regression, low-rank approximation, approximating all leverage scores, and @math -regression. The leading order term in the time complexity of our algorithms is @math or @math . We optimize the low-order @math terms in our running times (or for rank- @math approximation, the @math term), and show various tradeoffs. For instance, we also use our methods to design new preconditioners that improve the dependence on @math in least squares regression to @math . Finally, we provide preliminary experimental results which suggest that our algorithms are competitive in practice.
@cite_18: Let X be a data matrix of rank , representing n points in d-dimensional space. The linear support vector machine constructs a hyperplane separator that maximizes the 1norm soft margin. We develop a new oblivious dimension reduction technique which is precomputed and can be applied to any input matrix X. We prove that, with high probability, the margin and minimum enclosing ball in the feature space are preserved to within -relative error, ensuring comparable generalization as in the original space. We present extensive experiments with real and synthetic data to support our theory.
Paul, Boutsidis, Magdon-Ismail, and Drineas @cite_18 implemented our subspace embeddings and found that in the TechTC-300 matrices, a collection of 300 sparse matrices of document-term data, with an average of 150 to 200 rows and 15,000 columns, our subspace embeddings as used for the projection step in their SVM classifier are about 20 times faster than the Fast JL Transform, while maintaining the same classification accuracy. Despite this large improvement in the time for projecting the data, further research is needed for SVM classification, as the JL Transform empirically possesses additional properties important for SVM which make it faster to classify the projected data, even though the time to project the data using our method is faster.