Petr Tichavský

Anh Huy Phan, Petr Tichavský, Andrzej Cichocki

Product between mode-$n$ unfolding $\bY_{(n)}$ of an $N$-D tensor $\tY$ and Khatri-Rao products of $(N-1)$ factor matrices $\bA^{(m)}$, $m = 1,..., n-1, n+1, ..., N$ exists in algorithms for CANDECOMP/PARAFAC (CP). If $\tY$ is an error tensor of a tensor approximation, this product is the gradient of a cost function with respect to factors, and has the largest workload in most CP algorithms. In this paper, a fast method to compute this product is proposed. Experimental verification shows that the fast CP gradient can accelerate the CP_ALS algorithm 2 times and 8 times faster for factorizations of 3-D and 4-D tensors, and the speed-up ratios can be 20-30 times for higher dimensional tensors.

Anh-Huy Phan, Andrzej Cichocki, Andre Uschmajew et al.

Decompositions of tensors into factor matrices, which interact through a core tensor, have found numerous applications in signal processing and machine learning. A more general tensor model which represents data as an ordered network of sub-tensors of order-2 or order-3 has, so far, not been widely considered in these fields, although this so-called tensor network decomposition has been long studied in quantum physics and scientific computing. In this study, we present novel algorithms and applications of tensor network decompositions, with a particular focus on the tensor train decomposition and its variants. The novel algorithms developed for the tensor train decomposition update, in an alternating way, one or several core tensors at each iteration, and exhibit enhanced mathematical tractability and scalability to exceedingly large-scale data tensors. The proposed algorithms are tested in classic paradigms of blind source separation from a single mixture, denoising, and feature extraction, and achieve superior performance over the widely used truncated algorithms for tensor train decomposition.

Anh-Huy Phan, Konstantin Sobolev, Dmitry Ermilov et al.

A rising problem in the compression of Deep Neural Networks is how to reduce the number of parameters in convolutional kernels and the complexity of these layers by low-rank tensor approximation. Canonical polyadic tensor decomposition (CPD) and Tucker tensor decomposition (TKD) are two solutions to this problem and provide promising results. However, CPD often fails due to degeneracy, making the networks unstable and hard to fine-tune. TKD does not provide much compression if the core tensor is big. This motivates using a hybrid model of CPD and TKD, a decomposition with multiple Tucker models with small core tensor, known as block term decomposition (BTD). This paper proposes a more compact model that further compresses the BTD by enforcing core tensors in BTD identical. We establish a link between the BTD with shared parameters and a looped chain tensor network (TC). Unfortunately, such strongly constrained tensor networks (with loop) encounter severe numerical instability, as proved by y (Landsberg, 2012) and (Handschuh, 2015a). We study perturbation of chain tensor networks, provide interpretation of instability in TC, demonstrate the problem. We propose novel methods to gain the stability of the decomposition results, keep the network robust and attain better approximation. Experimental results will confirm the superiority of the proposed methods in compression of well-known CNNs, and TC decomposition under challenging scenarios

Anh-Huy Phan, Petr Tichavský, Andrzej Cichocki

In CANDECOMP/PARAFAC tensor decomposition, degeneracy often occurs in some difficult scenarios, e.g., when the rank exceeds the tensor dimension, or when the loading components are highly collinear in several or all modes, or when CPD does not have an optimal solution. In such the cases, norms of some rank-1 terms become significantly large and cancel each other. This makes algorithms getting stuck in local minima while running a huge number of iterations does not improve the decomposition. In this paper, we propose an error preservation correction method to deal with such problem. Our aim is to seek a new tensor whose norms of rank-1 tensor components are minimised in an optimization problem, while it preserves the approximation error. An alternating correction algorithm and an all-atone algorithm have been developed for the problem. In addition, we propose a novel CPD with a bound constraint on a norm of the rank-one tensors. The method can be useful for decomposing tensors that cannot be analyzed by traditional algorithms, such as tensors corresponding to the matrix multiplication.

Anh-Huy Phan, Petr Tichavský, Andrzej Cichocki

A novel algorithm is proposed for CANDECOMP/PARAFAC tensor decomposition to exploit best rank-1 tensor approximation. Different from the existing algorithms, our algorithm updates rank-1 tensors simultaneously in parallel. In order to achieve this, we develop new all-at-once algorithms for best rank-1 tensor approximation based on the Levenberg-Marquardt method and the rotational update. We show that the LM algorithm has the same complexity of first-order optimisation algorithms, while the rotational method leads to solving the best rank-1 approximation of tensors of size $2 \times 2 \times \cdots \times 2$. We derive a closed-form expression of the best rank-1 tensor of $2\times 2 \times 2$ tensors and present an ALS algorithm which updates 3 component at a time for higher order tensors. The proposed algorithm is illustrated in decomposition of difficult tensors which are associated with multiplication of two matrices.

Petr Tichavsky

The tensor train (TT) model is widely used to approximate high-dimensional tensors, enabling efficient handling of data that may exceed available memory. TT helps address the curse of dimensionality in applications such as system identification and dynamic programming. In some applications, TT is known as a ``matrix product state" (MPS). This paper introduces algorithms that facilitate the summation, Hadamard (elementwise) product, and matrix--vector product of matrices and vectors (tensors) represented in the tensor train (TT) format. The last product is also known under the acronym MPO--MPS. The proposed algorithms achieve an improved tradeoff between computational efficiency and accuracy compared to state-of-the-art methods.

Anh-Huy Phan, Konstantin Sobolev, Konstantin Sozykin et al.

Most state of the art deep neural networks are overparameterized and exhibit a high computational cost. A straightforward approach to this problem is to replace convolutional kernels with its low-rank tensor approximations, whereas the Canonical Polyadic tensor Decomposition is one of the most suited models. However, fitting the convolutional tensors by numerical optimization algorithms often encounters diverging components, i.e., extremely large rank-one tensors but canceling each other. Such degeneracy often causes the non-interpretable result and numerical instability for the neural network fine-tuning. This paper is the first study on degeneracy in the tensor decomposition of convolutional kernels. We present a novel method, which can stabilize the low-rank approximation of convolutional kernels and ensure efficient compression while preserving the high-quality performance of the neural networks. We evaluate our approach on popular CNN architectures for image classification and show that our method results in much lower accuracy degradation and provides consistent performance.

Anh-Huy Phan, Petr Tichavsky, Andrzej Cichocki

CANDECOMP/PARAFAC (CPD) approximates multiway data by sum of rank-1 tensors. Our recent study has presented a method to rank-1 tensor deflation, i.e. sequential extraction of the rank-1 components. In this paper, we extend the method 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.

Jiří Vomlel, Petr Tichavský

A difficult task in modeling with Bayesian networks is the elicitation of numerical parameters of Bayesian networks. A large number of parameters is needed to specify a conditional probability table (CPT) that has a larger parent set. In this paper we show that, most CPTs from real applications of Bayesian networks can actually be very well approximated by tables that require substantially less parameters. This observation has practical consequence not only for model elicitation but also for efficient probabilistic reasoning with these networks.

Anh Huy Phan, Petr Tichavský, Andrzej Cichocki

The damped Gauss-Newton (dGN) algorithm for CANDECOMP/PARAFAC (CP) decomposition can handle the challenges of collinearity of factors and different magnitudes of factors; nevertheless, for factorization of an $N$-D tensor of size $I_1\times I_N$ with rank $R$, the algorithm is computationally demanding due to construction of large approximate Hessian of size $(RT \times 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 (this part is common to both methods), requiring the inversion of a matrix of size $NR^2\times NR^2$, which is much smaller than the whole approximate Hessian, if $T \gg NR$. In addition, the implementation has lower memory requirements, because neither the Hessian nor its inverse never need to be stored in their entirety. A variant of the algorithm working with complex valued data is proposed as well. Complexity and performance of the proposed algorithm is compared with those of dGN and ALS with line search on examples of difficult benchmark tensors.