An Improved Frequent Directions Algorithm for Low-Rank Approximation via
  Block Krylov Iteration
  Frequent Directions, as a deterministic matrix sketching technique, has been
proposed for tackling low-rank approximation problems. This method has a high
degree of accuracy and practicality, but experiences a lot of computational
cost for large-scale data. Several recent works on the randomized version of
Frequent Directions greatly improve the computational efficiency, but
unfortunately sacrifice some precision. To remedy such issue, this paper aims
to find a more accurate projection subspace to further improve the efficiency
and effectiveness of the existing Frequent Directions techniques. Specifically,
by utilizing the power of Block Krylov Iteration and random projection
technique, this paper presents a fast and accurate Frequent Directions
algorithm named as r-BKIFD. The rigorous theoretical analysis shows that the
proposed r-BKIFD has a comparable error bound with original Frequent
Directions, and the approximation error can be arbitrarily small when the
number of iterations is chosen appropriately. Extensive experimental results on
both synthetic and real data further demonstrate the superiority of r-BKIFD
over several popular Frequent Directions algorithms, both in terms of
computational efficiency and accuracy.
