Tensor Deflation for CANDECOMP/PARAFAC - Part I: Alternating Subspace Update Algorithm
Result description
CANDECOMP/PARAFAC (CP) approximates multiway data by sum of rank-1 tensors. Unlike matrix decomposition, the procedure which estimates the best rank-tensor approximation through R sequential best rank-1 approximations does not work for tensors, because the deflation does not always reduce the tensor rank. In this paper, we propose a novel deflation method for the problem. When one factor matrix of a rank-CP decomposition is of full column rank, the decomposition can be performed through (R-1) rank-1 reductions. At each deflation stage, the residue tensor is constrained to have a reduced multilinear rank. For decomposition of order-3 tensors of size RxRxR and rank-R estimation of one rank-1 tensor has a computational cost of O(R^3) per iteration which is lower than the cost O(R^4) of the ALS algorithm for the overall CP decomposition. The method can be extended to tracking one or a few rank-one tensors of slow changes, or inspect variations of common patterns in individual datasets.
Keywords
Canonical polyadic decompositiontensor deflationtensor tracking
The result's identifiers
Result code in IS VaVaI
Result on the web
DOI - Digital Object Identifier
Alternative languages
Result language
angličtina
Original language name
Tensor Deflation for CANDECOMP/PARAFAC - Part I: Alternating Subspace Update Algorithm
Original language description
CANDECOMP/PARAFAC (CP) approximates multiway data by sum of rank-1 tensors. Unlike matrix decomposition, the procedure which estimates the best rank-tensor approximation through R sequential best rank-1 approximations does not work for tensors, because the deflation does not always reduce the tensor rank. In this paper, we propose a novel deflation method for the problem. When one factor matrix of a rank-CP decomposition is of full column rank, the decomposition can be performed through (R-1) rank-1 reductions. At each deflation stage, the residue tensor is constrained to have a reduced multilinear rank. For decomposition of order-3 tensors of size RxRxR and rank-R estimation of one rank-1 tensor has a computational cost of O(R^3) per iteration which is lower than the cost O(R^4) of the ALS algorithm for the overall CP decomposition. The method can be extended to tracking one or a few rank-one tensors of slow changes, or inspect variations of common patterns in individual datasets.
Czech name
—
Czech description
—
Classification
Type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BB - Applied statistics, operational research
OECD FORD branch
—
Result continuities
Project
GA14-13713S: Tensor Decomposition Methods and Their Applications
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
IEEE Transactions on Signal Processing
ISSN
1053-587X
e-ISSN
—
Volume of the periodical
63
Issue of the periodical within the volume
22
Country of publishing house
US - UNITED STATES
Number of pages
15
Pages from-to
5924-5938
UT code for WoS article
000362746500004
EID of the result in the Scopus database
—
Basic information
Result type
Jx - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP
BB - Applied statistics, operational research
Year of implementation
2015