Computing Dense Tensor Decompositions with Optimal Dimension Trees

Abstract : 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 tensor-times-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 decompo-sitions. We show that finding an optimal dimension tree for an N-dimensional tensor 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.
Type de document :
Article dans une revue
Algorithmica, Springer Verlag, 2018, pp.1-30. 〈10.1007/s00453-018-0525-3〉
Liste complète des métadonnées

Littérature citée [11 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01974471
Contributeur : Equipe Roma <>
Soumis le : mardi 8 janvier 2019 - 18:11:40
Dernière modification le : jeudi 7 février 2019 - 17:10:29

Fichier

algorithmica-revision-submitte...
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Oguz Kaya, Yves Robert. Computing Dense Tensor Decompositions with Optimal Dimension Trees. Algorithmica, Springer Verlag, 2018, pp.1-30. 〈10.1007/s00453-018-0525-3〉. 〈hal-01974471〉

Partager

Métriques

Consultations de la notice

39

Téléchargements de fichiers

27