DFacTo: Distributed Factorization of Tensors

By Joon Hee Choi, S. V. N. Vishwanathan. 2014

161 citations recorded by the source corpus.

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.

Subfields: Computational Mathematics, Computer Vision and Pattern Recognition, Hardware and Architecture

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mathematics

In Computer Vision and Pattern Recognition

In Hardware and Architecture

Citations in the corpus

Privacy-Preserving Tensor Factorization for Collaborative Health Data Analysis (2019, methodology): “DFacTo [6] improves GigaTensor by exploring properties related to the Khatri-Rao Product and achieves faster computation time and beer scalability.”
Federated Tensor Factorization for Computational Phenotyping (2017, neutral): “This is different from distributed tensor factorization models [7, 16] and grid tensor factorization models [9]. latter assumes data spread across different but inter-connected computer systems, in which the communication cost is negligible and data/computation can be arbitrarily reallocated to…”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 2 Applications and Future Perspectives (2017, background): “…of nonlinear functions and systems [Dolgov and Khoromskij, 2013, Khoromskij, 2011b, Khoromskij and Miao, 2014], • CP decomposition and its applications [Choi and Vishwanathan, 2014, Kamal et al., 2016, Kang et al., 2012, Shin et al., 2017, Vervliet and Lathauwer, 2016, Wang et al., 2015,…”
HiCOO: Hierarchical Storage of Sparse Tensors (2018, methodology): “DFacTo [30] considered MTTKRP as a series of sparse matrix-vector multiplications for distributed systems, however, it requires explicit matricization which takes non-negligible time.”
Tensor Networks for Dimensionality Reduction and Large-scale Optimization: Part 1 Low-Rank Tensor Decompositions (2016, unknown): “uge-scale tensors, include tensor sketching – a random mapping technique, which exploits kernel methods and regression [278], and the class of distributed algorithms such as the CPOPT [4], the DFacTo [45] and the GigaTensor which is based on Hadoop / Mapreduce paradigm [134]. Constraints. Under rath”
L G ] 1 1 A pr 2 01 7 Federated Tensor Factorization for Computational Phenotyping (2018, background): “is is different from distributed tensor factorization models [7, 16] and grid tensor factorization models [9].”