Computing Dense Tensor Decompositions with Optimal Dimension Trees

Calcul des Décompositions de Tenseurs Denses avec des Arbres de Dimension Optimalles

Oguz Kaya (1, 2) , Yves Robert (1, 3, 2) , Bora Uçar (1, 2)

1 ROMA - Optimisation des ressources : modèles, algorithmes et ordonnancement
2 LIP - Laboratoire de l'Informatique du Parallélisme
3 The University of Tennessee [Knoxville]

Dense tensor decompositions have been widely used in many signal processing problems including analyzing speech signals, identifying the localization of signal sources, and many other communication applications. Computing these decompositions poses major computational challenges for big datasets emerging in these domains. CANDECOMP/PARAFAC~(CP) and Tucker formulations are the prominent tensor decomposition schemes heavily used in these fields, and the algorithms for computing them involve applying two core operations, namely tensor-times-matrix~(TTM) and -vector~(TTV) multiplication, which are executed repetitively within an iterative framework. In the recent past, efficient computational schemes using a data structure called dimension tree are employed to significantly reduce the cost of these two operations through storing and reusing partial results that are commonly used across different iterations of these algorithms. This framework has been introduced for sparse CP and Tucker decompositions in the literature, and a recent work investigates using an optimal binary dimension tree structure in computing dense Tucker decompositions. In this paper, we investigate finding an optimal dimension tree for both CP and Tucker decompositions. We show that finding an optimal dimension tree is NP-hard for both decompositions, provide faster exact algorithms for finding an optimal dimension tree in $O(3^N)$ time using $O(2^N)$ space for the Tucker case, and extend the algorithm to the case of CP decomposition with the same time and space complexities.

Les décompositions de tenseurs sont largement utilisées dans plusieurs problèmes de traitement du signal, notamment l’analyse des signaux vocaux, l’identification de la localisation des sources des signaux et d’autres applications de communication. Le calcul de ces décompositions pose un énorme défi calculatoire, particulièrement pour les grands jeux de données apparaissant dans ces domaines. Les formulations du CANDECOMP/PARAFAC (CP) et Tucker sont les deux décompositions les plus intensivement utilisées. Les algorithmes pour calculer ces décompositions incluent deux operations principales, tenseur-fois-matrice (TTM) et -vector (TTV), qui se répètent dans une méthode iterative. Dans ce rapport, on introduit un nouveau schema de calcul pour éffectuer ces deux operations efficacement en calculant les decompositions CP et Tucker. Pour ce faire, on adopte une structure d’arbre qui permet de stocker et ré-utiliser les résultats partiels pour réduire le coût de calcul de manière significative. Ensuite, on fournit un algorithme glouton, s’exécutant en temps linéaire, pour trouver l’ordre optimal minimisant le coût de calcule d’une serie de TTMs. Finalement, on examine le problème de trouver un arbre optimal pour calculer les décompositions CP et Tucker avec le nouveau schema de calcul proposé, et on prouve que ce problème est NP-difficile dans les deux cas.

Mots clés: dimension trees; tensor decomposition; CP decomposition; Tucker decomposition

Mots clés: arbres de dimension; décomposition Tucker; décomposition de tenseurs; décomposition CP

Domaines: Informatique [cs]

Oguz Kaya, Yves Robert, Bora Uçar. Computing Dense Tensor Decompositions with Optimal Dimension Trees. [Research Report] RR-9080, Inria. 2017. ⟨hal-01562399⟩