Header and Body 3


This invention is an expansion of recently discovered matrix sketching technique. The first algorithm, Incremental Frequent Directions has a running time of O(nml) and is based on an algorithm called Frequent Directions II that has a running time of O(nml2). It replaces the full SVD step in Frequent Directions II with a rank-one SVD update. The second algorithm, named Truncated Incremental Frequent Directions II, is a form of incremental frequent directions, with lower running time in trade of the precision for O(nl3). The third algorithm, Truncated Incremental Frequent Directions, uses the same idea from Truncated Incremental Frequent Directions II to Frequent Directions; instead of performing the truncated SVD update for each row of matrix A, it does a batch computation with ½ rows each iteration. This algorithm works with O(nml).

All three algorithms are fast and memory efficient; furthermore, both truncated incremental frequent direction and II are more accurate than the corresponding incremental frequent direction and II in terms of accuracy when measuring relative error.