SVD and Tucker Decomposition with Low RAM Requirements

Recently I’ve been experimenting with algorithms for the Singular Value Decomposition and the Tucker Decomposition, with the goal of processing large matrices (more than 10⁵ rows and columns) and large tensors (more than 10⁴ rows, columns, and tubes) that are relatively sparse (about 10% density). The problem with matrices and tensors of this size is that most algorithms use a lot of RAM. My desktop computer has 8 GiB of RAM, but that’s not enough. However, I have found some algorithms that have low RAM requirements and yet are as fast as the standard algorithms.

Until recently, I have been using Doug Rohde’s SVD implementation and Brett Bader and Tamara Kolda’s Tucker decomposition. Both of these use sparse representations and carefully designed algorithms. I recommend both highly, but I am now reaching their limits, given the hardware that is currently available to me.

For low RAM SVD and eigen decomposition, I have been experimenting with various stochastic approximations, such as the Generalized Hebbian Algorithm (GHA), Subspace Networks (SN), and Stochastic Gradient Ascent (SGA). The stochastic approach has performed well in the Netflix Prize competition, but I find that it is sensitive to parameter tuning and somewhat slow. I am now using Matthew Brand’s Thin Singular Value Decomposition, which has been implemented in Matlab by David Wingate. This algorithm uses little RAM, runs quickly, has no parameters to tune, and allows incremental updating of the matrix.

For low RAM Tucker decomposition, I was experimenting with stochastic SVD and eigen decomposition embedded in Bader and Kolda’s Alternating Least Squares (ALS) algorithm. This approach uses little RAM but runs either very slowly (with Brand’s SVD) or very, very slowly (with GHA, SN, or SGA). Then I discovered Hongcheng Wang and Narenda Ahuja’s algorithm for Tucker decomposition, which uses little RAM and runs at least as quickly as Bader and Kolda’s algorithm. The fit of Wang and Ahuja’s decomposition is slightly worse than the fit of Bader and Kolda’s decomposition, but the difference might not matter for my purposes, and I have found a few small tweaks that improve Wang and Ahuja’s fit.

It’s interesting that Brand, Wang, and Ahuja work in computational vision. The demands of visual data have motivated them to develop algorithms for SVD and Tucker decomposition that can handle large matrices and tensors. My intuitions about computational linguistics and the demands of linguistic data are leading me along the same path. I was once attracted to the view of evolutionary psychology, that the mind consists of many different modules, but now I am returning to the older view of the mind as more unified.

Update: My algorithm and source code for big tensors.