Overview of recent advances in numerical tensor algebra
---
paper_title: Blind Identification of Underdetermined Mixtures by Simultaneous Matrix Diagonalization

paper_content:

In this paper, we study simultaneous matrix diagonalization-based techniques for the estimation of the mixing matrix in underdetermined independent component analysis (ICA). This includes a generalization to underdetermined mixtures of the well-known SOBI algorithm. The problem is reformulated in terms of the parallel factor decomposition (PARAFAC) of a higher-order tensor. We present conditions under which the mixing matrix is unique and discuss several algorithms for its computation.
---
paper_title: Tensor-based channel estimation (TENCE) for two-way relaying with multiple antennas and spatial reuse

paper_content:

In this paper we study two-way relaying with amplify-and-forward (AF) relays. In two-way relaying, two terminals exchange data with the help of an intermediate relay station. In order to enable mass deployment of these relays, we focus on very simple AF relays that do not have any channel state information. Hence, to separate the data streams in two-way relaying, both user terminals need reliable knowledge of all relevant channel parameters. We therefore propose the novel tensor-based channel estimation algorithm TENCE that provides both terminals with full knowledge of all channel parameters involved in the transmission. The solution is algebraic, i.e., it does not require any iterative procedures. Moreover, TENCE is applicable to arbitrary antenna configurations. We also derive criteria for the design of the pilot symbols and the corresponding relay amplification matrices. Computer simulations demonstrate the achievable channel estimation accuracy.
---
paper_title: Tensor Decompositions and Applications

paper_content:

This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or $N$-way array. Decompositions of higher-order tensors (i.e., $N$-way arrays with $N \geq 3$) have applications in psycho-metrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rank-one tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.
---
paper_title: Blind PARAFAC Receivers for DS-CDMA Systems

paper_content:

This paper links the direct-sequence code-division multiple access (DS-CDMA) multiuser separation-equalization-detection problem to the parallel factor (PARAFAC) model, which is an analysis tool rooted in psychometrics and chemometrics. Exploiting this link, it derives a deterministic blind PARAFAC DS-CDMA receiver with performance close to non-blind minimum mean-squared error (MMSE). The proposed PARAFAC receiver capitalizes on code, spatial, and temporal diversity-combining, thereby supporting small sample sizes, more users than sensors, and/or less spreading than users. Interestingly, PARAFAC does not require knowledge of spreading codes, the specifics of multipath (interchip interference), DOA-calibration information, finite alphabet/constant modulus, or statistical independence/whiteness to recover the information-bearing signals. Instead, PARAFAC relies on a fundamental result regarding the uniqueness of low-rank three-way array decomposition due to Kruskal (1977, 1988) (and generalized herein to the complex-valued case) that guarantees identifiability of all relevant signals and propagation parameters. These and other issues are also demonstrated in pertinent simulation experiments.
---
paper_title: Multilinear (Tensor) Image Synthesis, Analysis, and Recognition

paper_content:

Linear algebra, the algebra of vectors and matrices, has traditionally been a veritable workhorse in image processing. Linear algebraic methods such as principal components analysis (PCA) and its refinement known as independent components analysis (ICA) model single-factor linear variation in image formation or the linear combination of multiple sources. In this exploratory signal processing article, we review a novel, multilinear (tensor) algebraic framework for image processing, particularly for the synthesis, analysis, and recognition of images. In particular, we will discuss multilinear generalizations of PCA and ICA and present new applications of these tensorial methods to image-based rendering and the analysis and recognition of facial image ensembles.
---
paper_title: Unsupervised Multiway Data Analysis: A Literature Survey

paper_content:

Two-way arrays or matrices are often not enough to represent all the information in the data and standard two-way analysis techniques commonly applied on matrices may fail to find the underlying structures in multi-modal datasets. Multiway data analysis has recently become popular as an exploratory analysis tool in discovering the structures in higher-order datasets, where data have more than two modes. We provide a review of significant contributions in the literature on multiway models, algorithms as well as their applications in diverse disciplines including chemometrics, neuroscience, social network analysis, text mining and computer vision.
---
paper_title: Adaptive Algorithms to Track the PARAFAC Decomposition of a Third-Order Tensor

paper_content:

The PARAFAC decomposition of a higher-order tensor is a powerful multilinear algebra tool that becomes more and more popular in a number of disciplines. Existing PARAFAC algorithms are computationally demanding and operate in batch mode - both serious drawbacks for on-line applications. When the data are serially acquired, or the underlying model changes with time, adaptive PARAFAC algorithms that can track the sought decomposition at low complexity would be highly desirable. This is a challenging task that has not been addressed in the literature, and the topic of this paper. Given an estimate of the PARAFAC decomposition of a tensor at instant t, we propose two adaptive algorithms to update the decomposition at instant t+1, the new tensor being obtained from the old one after appending a new slice in the 'time' dimension. The proposed algorithms can yield estimation performance that is very close to that obtained via repeated application of state-of-art batch algorithms, at orders of magnitude lower complexity. The effectiveness of the proposed algorithms is illustrated using a MIMO radar application (tracking of directions of arrival and directions of departure) as an example.
---
paper_title: Parallel Factor Analysis in Sensor Array Processing

paper_content:

This paper links multiple invariance sensor array processing (MI-SAP) to parallel factor (PARAFAC) analysis, which is a tool rooted in psychometrics and chemometrics. PARAFAC is a common name for low-rank decomposition of three- and higher way arrays. This link facilitates the derivation of powerful identifiability results for MI-SAP, shows that the uniqueness of single- and multiple-invariance ESPRIT stems from uniqueness of low-rank decomposition of three-way arrays, and allows tapping on the available expertise for fitting the PARAFAC model. The results are applicable to both data-domain and subspace MI-SAP formulations. The paper also includes a constructive uniqueness proof for a special PARAFAC model.
---
paper_title: Higher-Order SVD-Based Subspace Estimation to Improve the Parameter Estimation Accuracy in Multidimensional Harmonic Retrieval Problems

paper_content:

Multidimensional harmonic retrieval problems are encountered in a variety of signal processing applications including radar, sonar, communications, medical imaging, and the estimation of the parameters of the dominant multipath components from MIMO channel measurements. R-dimensional subspace-based methods, such as R-D Unitary ESPRIT, R-D RARE, or R-D MUSIC, are frequently used for this task. Since the measurement data is multidimensional, current approaches require stacking the dimensions into one highly structured matrix. However, in the conventional subspace estimation step, e.g., via an SVD of the latter matrix, this structure is not exploited. In this paper, we define a measurement tensor and estimate the signal subspace through a higher-order SVD. This allows us to exploit the structure inherent in the measurement data already in the first step of the algorithm which leads to better estimates of the signal subspace. We show how the concepts of forward-backward averaging and the mapping of centro-Hermitian matrices to real-valued matrices of the same size can be extended to tensors. As examples, we develop the R-D standard Tensor-ESPRIT and the R-D Unitary Tensor-ESPRIT algorithms. However, these new concepts can be applied to any multidimensional subspace-based parameter estimation scheme. Significant improvements of the resulting parameter estimation accuracy are achieved if there is at least one of the R dimensions, which possesses a number of sensors that is larger than the number of sources. This can already be observed in the two-dimensional case.
---
paper_title: Blind Deconvolution of DS-CDMA Signals by Means of Decomposition in Rank-$(1,L,L)$ Terms

paper_content:

In this paper, we present a powerful technique for the blind extraction of direct-sequence code-division multiple access (DS-CDMA) signals from convolutive mixtures received by an antenna array. The technique is based on a generalization of the canonical or parallel factor decomposition (CANDECOMP/PARAFAC) in multilinear algebra. We present a bound on the number of users under which blind separation and deconvolution is guaranteed. The solution is computed by means of an alternating least squares (ALS) algorithm. The excellent performance is illustrated by means of a number of simulations. We include an explicit expression of the Cramer-Rao bound (CRB) of the transmitted symbols.
---
paper_title: A Constrained Factor Decomposition With Application to MIMO Antenna Systems

paper_content:

In this paper, we formulate a new tensor decomposition herein called constrained factor (CONFAC) decomposition. It consists in decomposing a third-order tensor into a triple sum of rank-one tensor factors, where interactions involving the components of different tensor factors are allowed. The interaction pattern is controlled by three constraint matrices the columns of which are canonical vectors. Each constraint matrix is associated with a given dimension, or mode, of the tensor. The explicit use of these constraint matrices provides degrees of freedom to the CONFAC decomposition for modeling tensor signals with constrained structures which cannot be handled with the standard parallel factor (PARAFAC) decomposition. The uniqueness of this decomposition is discussed and an application to multiple-input multiple-output (MIMO) antenna systems is presented. A new transmission structure is proposed, the core of which consists of a precoder tensor decomposed as a function of the CONFAC constraint matrices. By adjusting the precoder constraint matrices, we can control the allocation of data streams and spreading codes to transmit antennas. Based on a CONFAC model of the received signal, blind symbol/code/channel recovery is possible using the alternating least squares algorithm. For illustrating this application, we evaluate the bit-error-rate (BER) performance for some configurations of the precoder constraint matrices.
---
paper_title: A Block Component Model-Based Blind DS-CDMA Receiver

paper_content:

In this paper, we consider the problem of blind multiuser separation-equalization in the uplink of a wideband DS-CDMA system, in a multipath propagation environment with intersymbol-interference (ISI). To solve this problem, we propose a multilinear algebraic receiver that relies on a new third-order tensor decomposition and generalizes the parallel factor (PARAFAC) model. Our method is deterministic and exploits the temporal, spatial and spectral diversities to collect the received data in a third-order tensor. The specific algebraic structure of this tensor is then used to decompose it in a sum of user's contributions. The so-called block component model (BCM) receiver does not require knowledge of the spreading codes, the propagation parameters, nor statistical independence of the sources but relies instead on a fundamental uniqueness condition of the decomposition that guarantees identifiability of every user's contribution. The development of fast and reliable techniques to calculate this decomposition is important. We propose a blind receiver based either on an alternating least squares (ALS) algorithm or on a Levenberg-Marquardt (LM) algorithm. Simulations illustrate the performance of the algorithms.
---
paper_title: PARAFAC-Based Blind Estimation Of Possibly Underdetermined Convolutive MIMO Systems

paper_content:

In this paper, we consider the problem of blind identification of a convolutive multiple-input-multiple-output (MIMO) system with No outputs and Ni inputs. While many methods have been proposed to blindly identify convolutive MIMO systems with No ges Ni (overdetermined), very scarce results exist for the case of (underdetermined), all of which refer to systems that either have some special structure or special and values. In this paper, we show that, as long as , independent of whether the system is overdetermined or underdetermined, we can always find the appropriate order of statistics that guarantees identifiability of the system response within trivial ambiguities. We also propose an algorithm to reach the solution, that consists of parallel factorization (PARAFAC) of a -way tensor containing th-order statistics of the system outputs, followed by an iterative scheme. For a certain order of statistics , we provide the description of the class of identifiable MIMO systems. We also show that this class can be expanded by applying PARAFAC decomposition to a pair of tensors instead of one tensor. The proposed approach constitutes a novel scheme for estimation of underdetermined systems, and improves over existing approaches for overdetermined systems.
---
paper_title: Tensor-Based Channel Estimation and Iterative Refinements for Two-Way Relaying With Multiple Antennas and Spatial Reuse

paper_content:

Relaying is one of the key technologies to satisfy the demands of future mobile communication systems. In particular, two-way relaying is known to exploit the radio resources in a very efficient manner. In this contribution, we consider two-way relaying with amplify-and-forward (AF) MIMO relays. Since AF relays do not decode the signals, the separation of the data streams has to be performed by the terminals themselves. For this task both nodes require reliable channel knowledge of all relevant channel parameters. Therefore, we examine channel estimation schemes for two-way relaying with AF MIMO relays. We investigate a simple Least Squares (LS) based scheme for the estimation of the compound channels as well as a tensor-based channel estimation (TENCE) scheme which takes advantage of the special structure in the compound channel matrices to further improve the estimation accuracy. Note that TENCE is purely algebraic (i.e., it does not require any iterative procedures) and applicable to arbitrary antenna configurations. Then we demonstrate that the solution obtained by TENCE can be improved by an iterative refinement which is based on the structured least squares (SLS) technique. In this application, between one and four iterations are sufficient and consequently the increase in computational complexity is moderate. The iterative refinement is optional and targeted for cases where the channel estimation accuracy is critical. Moreover, we propose design rules for the training symbols as well as the relay amplification matrices during the training phase to facilitate the estimation procedures. Finally, we evaluate the achievable channel estimation accuracy of the LS-based compound channel estimation scheme as well as the tensor-based approach and its iterative refinement via numerical computer simulations.
---
paper_title: Tensor Decompositions and Applications

paper_content:

This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or $N$-way array. Decompositions of higher-order tensors (i.e., $N$-way arrays with $N \geq 3$) have applications in psycho-metrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rank-one tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.
---
paper_title: Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics

paper_content:

Abstract A three-way array X (or three-dimensional matrix) is an array of numbers xijk subscripted by three indices. A triad is a multiplicative array, xijk = aibjck. Analogous to the rank and the row rank of a matrix, we define rank (X) to be the minimum number of triads whose sum is X, and dim1(X) to be the dimensionality of the space of matrices generated by the 1-slabs of X. (Rank and dim1 may not be equal.) We prove several lower bounds on rank. For example, a special case of Theorem 1 is that rank(X)⩾dim 1 (UX) + rank(XW) − dim 1 (UXW) , where U and W are matrices; this generalizes a matrix theorem of Frobenius. We define the triple product [A, B, C] of three matrices to be the three-way array whose (i, j, k) element is given by ⩞rairbjrckr; in other words, the triple product is the sum of triads formed from the columns of A, B, and C. We prove several sufficient conditions for the factors of a triple product to be essentially unique. For example (see Theorem 4a), suppose [A, B, C] = [ A , B , C ] , and each of the matrices has R columns. Suppose every set of rank (A) columns of A are independent, and similar conditions hold for B and C. Suppose rank (A) + rank (B) + rank (C) ⩾ 2R + 2. Then there exist diagonal matrices Λ, M, N and a permutation matrix P such that A = APΛ, B = BP M , C = CP N . Our results have applications to arithmetic complexity theory and to statistical models used in three-way multidimensional scaling.
---
paper_title: Unsupervised Multiway Data Analysis: A Literature Survey

paper_content:

Two-way arrays or matrices are often not enough to represent all the information in the data and standard two-way analysis techniques commonly applied on matrices may fail to find the underlying structures in multi-modal datasets. Multiway data analysis has recently become popular as an exploratory analysis tool in discovering the structures in higher-order datasets, where data have more than two modes. We provide a review of significant contributions in the literature on multiway models, algorithms as well as their applications in diverse disciplines including chemometrics, neuroscience, social network analysis, text mining and computer vision.
---
paper_title: Unsupervised Multiway Data Analysis: A Literature Survey

paper_content:

Two-way arrays or matrices are often not enough to represent all the information in the data and standard two-way analysis techniques commonly applied on matrices may fail to find the underlying structures in multi-modal datasets. Multiway data analysis has recently become popular as an exploratory analysis tool in discovering the structures in higher-order datasets, where data have more than two modes. We provide a review of significant contributions in the literature on multiway models, algorithms as well as their applications in diverse disciplines including chemometrics, neuroscience, social network analysis, text mining and computer vision.
---
paper_title: Tensor Decompositions, Alternating Least Squares and Other Tales

paper_content:

This work was originally motivated by a classification of tensors proposed by Richard Harshman. In particular, we focus on simple and multiple “bottlenecks”, and on “swamps”. Existing theoretical results are surveyed, some numerical algorithms are described in details, and their numerical complexity is calculated. In particular, the interest in using the ELS enhancement in these algorithms is discussed. Computer simulations feed this discussion.
---
paper_title: Tensor rank and the ill-posedness of the best low-rank approximation problem

paper_content:

There has been continued interest in seeking a theorem describing optimal low-rank approximations to tensors of order 3 or higher, that parallels the Eckart-Young theorem for matrices. In this paper, we argue that the naive approach to this problem is doomed to failure because, unlike matrices, tensors of order 3 or higher can fail to have best rank-r approximations. The phenomenon is much more widespread than one might suspect: examples of this failure can be constructed over a wide range of dimensions, orders and ranks, regardless of the choice of norm (or even Bregman divergence). Moreover, we show that in many instances these counterexamples have positive volume: they cannot be regarded as isolated phenomena. In one extreme case, we exhibit a tensor space in which no rank-3 tensor has an optimal rank-2 approximation. The notable exceptions to this misbehavior are rank-1 tensors and order-2 tensors. In a more positive spirit, we propose a natural way of overcoming the ill-posedness of the low-rank approximation problem, by using weak solutions when true solutions do not exist. In our work we emphasize the importance of closely studying concrete low-dimensional examples as a first step towards more general results. To this end, we present a detailed analysis of equivalence classes of 2-by-2-by-2 tensors, and we develop methods for extending results upwards to higher orders and dimensions. Finally, we link our work to existing studies of tensors from an algebraic geometric point of view. The rank of a tensor can in theory be given a semialgebraic description; i.e., can be determined by a system of polynomial inequalities. In particular we make extensive use of the 2-by-2-by-2 hyperdeterminant.
---
paper_title: Symmetric tensors and symmetric tensor rank

paper_content:

A symmetric tensor is a higher order generalization of a symmetric matrix. In this paper, we study various properties of symmetric tensors in relation to a decomposition into a sum of symmetric outer product of vectors. A rank-1 order-k tensor is the outer product of k non-zero vectors. Any symmetric tensor can be decomposed into a linear combination of rank-1 tensors, each of them being symmetric or not. The rank of a symmetric tensor is the minimal number of rank-1 tensors that is necessary to reconstruct it. The symmetric rank is obtained when the constituting rank-1 tensors are imposed to be themselves symmetric. It is shown that rank and symmetric rank are equal in a number of cases, and that they always exist in an algebraically closed field. We will discuss the notion of the generic symmetric rank, which, due to the work of Alexander and Hirschowitz, is now known for any values of dimension and order. We will also show that the set of symmetric tensors of symmetric rank at most r is not closed, unless r = 1.
---
paper_title: Subtracting a best rank-1 approximation may increase tensor rank

paper_content:

It has been shown that a best rank-R approximation of an order-k tensor may not exist when R>1 and k>2. This poses a serious problem to data analysts using tensor decompositions. It has been observed numerically that, generally, this issue cannot be solved by consecutively computing and subtracting best rank-1 approximations. The reason for this is that subtracting a best rank-1 approximation generally does not decrease tensor rank. In this paper, we provide a mathematical treatment of this property for real-valued 2x2x2 tensors, with symmetric tensors as a special case. Regardless of the symmetry, we show that for generic 2x2x2 tensors (which have rank 2 or 3), subtracting a best rank-1 approximation results in a tensor that has rank 3 and lies on the boundary between the rank-2 and rank-3 sets. Hence, for a typical tensor of rank 2, subtracting a best rank-1 approximation increases the tensor rank.
---
paper_title: Nonnegative approximations of nonnegative tensors

paper_content:

We study the decomposition of a nonnegative tensor into a minimal sum of outer product of nonnegative vectors and the associated parsimonious naive Bayes probabilistic model. We show that the corresponding approximation problem, which is central to nonnegative PARAFAC, will always have optimal solutions. The result holds for any choice of norms and, under a mild assumption, even Bregman divergences.
---
paper_title: Tensor Decompositions and Applications

paper_content:

This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or $N$-way array. Decompositions of higher-order tensors (i.e., $N$-way arrays with $N \geq 3$) have applications in psycho-metrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rank-one tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.
---
paper_title: A multilinear singular value decomposition

paper_content:

We discuss a multilinear generalization of the singular value decomposition. There is a strong analogy between several properties of the matrix and the higher-order tensor decomposition; uniqueness, link with the matrix eigenvalue decomposition, first-order perturbation effects, etc., are analyzed. We investigate how tensor symmetries affect the decomposition and propose a multilinear generalization of the symmetric eigenvalue decomposition for pair-wise symmetric tensors.
---
paper_title: Tensor rank and the ill-posedness of the best low-rank approximation problem

paper_content:

There has been continued interest in seeking a theorem describing optimal low-rank approximations to tensors of order 3 or higher, that parallels the Eckart-Young theorem for matrices. In this paper, we argue that the naive approach to this problem is doomed to failure because, unlike matrices, tensors of order 3 or higher can fail to have best rank-r approximations. The phenomenon is much more widespread than one might suspect: examples of this failure can be constructed over a wide range of dimensions, orders and ranks, regardless of the choice of norm (or even Bregman divergence). Moreover, we show that in many instances these counterexamples have positive volume: they cannot be regarded as isolated phenomena. In one extreme case, we exhibit a tensor space in which no rank-3 tensor has an optimal rank-2 approximation. The notable exceptions to this misbehavior are rank-1 tensors and order-2 tensors. In a more positive spirit, we propose a natural way of overcoming the ill-posedness of the low-rank approximation problem, by using weak solutions when true solutions do not exist. In our work we emphasize the importance of closely studying concrete low-dimensional examples as a first step towards more general results. To this end, we present a detailed analysis of equivalence classes of 2-by-2-by-2 tensors, and we develop methods for extending results upwards to higher orders and dimensions. Finally, we link our work to existing studies of tensors from an algebraic geometric point of view. The rank of a tensor can in theory be given a semialgebraic description; i.e., can be determined by a system of polynomial inequalities. In particular we make extensive use of the 2-by-2-by-2 hyperdeterminant.
---
paper_title: Blind Identification of Underdetermined Mixtures by Simultaneous Matrix Diagonalization

paper_content:

In this paper, we study simultaneous matrix diagonalization-based techniques for the estimation of the mixing matrix in underdetermined independent component analysis (ICA). This includes a generalization to underdetermined mixtures of the well-known SOBI algorithm. The problem is reformulated in terms of the parallel factor decomposition (PARAFAC) of a higher-order tensor. We present conditions under which the mixing matrix is unique and discuss several algorithms for its computation.
---
paper_title: Tensor Decompositions and Applications

paper_content:

This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or $N$-way array. Decompositions of higher-order tensors (i.e., $N$-way arrays with $N \geq 3$) have applications in psycho-metrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rank-one tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.
---
paper_title: Tensor Decompositions, Alternating Least Squares and Other Tales

paper_content:

This work was originally motivated by a classification of tensors proposed by Richard Harshman. In particular, we focus on simple and multiple “bottlenecks”, and on “swamps”. Existing theoretical results are surveyed, some numerical algorithms are described in details, and their numerical complexity is calculated. In particular, the interest in using the ELS enhancement in these algorithms is discussed. Computer simulations feed this discussion.
---
paper_title: A closed-form solution for multilinear PARAFAC decompositions

paper_content:

In this paper we study the R-way Parallel Factor Analysis (also referred to as R-way PARAFAC) problem. This branch of multi-way signal processing has received increased attention recently which is due to the versatility of the model as well as the identifiability results demonstrating its superiority to matrix-only (2-way) approaches. In R-way PARAFAC analysis, the goal is to decompose an R-dimensional tensor into a minimal sum of rank-1 terms. So far, there exist sub-optimal closed-form solutions as well as iterative techniques for finding these decompositions. However, the latter often require many iterations to converge. In this contribution we demonstrate that the R-way PARAFAC decomposition can be reduced to a set of simultaneous matrix diagonalization problems. Exploiting the structure of the R-dimensional problem, we obtain several estimates for each of the factors and present a "best matching" scheme to select the best estimate for each factor. By means of computer simulations we compare our closed-form solution to an iterative technique and demonstrate the enhanced robustness in critical scenarios.
---
paper_title: A comparison of algorithms for fitting the PARAFAC model

paper_content:

A multitude of algorithms have been developed to fit a trilinear PARAFAC model to a three-way array. Limits and advantages of some of the available methods (i.e. GRAM-DTLD, PARAFAC-ALS, ASD, SWATLD, PMF3 and dGN) are compared. The algorithms are explained in general terms together with two approaches to accelerate them: line search and compression. In order to compare the different methods, 720 sets of artificial data were generated with varying level and type of noise, collinearity of the factors and rank. Two PARAFAC models were fitted on each data set: the first having the correct number of factors F and the second with F+1 components (the objective being to assess the sensitivity of the different approaches to the over-factoring problem, i.e. when the number of extracted components exceeds the rank of the array). The algorithms have also been tested on two real data sets of fluorescence measurements, again by extracting both the right and an exceeding number of factors. The evaluations are based on: number of iterations necessary to reach convergence, time consumption, quality of the solution and amount of resources required for the calculations (primarily memory).
---
paper_title: A closed-form solution for Parallel Factor (PARAFAC) Analysis

paper_content:

Parallel factor analysis (PARAFAC) is a branch of multi-way signal processing that has received increased attention recently. This is due to the large class of applications as well as the milestone identifiability results demonstrating the superiority to matrix (two-way) analysis approaches. A significant amount of research was dedicated to iterative methods to estimate the factors from noisy data. In many situations these require many iterations and are not guaranteed to converge to the global optimum. Therefore, suboptimal closed-form solutions were proposed as initializations. In this contribution we derive a closed-form solution to completely replace the iterative approach by transforming PARAFAC into several joint diagonalization problems. Thereby, we obtain several estimates for each of the factors and present a new "best matching" scheme to select the best estimate for each factor. In contrast to the techniques known from the literature, our closed-form solution can efficiently exploit symmetric as well as Hermitian symmetric models and solve the underdetermined case, if there are at least two modes that are non-degenerate and full rank. This closed-form solution achieves approximately the same performance as previously proposed iterative solutions and even outperforms them in critical scenarios.
---
paper_title: Tensor Decompositions and Applications

paper_content:

This survey provides an overview of higher-order tensor decompositions, their applications, and available software. A tensor is a multidimensional or $N$-way array. Decompositions of higher-order tensors (i.e., $N$-way arrays with $N \geq 3$) have applications in psycho-metrics, chemometrics, signal processing, numerical linear algebra, computer vision, numerical analysis, data mining, neuroscience, graph analysis, and elsewhere. Two particular tensor decompositions can be considered to be higher-order extensions of the matrix singular value decomposition: CANDECOMP/PARAFAC (CP) decomposes a tensor as a sum of rank-one tensors, and the Tucker decomposition is a higher-order form of principal component analysis. There are many other tensor decompositions, including INDSCAL, PARAFAC2, CANDELINC, DEDICOM, and PARATUCK2 as well as nonnegative variants of all of the above. The N-way Toolbox, Tensor Toolbox, and Multilinear Engine are examples of software packages for working with tensors.
---
paper_title: Best multilinear rank approximation of tensors with quasi-Newton methods on Grassmannians

paper_content:

In many fields of science, engineering, and economics large amounts of data are stored and there is a need to analyze these data in order to extract information for various purposes. Data mining is a general concept involving different tools for performing this kind of analysis. The development of mathematical models and efficient algorithms is of key importance. In this thesis we discuss algorithms for the reduced rank regression problem and algorithms for the computation of the best multilinear rank approximation of tensors. The first two papers deal with the reduced rank regression problem, which is encountered in the field of state-space subspace system identification. More specifically the problem is \[ \min_{\rank(X) = k} \det (B - X A)(B - X A)\tp, \] where $A$ and $B$ are given matrices and we want to find $X$ under a certain rank condition that minimizes the determinant. This problem is not properly stated since it involves implicit assumptions on $A$ and $B$ so that $(B - X A)(B - X A)\tp$ is never singular. This deficiency of the determinant criterion is fixed by generalizing the minimization criterion to rank reduction and volume minimization of the objective matrix. The volume of a matrix is defined as the product of its nonzero singular values. We give an algorithm that solves the generalized problem and identify properties of the input and output signals causing a singular objective matrix. Classification problems occur in many applications. The task is to determine the label or class of an unknown object. The third paper concerns with classification of handwritten digits in the context of tensors or multidimensional data arrays. Tensor and multilinear algebra is an area that attracts more and more attention because of the multidimensional structure of the collected data in various applications. Two classification algorithms are given based on the higher order singular value decomposition (HOSVD). The main algorithm makes a data reduction using HOSVD of 98--99 \% prior the construction of the class models. The models are computed as a set of orthonormal bases spanning the dominant subspaces for the different classes. An unknown digit is expressed as a linear combination of the basis vectors. The resulting algorithm achieves 5\% in classification error with fairly low amount of computations. The remaining two papers discuss computational methods for the best multilinear rank approximation problem \[ \min_{\cB} \| \cA - \cB\| \] where $\cA$ is a given tensor and we seek the best low multilinear rank approximation tensor $\cB$. This is a generalization of the best low rank matrix approximation problem. It is well known that for matrices the solution is given by truncating the singular values in the singular value decomposition (SVD) of the matrix. But for tensors in general the truncated HOSVD does not give an optimal approximation. For example, a third order tensor $\cB \in \RR^{I \x J \x K}$ with rank$(\cB) = (r_1,r_2,r_3)$ can be written as the product \[ \cB = \tml{X,Y,Z}{\cC}, \qquad b_{ijk}=\sum_{\lambda,\mu,\nu} x_{i\lambda} y_{j\mu} z_{k\nu} c_{\lambda\mu\nu}, \] where $\cC \in \RR^{r_1 \x r_2 \x r_3}$ and $X \in \RR^{I \times r_1}$, $Y \in \RR^{J \times r_2}$, and $Z \in \RR^{K \times r_3}$ are matrices of full column rank. Since it is no restriction to assume that $X$, $Y$, and $Z$ have orthonormal columns and due to these constraints, the approximation problem can be considered as a nonlinear optimization problem defined on a product of Grassmann manifolds. We introduce novel techniques for multilinear algebraic manipulations enabling means for theoretical analysis and algorithmic implementation. These techniques are used to solve the approximation problem using Newton and Quasi-Newton methods specifically adapted to operate on products of Grassmann manifolds. The presented algorithms are suited for small, large and sparse problems and, when applied on difficult problems, they clearly outperform alternating least squares methods, which are standard in the field.
---
paper_title: A Newton – Grassmann method for computing the Best MultiLinear Rank-( r 1 , r 2 , r 3 ) Approximation of a Tensor

paper_content:

We derive a Newton method for computing the best rank-$(r_1,r_2,r_3)$ approximation of a given $J\times K\times L$ tensor $\mathcal{A}$. The problem is formulated as an approximation problem on a product of Grassmann manifolds. Incorporating the manifold structure into Newton's method ensures that all iterates generated by the algorithm are points on the Grassmann manifolds. We also introduce a consistent notation for matricizing a tensor, for contracted tensor products and some tensor-algebraic manipulations, which simplify the derivation of the Newton equations and enable straightforward algorithmic implementation. Experiments show a quadratic convergence rate for the Newton-Grassmann algorithm.
---

Title: Overview of Recent Advances in Numerical Tensor Algebra

Section 1: INTRODUCTION
Description 1: This section introduces tensors, their applications, and the importance of tensor methods over traditional matrix methods. It provides a background on tensor compression, approximation, and decomposition techniques.

Section 2: RANK AND THE CP EXPANSION
Description 2: This section explores the concept of tensor rank and the CP (CANDECOMP/PARAFAC) decomposition, covering definitions, properties, uniqueness, and challenges in low-rank tensor approximation.

Section 3: MULTI-RANK AND THE HOSVD
Description 3: This section discusses the notion of multi-rank for tensors and introduces the Higher Order Singular Value Decomposition (HOSVD), explaining its calculation, properties, and applications.

Section 4: ALGORITHMS FOR LOW-RANK APPROXIMATION
Description 4: This section describes various algorithms for finding low-rank approximations of tensors, including the Alternating Least Squares (ALS) method and improvements on it. It explores different optimization techniques used in practical implementations.

Section 5: ALGORITHMS FOR LOW MULTI-RANK APPROXIMATION
Description 5: This section examines algorithms for obtaining low multi-rank approximations, highlighting techniques such as the Higher Order Orthogonal Iteration (HOOI) and methods involving manifold optimization.