# An Improved Frequent Directions Algorithm for Low-Rank Approximation via Block Krylov Iteration

arXiv: https://arxiv.org/abs/2109.11703 · HTML: https://mlsanity.com/paper/2109.11703/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 76 references that are in the map.
- First posted on arXiv 24 Sep 2021.

## Builds on (most cited first, 12 of 12)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition](https://mlsanity.com/paper/1504.05477/) (2015)
- [Frequent Directions : Simple and Deterministic Matrix Sketching](https://mlsanity.com/paper/1501.01711/) (2015)
- [Practical sketching algorithms for low-rank matrix approximation](https://mlsanity.com/paper/1609.00048/) (2016)
- [Efficient Second Order Online Learning by Sketching](https://mlsanity.com/paper/1602.02202/) (2016)
- [Filter Sketch for Network Pruning](https://mlsanity.com/paper/2001.08514/) (2020)
- [A Practical Guide to Randomized Matrix Computations with MATLAB Implementations](https://mlsanity.com/paper/1505.07570/) (2015)
- [Tighter Low-rank Approximation via Sampling the Leveraged Element](https://mlsanity.com/paper/1410.3886/) (2014)
- [Preconditioned Data Sparsification for Big Data with Applications to PCA and K-means](https://mlsanity.com/paper/1511.00152/) (2015)
- [Making Online Sketching Hashing Even Faster](https://mlsanity.com/paper/2010.04948/) (2020)
- [Efficient Frequent Directions Algorithm for Sparse Matrices](https://mlsanity.com/paper/1602.00412/) (2016)
- [Effective Streaming Low-tubal-rank Tensor Approximation via Frequent Directions](https://mlsanity.com/paper/2108.10129/) (2021)

## Built on by (most cited first, 1 of 1)

- [Towards Efficient and Accurate Approximation: Tensor Decomposition Based on Randomized Block Krylov Iteration](https://mlsanity.com/paper/2211.14828/) (2022)

## Abstract (arXiv)

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.