HOQRI: Higher-order QR Iteration for Scalable Tucker Decomposition

We propose a new algorithm called higher-order QR iteration (HOQRI) for computing the Tucker decomposition of large and sparse tensors. Compared to the celebrated higher-order orthogonal iterations (HOOI), HOQRI relies on a simple orthogonalization step in each iteration rather than a more sophisticated singular value decomposition step as in HOOI. More importantly, when dealing with extremely large and sparse data tensors, HOQRI completely eliminates the intermediate memory explotion by defining a new sparse tensor operation called TTMcTC. Furthermore, HOQRI is shown to monotically improve the objective function, thus enjoys the same convergence guarantee as that of HOOI. Numerical experiments on synthetic and real data showcase the effectiveness of HOQRI.