Home Page Image
     


Welcome to My Space

- TENSORBOX (2013), a Matlab toolbox for tensor decompositions is now available to download.

- Tensor Deflation for CANDECOMP/PARAFAC. Part 1: Alternating Subspace Update Algorithm

CANDECOMP/PARAFAC (CP) approximates multiway data by sum of rank-1 tensors. Unlike matrix decomposition, the procedure which estimates the best rank-R 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- R CP decomposition is of full column rank, the decomposition can be performed through (R-1) rank-1 reductions. For decomposition of order-3 tensors of size R x R x R 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.

Ref: Anh-Huy Phan, Petr Tichavský and Andrzej Cichocki, Tensor Deflation for CANDECOMP/PARAFAC. Part 1: Alternating Subspace Update Algorithm , IEEE, Transaction on Signal Processing, 2015.

- Tensor Deflation for CANDECOMP/PARAFAC. Part 2: Initialization and Error Analysis

Part 2 of the study presents several initialization algorithms suitable for the algorithm proposed in Part 1, and error analysis of the tensor deflation algorithm, which shows that there is a marginal loss of accuracy of the deflation algorithm compared to the ordinary CP decomposition.

Ref: Anh-Huy Phan, Petr Tichavský and Andrzej Cichocki, Tensor Deflation for CANDECOMP/PARAFAC. Part 2: Initialization and Error Analysis , IEEE, Transaction on Signal Processing, 2015.

- Tensor Deflation for CANDECOMP/PARAFAC. Part 3: Rank Splitting

In this paper, we extend the rank-1 tensor deflation to block deflation problem. When at least two factor matrices have full column rank, one can extract two rank-1 tensors simultaneously, and rank of the data tensor is reduced by 2. For decomposition of order-3 tensors of size R x R x R and rank-R, the block deflation has a complexity of O(R^3) per iteration which is lower than the cost O(R^4) of the ALS algorithm for the overall CPD.

Ref: Anh-Huy Phan, Petr Tichavský and Andrzej Cichocki, Tensor Deflation for CANDECOMP/PARAFAC. Part 3: Rank Splitting , 2015.

- Matlab code and demo for the fast damped Gauss-Newton algorithms for CANDECOMP/PARAFAC (CP)

Approximate Hessian is often huge and impractical to directly invert. Such task normally costs O(R3T3) where T = I1 + I2 + ... + IN. The fLM algorithms invert the aproximate Hessian with a cost of O(N3R6) or O(NR6).

Ref: Anh Huy Phan, Petr Tichavský, and Andrzej Cichocki, Low Complexity Damped Gauss-Newton Algorithms for CANDECOMP/PARAFAC, SIAM. J. Matrix Anal. & Appl. 34, 126 (2013).

Matlab code of the fLM algorithm is provided in the TENSORBOX.

- Matlab code and demo for the fast CP gradients for CANDECOMP/PARAFAC (CP)

The fast CP gradient can accelerate CP algorithm such ALS, OPT, dGN 8 times fast for 4-D tensors, and even up to 30 times for higher dimensional tensors.

Ref: Anh Huy Phan, Petr Tichavský, and Andrzej Cichocki, Fast Alternating LS Algorithms for High Order CANDECOMP/PARAFAC Tensor Factorizations, IEEE, Transaction on Signal Processing, accepted for publication, 2013.

- Cramer-Rao Induced bound for CANDECOMP/PARAFAC Decomposition

This paper presents a Cramer-Rao lower bound (CRLB) on the variance of unbiased estimates of factor matrices in CANDECOMP/PARAFAC (CP) tensor decomposition. A novel expression needs less operations for computing the bound, O(NR6), than the best existing state-of-the art algorithm, O(N3R6) operations. Insightful expressions are derived for tensors of rank 1 and rank 2 of arbitrary dimension and for tensors of arbitrary dimension and rank, where two factor matrices have orthogonal columns. The results can be used as a gauge of performance of different approximate CP decomposition algorithms, prediction of their accuracy, and for checking stability of a given decomposition of a tensor. A novel expression is derived for a Hessian matrix needed in popular damped Gauss-Newton method for solving the CP decomposition of tensors with missing elements.

Ref: Petr Tichavský, Anh Huy Phan, Zbynek Koldovský, Cramer-Rao-Induced Bounds for CANDECOMP/PARAFAC tensor decomposition , IEEE, Transaction on Signal Processing, pp. 1986-1997, vol. 61, no. 8, 2013.

- Matlab code and demo for the fast algorithm for high order CANDECOMP/PARAFAC (CP) through tensor reshaping

The method exploits the uniqueness of CPD and the relation of a tensor in Kruskal form and its unfolded tensor. The FCP algorithm decomposes an unfolded tensor with lower order, e.g., order-3 tensor. On basis of the order-3 estimated tensor, a structured Kruskal tensor of the same dimension as the data tensor is then generated, and decomposed to find the final solution using fast algorithms for the structured CPD. Using CRIB, we design tensor unfolding strategy which ensures as little deterioration of accuracy as possible.

Ref: Anh Huy Phan, Petr Tichavský, and Andrzej Cichocki, CANDECOMP/PARAFAC Decomposition of High-order Tensors Through Tensor Reshaping, IEEE, Transaction on Signal Processing, accepted for publication, 2013.

- NFEA: Tensor Toolbox for Feature Extraction and Applications

(ver. for BCI)

-TENSORBOX: A Matlab toolbox for tensor decompositions is now available.