Computing Dense Tensor Decompositions with Optimal Dimension Trees

Résumé : 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.
Type de document :
Rapport
[Research Report] RR-9080, Inria. 2017
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01562399
Contributeur : Equipe Roma <>
Soumis le : vendredi 14 juillet 2017 - 16:28:15
Dernière modification le : mardi 16 janvier 2018 - 15:35:08

Fichier

rr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01562399, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

153

Téléchargements de fichiers

83