Masterproef T703 : Efficiënte multilineaire vermenigvuldigingen met tensoren

Begeleiding:

Informatie:	Karl Meerbergen	Nick Vannieuwenhoven
Promotoren:	Karl Meerbergen
Begeleider:	Karl Meerbergen	Nick Vannieuwenhoven

Onderzoeksgroep:

Numerieke Approximatie en Lineaire Algebra Groep

Context:

Meerdimensionale data komt op natuurlijke wijze voor in een aantal toepassingsdomeinen, zoals chemometrie (spectrometrie), data mining en pattroonherkenning. Om de data afkomstig van deze toepassingen te analyseren, zijn compressietechnieken onmisbaar. Voor tweedimensionale data is de singuliere waardenontbinding hiervoor een geschikte kandidaat. De overeenkomstige techniek voor meerdimensionale data is de hogere-orde singuliere waardenontbinding (HOSVD). Om deze ontbinding te berekenen bestaan er verschillende algoritmen waarin multilineaire matrix-tensorvermenigvuldigingen frequent berekend moeten worden. Bijvoorbeeld: een tensor met dimensies n1 x n2 x n3 wordt vermenigvuldigd met drie matrices van dimensies r1 x n1, r2 x n2 en r3 x n3, respectievelijk, om zo een nieuwe tensor van dimensie r1 x r2 x r3 te bekomen.

Doel:

Het efficiënt implementeren van de multilineaire vermenigvuldiging door middel van het efficiënt uitbuiten van impliciete unfoldings, mogelijk gecombineerd met een blokstructuur. De volgorde waarin de matrixvermenigvuldigingen worden uitgevoerd speelt een rol en kan geoptimaliseerd worden.

Mogelijke Onderzoeksvragen:

We zullen onderzoeken of blokgebaseerde technieken nuttig zijn voor de multilineaire vermenigvuldiging teneinde het geheugengebruik van de algoritmen te begrenzen. De opdracht is vrij open en biedt de student de mogelijkheid om binnen de context van dit eindwerk de focus te verleggen.

Uitwerking:

De focus ligt op het implementeren van enkele mogelijke strategieën om het algoritme op een blokgebaseerde manier uit te voeren. De verschillende technieken worden met elkaar vergeleken en theoretisch geanalyseerd. De student vergelijkt de prestaties met enkele klassieke implementaties van dit algoritme en verklaart de behaalde versnellingsfactor. Indien hiervoor interesse bestaat en er tijd rest, kan dit algoritme ook geparallelliseerd worden.

Relevante literatuur:

Kolda and Bader. Tensor decompositions and applications. SIAM Review. 51(3), pp 455-500.
Vannieuwenhoven, Vanbaelen, Meerbergen, Vandebril. The dense multiple-vector tensor-vector product: An initial study. Tech. Rep. TW635. KU Leuven.
Phan, Tichavsky, Cichocki. Fast alternating LS algorithms for high order CANDECOMP/PARAFAC tensor factorizations. IEEE Trans. Signal Process. 61(19), pp 4834-4846.

Profiel:

De student is geïnteresseerd in het theoretisch analyseren, bedenken en optimaliseren van de prestaties van algoritmen en is in staat om efficiënte code te produceren in C++.

Deze masterproef is voor 1 student.