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.
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.
@cite_18
2093813380
We introduce a new low-distortion embedding of @math into @math ( @math ) called the fast Johnson-Lindenstrauss transform (FJLT). The FJLT is faster than standard random projections and just as easy to implement. It is based upon the preconditioning of a sparse projection matrix with a randomized Fourier transform. Sparse random projections are unsuitable for low-distortion embeddings. We overcome this handicap by exploiting the “Heisenberg principle” of the Fourier transform, i.e., its local-global duality. The FJLT can be used to speed up search algorithms based on low-distortion embeddings in @math and @math . We consider the case of approximate nearest neighbors in @math . We provide a faster algorithm using classical projections, which we then speed up further by plugging in the FJLT. We also give a faster algorithm for searching over the hypercube.