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

Area of Science:

• Numerical Linear Algebra
• Data Science
• Machine Learning

Background:

• Frequent Directions (FDs) is a deterministic matrix sketching technique for low-rank approximation.
• FDs offer high accuracy but suffer from significant computational costs on large datasets.
• Existing randomized FDs improve efficiency but compromise precision.

Purpose of the Study:

• To develop a more accurate projection subspace for Frequent Directions techniques.
• To enhance both the efficiency and effectiveness of existing FDs algorithms.
• To address the precision-accuracy trade-off in randomized FDs.

Main Methods:

• Integration of block Krylov iteration with random projection techniques.
• Development of a novel fast and accurate FDs algorithm, termed r-BKIFD.
• Theoretical error bound analysis and extensive experimental validation.

Main Results:

• The proposed r-BKIFD algorithm demonstrates a comparable error bound to the original FDs.
• Approximation error can be minimized by selecting an appropriate number of iterations.
• r-BKIFD outperforms popular FDs algorithms in computational efficiency and accuracy on synthetic and real data.

Conclusions:

• r-BKIFD offers a superior balance of accuracy and computational efficiency for low-rank approximation.
• The new method effectively mitigates the precision loss associated with previous randomized FDs.
• r-BKIFD presents a promising advancement for large-scale matrix approximation problems.