Recently a deterministic method, frequent directions (FD) is proposed to solve the high dimensional low rank approximation problem. It works well in practice, but experiences high computational cost. In this paper, we establish a fast frequent directions algorithm for the low rank approximation problem, which implants a randomized algorithm, sparse subspace embedding (SpEmb) in FD. This new algorithm makes use of FD's natural block structure and sends more information through SpEmb to each block in FD. We prove that our new algorithm produces a good low rank approximation with a sketch of size linear on the rank approximated. Its effectiveness and efficiency are demonstrated by the experimental results on both synthetic and real world datasets, as well as applications in network analysis.
Since its introduction by Clarkson and Woodruff @cite_28 , SpEmb has received great attention due to its efficient time complexity. It has been extensively used as a randomization technique to solve numerical linear algebraic problems, here we look at its application on low rank approximation.
@cite_28
2101043704
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 = O(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,