2014/06/17 by Joon Hee Choi, Choi, Joon Hee, S. V. N. Vishwanathan +1 · 4 citations
Computer Science · Mathematics · #Advanced Data Compression Techniques #FOS: Computer and information sciences #Machine Learning (stat.ML) #Parallel Computing and Optimization Techniques #Tensor decomposition and applications #stat.ML
paper · pdf · doi:10.48550/arxiv.1406.4519
Under review for NIPS 2014
arxiv created 2014/06/17 · openalex publication_date 2014/06/17 · arxiv updated 2014/06/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a technique for significantly speeding up Alternating Least Squares (ALS) and Gradient Descent (GD), two widely used algorithms for tensor factorization. By exploiting properties of the Khatri-Rao product, we show how to efficiently address a computationally challenging sub-step of both algorithms. Our algorithm, DFacTo, only requires two sparse matrix-vector products and is easy to parallelize. DFacTo is not only scalable but also on average 4 to 10 times faster than competing algorithms on a variety of datasets. For instance, DFacTo only takes 480 seconds on 4 machines to perform one iteration of the ALS algorithm and 1,143 seconds to perform one iteration of the GD algorithm on a 6.5 million x 2.5 million x 1.5 million dimensional tensor with 1.2 billion non-zero entries.