Low Complexity Damped Gauss-Newton algorithms for CANDECOMP/PARAFAC

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985556%3A_____%2F13%3A00391019" target="_blank" >RIV/67985556:_____/13:00391019 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1137/100808034" target="_blank" >http://dx.doi.org/10.1137/100808034</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/100808034" target="_blank" >10.1137/100808034</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Low Complexity Damped Gauss-Newton algorithms for CANDECOMP/PARAFAC

Popis výsledku v původním jazyce

The damped Gauss-Newton (dGN) algorithm for CANDECOMP/PARAFAC (CP) decomposition can handle the challenges of factors and different magnitudes of factors; nevertheless, for factorization of an order-N tensor of size I_1I_2 I_N with rank R, the algorithmis computationally demanding due to construction of large approximate Hessian of size (RT RT) and its inversion where T= sum_n I_n. In this paper, we propose a fast implementation of the dGN algorithm which is based on novel expressions of the inverse approximate Hessian in block form. The new implementation has lower computational complexity, besides computation of the gradient, requiring the inversion of a matrix of size NR^2xNR^2, which is smaller than the whole approximate Hessian, if T>NR. In addition, neither the Hessian nor its inverse never needs to be stored in its entirety. A variant of the algorithm working with complex-valued data is proposed as well.

Název v anglickém jazyce

Low Complexity Damped Gauss-Newton algorithms for CANDECOMP/PARAFAC

Popis výsledku anglicky

The damped Gauss-Newton (dGN) algorithm for CANDECOMP/PARAFAC (CP) decomposition can handle the challenges of factors and different magnitudes of factors; nevertheless, for factorization of an order-N tensor of size I_1I_2 I_N with rank R, the algorithmis computationally demanding due to construction of large approximate Hessian of size (RT RT) and its inversion where T= sum_n I_n. In this paper, we propose a fast implementation of the dGN algorithm which is based on novel expressions of the inverse approximate Hessian in block form. The new implementation has lower computational complexity, besides computation of the gradient, requiring the inversion of a matrix of size NR^2xNR^2, which is smaller than the whole approximate Hessian, if T>NR. In addition, neither the Hessian nor its inverse never needs to be stored in its entirety. A variant of the algorithm working with complex-valued data is proposed as well.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BB - Aplikovaná statistika, operační výzkum

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

SIAM Journal on Matrix Analysis and Applications

ISSN

0895-4798

e-ISSN

—

Svazek periodika

34

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

22

Strana od-do

126-147

Kód UT WoS článku

000316855600007

EID výsledku v databázi Scopus

—