The rank of a 2 × 2 × 2 tensor

As computing power increases, many more problems in engineering and data analysis involve computation with tensors, or multi-way data arrays. Most applications involve computing a decomposition of a tensor into a linear combination of rank-1 tensors. Ideally, the decomposition involves a minimal number of terms, i.e. computation of the rank of the tensor. Tensor rank is not a straight-forward extension of matrix rank. A constructive proof based on an eigenvalue criterion is provided that shows when a 2?×?2?×?2 tensor over ? is rank-3 and when it is rank-2. The results are extended to show that n?×?n?×?2 tensors over ? have maximum possible rank n?+?k where k is the number of complex conjugate eigenvalue pairs of the matrices forming the two faces of the tensor cube.     

Factorization strategies for third-order tensors

Operations with tensors, or multiway arrays, have become increasingly prevalent in recent years. Traditionally, tensors are represented or decomposed as a sum of rank-1 outer products using either the CANDECOMP/PARAFAC (CP) or the Tucker models, or some variation thereof. Such decompositions are motivated by specific applications where the goal is to find an approximate such representation for a given multiway array. The specifics of the approximate representation (such as how many terms to use in the sum, orthogonality constraints, etc.) depend on the application.In this paper, we explore an alternate representation of tensors which shows promise with respect to the tensor approximation problem. Reminiscent of matrix factorizations, we present a new factorization of a tensor as a product of tensors. To derive the new factorization, we define a closed multiplication operation between tensors. A major motivation for considering this new type of tensor multiplication is to devise new types of factorizations for tensors which can then be used in applications.Specifically, this new multiplication allows us to introduce concepts such as tensor transpose, inverse, and identity, which lead to the notion of an orthogonal tensor. The multiplication also gives rise to a linear operator, and the null space of the resulting operator is identified. We extend the concept of outer products of vectors to outer products of matrices. All derivations are presented for third-order tensors. However, they can be easily extended to the order-p(p>3) case. We conclude with an application in image deblurring.     

Generalizing the column-row matrix decomposition to multi-way arrays

In this paper, we provide two generalizations of the CUR matrix decomposition Y=CUR (also known as pseudo-skeleton approximation method [1]) to the case of N-way arrays (tensors). These generalizations, which we called Fiber Sampling Tensor Decomposition types 1 and 2 (FSTD1 and FSTD2), provide explicit formulas for the parameters of a rank-(R,R,…,R) Tucker representation (the core tensor of size R×R×?×R and the matrix factors of sizes I_n×R, n=1,2,…N) based only on some selected entries of the original tensor. FSTD1 uses P^N-1(P?R)n-mode fibers of the original tensor while FSTD2 uses exactly R fibers in each mode as matrix factors, as suggested by the existence theorem provided in Oseledets et al. (2008) [2], with a core tensor defined in terms of the entries of a subtensor of size R×R×?×R. For N=2 our results are reduced to the already known CUR matrix decomposition where the core matrix is defined as the inverse of the intersection submatrix, i.e. U=W^-1. Additionally, we provide an adaptive type algorithm for the selection of proper fibers in the FSTD1 model which is useful for large scale applications. Several numerical results are presented showing the performance of our FSTD1 Adaptive Algorithm compared to two recently proposed approximation methods for 3-way tensors.     

Structured multi-way arrays and their applications

Based on the structure of the rank-1 matrix and the different unfolding ways of the tensor, we present two types of structured tensors which contain the rank-1 tensors as special cases. We study some properties of the ranks and the best rank-r approximations of the structured tensors. By using the upper-semicontinuity of the matrix rank, we show that for the structured tensors, there always exist the best rank-r approximations. This can help one to better understand the sequential unfolding singular value decomposition (SVD) method for tensors proposed by J. Salmi et al. [IEEE Trans Signal Process, 2009, 57(12): 4719–4733] and offer a generalized way of low rank approximations of tensors. Moreover, we apply the structured tensors to estimate the upper and lower bounds of the best rank-1 approximations of the 3rd-order and 4th-order tensors, and to distinguish the well written and non-well written digits.     

Subtracting a best rank‐1 approximation from p × p × 2(p≥2) tensors

We introduce one special form of the ptimesp × 2 (p≥2) tensors by multilinear orthonormal transformations, and present some interesting properties of the special form. Through discussing on the special form, we provide a solution to one conjecture proposed by Stegeman and Comon in a conference paper (Proceedings of the EUSIPCO 2009 Conference, Glasgow, Scotland, 2009), and reveal an important conclusion about subtracting a best rank‐1 approximations from p × p × 2 tensors of the special form. All of these confirm that consecutively subtracting the best rank‐1 approximations may not lead to a best low rank approximation of a tensor. Numerical examples show the correctness of our theory. Copyright © 2011 John Wiley & Sons, Ltd.     

The Average Condition Number of Most Tensor Rank Decomposition Problems is Infinite

The tensor rank decomposition, or canonical polyadic decomposition, is the decomposition of a tensor into a sum of rank-1 tensors. The condition number of the tensor rank decomposition measures the sensitivity of the rank-1 summands with respect to structured perturbations. Those are perturbations preserving the rank of the tensor that is decomposed. On the other hand, the angular condition number measures the perturbations of the rank-1 summands up to scaling. We show for random rank-2 tensors that the expected value of the condition number is infinite for a wide range of choices of the density. Under a mild additional assumption, we show that the same is true for most higher ranks \(r\ge 3\) as well. In fact, as the dimensions of the tensor tend to infinity, asymptotically all ranks are covered by our analysis. On the contrary, we show that rank-2 tensors have finite expected angular condition number. Based on numerical experiments, we conjecture that this could also be true for higher ranks. Our results underline the high computational complexity of computing tensor rank decompositions. We discuss consequences of our results for algorithm design and for testing algorithms computing tensor rank decompositions.

     

Procrustes problems and associated approximation problems for matrices with k-involutory symmetries

We say that a matrix R∈C^n×n is k-involutary if its minimal polynomial is x^k-1 for some k?2, so R^k-1=R^-1 and the eigenvalues of R are 1,ζ,ζ²,…,ζ^k-1, where ζ=e^2πi/k. Let α,μ∈{0,1,…,k-1}. If R∈C^m×m, A∈C^m×n, S∈C^n×n and R and S are k-involutory, we say that A is (R,S,μ)-symmetric if RAS^-1=ζ^μA, and A is (R,S,α,μ)-symmetric if RAS^-α=ζ^μA.Let L be the class of m×n(R,S,μ)-symmetric matrices or the class of m×n(R,S,α,μ)-symmetric matrices. Given X∈C^n×t and B∈C^m×t, we characterize the matrices A in L that minimize ‖AX-B‖ (Frobenius norm), and, given an arbitrary W∈C^m×n, we find the unique matrix A∈L that minimizes both ‖AX-B‖ and ‖A-W‖. We also obtain necessary and sufficient conditions for existence of A∈L such that AX=B, and, assuming that the conditions are satisfied, characterize the set of all such A.     

Third-Order Tensors as Linear Operators on a Space of Matrices

A recently proposed tensor-tensor multiplication (M.E. Kilmer, C.D. Martin, L. Perrone, A Third-Order Generalization of the Matrix SVD as a Product of Third-Order Tensors, Tech. Rep. TR-2008-4, Tufts University, October 2008) opens up new avenues to understanding the action of n×n×n tensors on a space of n×n matrices. In particular it emphasizes the need to understand the space of objects upon which tensors act. This paper defines a free module and shows that every linear transformation on that module can be represented by tensor multiplication. In addition, it presents a generalization of ideas of eigenvalue and eigenvector to the space of n×n×n tensors.     

Strong linear preservers of rank reverse permutability on triangular matrices

Let F be a field with ∣F∣ > 2 and T_n(F) be the set of all n × n upper triangular matrices, where n ? 2. Let k ? 2 be a given integer. A k-tuple of matrices A₁, …, A_k ∈ T_n(F) is called rank reverse permutable if rank(A₁ A₂ ? A_k) = rank(A_k A_k−1 ? A₁). We characterize the linear maps on T_n(F) that strongly preserve the set of rank reverse permutable matrix k-tuples.     

A general product of tensors with applications

We study a general product of two n  -dimensional tensors A$\mathbb{A}$ and B$\mathbb{B}$ with orders m?2$m?2$ and k?1$k?1$. This product satisfies the associative law, and is a generalization of the usual matrix product. Using this product, many concepts and known results of tensors can be simply expressed and/or proved, and a number of applications of it will be given. Using the associative law of this tensor product and some properties on the resultant of a system of homogeneous equations on n variables, we define the similarity and congruence of tensors (which are also the generalizations of the corresponding relations for matrices), and prove that similar tensors have the same characteristic polynomials, thus the same spectra. We study two special kinds of similarity: permutational similarity and diagonal similarity, and their applications in the study of the spectra of hypergraphs and nonnegative irreducible tensors. We also define the direct product of tensors (in matrix case it is also called the Kronecker product), and give its applications in the study of the spectra of two kinds of the products of hypergraphs. We also give applications of this general product in the study of nonnegative tensors, including a characterization of primitive tensors, the upper bounds of primitive degrees and the cyclic indices of some nonnegative irreducible tensors.     

Preservers of pairs of bivectors with bounded distance

We extend Liu’s fundamental theorem of the geometry of alternate matrices to the second exterior power of an infinite dimensional vector space and also use her theorem to characterize surjective mappings T from the vector space V of all n×n alternate matrices over a field with at least three elements onto itself such that for any pair A, B in V, rank(A-B)?2k if and only if rank(T(A)-T(B))?2k, where k is a fixed positive integer such that n?2k+2 and k?2.     

Low rank Tucker-type tensor approximation to classical potentials

This paper investigates best rank-(r ₁,..., r _d ) Tucker tensor approximation of higher-order tensors arising from the discretization of linear operators and functions in ℝ ^d . Super-convergence of the best rank-(r ₁,..., r _d ) Tucker-type decomposition with respect to the relative Frobenius norm is proven. Dimensionality reduction by the two-level Tucker-to-canonical approximation is discussed. Tensor-product representation of basic multi-linear algebra operations is considered, including inner, outer and Hadamard products. Furthermore, we focus on fast convolution of higher-order tensors represented by the Tucker/canonical models. Optimized versions of the orthogonal alternating least-squares (ALS) algorithm is presented taking into account the different formats of input data. We propose and test numerically the mixed CT-model, which is based on the additive splitting of a tensor as a sum of canonical and Tucker-type representations. It allows to stabilize the ALS iteration in the case of “ill-conditioned” tensors. The best rank-(r ₁,..., r _d ) Tucker decomposition is applied to 3D tensors generated by classical potentials, for example and with x, y ∈ ℝ ^d . Numerical results for tri-linear decompositions illustrate exponential convergence in the Tucker rank, and robustness of the orthogonal ALS iteration.      

Symmetry transformations for square sliced three-way arrays, with applications to their typical rank

The typical 3-tensorial rank has been much studied over algebraically closed fields, but very little has been achieved in the way of results pertaining to the real field. The present paper examines the typical 3-tensorial rank over the real field, when the slices of the array involved are square matrices. The typical rank of 3 × 3 × 3 arrays is shown to be five. The typical rank of p × q × q arrays is shown to be larger than q + 1 unless there are only two slices (p = 2), or there are three slices of order 2 × 2 (p = 3 and q = 2). The key result is that when the rank is q + 1, there usually exists a rank-preserving transformation of the array to one with symmetric slices.     

A concise proof of Kruskal’s theorem on tensor decomposition

A theorem of J. Kruskal from 1977, motivated by a latent-class statistical model, established that under certain explicit conditions the expression of a third-order tensor as the sum of rank-1 tensors is essentially unique. We give a new proof of this fundamental result, which is substantially shorter than both the original one and recent versions along the original lines.     

2-Adic valuations of certain ratios of products of factorials and applications

We prove the conjecture of Falikman-Friedland-Loewy on the parity of the degrees of projective varieties of n×n complex symmetric matrices of rank at most k. We also characterize the parity of the degrees of projective varieties of n×n complex skew symmetric matrices of rank at most 2p. We give recursive relations which determine the parity of the degrees of projective varieties of m×n complex matrices of rank at most k. In the case the degrees of these varieties are odd, we characterize the minimal dimensions of subspaces of n×n skew symmetric real matrices and of m×n real matrices containing a nonzero matrix of rank at most k. The parity questions studied here are also of combinatorial interest since they concern the parity of the number of plane partitions contained in a given box, on the one hand, and the parity of the number of symplectic tableaux of rectangular shape, on the other hand.     

Bijective linear maps on semimodules spanned by Boolean matrices of fixed rank

Let M_m,n(B) be the semimodule of all m×n Boolean matrices where B is the Boolean algebra with two elements. Let k be a positive integer such that 2?k?min(m,n). Let B(m,n,k) denote the subsemimodule of M_m,n(B) spanned by the set of all rank k matrices. We show that if T is a bijective linear mapping on B(m,n,k), then there exist permutation matrices P and Q such that T(A)=PAQ for all A∈B(m,n,k) or m=n and T(A)=PA^tQ for all A∈B(m,n,k). This result follows from a more general theorem we prove concerning the structure of linear mappings on B(m,n,k) that preserve both the weight of each matrix and rank one matrices of weight k². Here the weight of a Boolean matrix is the number of its nonzero entries.     

The Number of Singular Vector Tuples and Uniqueness of Best Rank-One Approximation of Tensors

In this paper we discuss the notion of singular vector tuples of a complex-valued \(d\) -mode tensor of dimension \(m_1\times \cdots \times m_d\) . We show that a generic tensor has a finite number of singular vector tuples, viewed as points in the corresponding Segre product. We give the formula for the number of singular vector tuples. We show similar results for tensors with partial symmetry. We give analogous results for the homogeneous pencil eigenvalue problem for cubic tensors, i.e., \(m_1=\cdots =m_d\) . We show the uniqueness of best approximations for almost all real tensors in the following cases: rank-one approximation; rank-one approximation for partially symmetric tensors (this approximation is also partially symmetric); rank- \((r_1,\ldots ,r_d)\) approximation for \(d\) -mode tensors.     

Subtotally positive and Monge matrices

A real matrix is called k-subtotally positive if the determinants of all its submatrices of order at most k are positive. We show that for an m × n matrix, only mn inequalities determine such class for every k, 1 ? k ? min(m,n). Spectral properties of square k-subtotally positive matrices are studied. Finally, completion problems for 2-subtotally positive matrices and their additive counterpart, the anti-Monge matrices, are investigated. Since totally positive matrices are 2-subtotally positive as well, the presented necessary conditions for this completion problem are also necessary conditions for totally positive matrices.     

Best constants for tensor products of Bernstein type operators

For the tensor product of k copies of the same one-dimensional Bernstein-type operator L, we consider the problem of finding the best constant in preservation of the usual modulus of continuity for the lp-norm on Rk. Two main results are obtained: the first one gives both necessary and sufficient conditions in order that 1+k1−1/p is the best uniform constant for a single operator; the second one gives sufficient conditions in order that 1+k1−1/p is the best uniform constant for a family of operators. The general results are applied to several classical families of operators usually considered in approximation theory. Throughout the paper, probabilistic concepts and methods play an important role.