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.

     

A fast algorithm for the spectral radii of weakly reducible nonnegative tensors

In this paper, we propose a fast algorithm for computing the spectral radii of symmetric nonnegative tensors. In particular, by this proposed algorithm, we are able to obtain the spectral radii of weakly reducible symmetric nonnegative tensors without requiring the partition of the tensors. As we know, it is very costly to determine the partition for large‐sized weakly reducible tensors. Numerical results are reported to show that the proposed algorithm is efficient and also able to compute the spectral radii of large‐sized tensors. As an application, we present an algorithm for testing the positive definiteness of Z‐tensors. By this algorithm, it is guaranteed to determine the positive definiteness for any Z‐tensor.     

Copositivity Detection of Tensors: Theory and Algorithm

A symmetric tensor is called copositive if it generates a multivariate form taking nonnegative values over the nonnegative orthant. Copositive tensors have found important applications in polynomial optimization, tensor complementarity problems and vacuum stability of a general scalar potential. In this paper, we consider copositivity detection of tensors from both theoretical and computational points of view. After giving several necessary conditions for copositive tensors, we propose several new criteria for copositive tensors based on the representation of the multivariate form in barycentric coordinates with respect to the standard simplex and simplicial partitions. It is verified that, as the partition gets finer and finer, the concerned conditions eventually capture all strictly copositive tensors. Based on the obtained theoretical results with the help of simplicial partitions, we propose a numerical method to judge whether a tensor is copositive or not. The preliminary numerical results confirm our theoretical findings.     

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.     

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 may increase tensor rank

It has been shown that a best rank-R approximation of an order-k tensor may not exist when R?2 and k?3. 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 2×2×2 tensors, with symmetric tensors as a special case. Regardless of the symmetry, we show that for generic 2×2×2 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.     

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.     

On computing minimal <Emphasis Type="Italic">H</Emphasis>-eigenvalue of sign-structured tensors

Finding the minimal H-eigenvalue of tensors is an important topic in tensor computation and numerical multilinear algebra. This paper is devoted to a sum-of-squares (SOS) algorithm for computing the minimal H-eigenvalues of tensors with some sign structures called extended essentially nonnegative tensors (EEN-tensors), which includes nonnegative tensors as a subclass. In the even-order symmetric case, we first discuss the positive semi-definiteness of EEN-tensors, and show that a positive semi-definite EEN-tensor is a nonnegative tensor or an M-tensor or the sum of a nonnegative tensor and an M-tensor, then we establish a checkable sufficient condition for the SOS decomposition of EEN-tensors. Finally, we present an efficient algorithm to compute the minimal H-eigenvalues of even-order symmetric EEN-tensors based on the SOS decomposition. Numerical experiments are given to show the efficiency of the proposed algorithm.     

Finding the Maximum Eigenvalue of Essentially Nonnegative Symmetric Tensors via Sum of Squares Programming

Finding the maximum eigenvalue of a tensor is an important topic in tensor computation and multilinear algebra. Recently, for a tensor with nonnegative entries (which we refer it as a nonnegative tensor), efficient numerical schemes have been proposed to calculate its maximum eigenvalue based on a Perron–Frobenius-type theorem. In this paper, we consider a new class of tensors called essentially nonnegative tensors, which extends the concept of nonnegative tensors, and examine the maximum eigenvalue of an essentially nonnegative tensor using the polynomial optimization techniques. We first establish that finding the maximum eigenvalue of an essentially nonnegative symmetric tensor is equivalent to solving a sum of squares of polynomials (SOS) optimization problem, which, in its turn, can be equivalently rewritten as a semi-definite programming problem. Then, using this sum of squares programming problem, we also provide upper and lower estimates for the maximum eigenvalue of general symmetric tensors. These upper and lower estimates can be calculated in terms of the entries of the tensor. Numerical examples are also presented to illustrate the significance of the results.     

Rank-<Emphasis Type="Italic">r</Emphasis> decomposition of symmetric tensors

An algorithm is presented for decomposing a symmetric tensor into a sum of rank-1 symmetric tensors. For a given tensor, by using apolarity, catalecticant matrices and the condition that the mapping matrices are commutative, the rank of the tensor can be obtained by iteration. Then we can find the generating polynomials under a selected basis set. The decomposition can be constructed by the solutions of generating polynomials under the condition that the solutions are all distinct which can be guaranteed by the commutative property of the matrices. Numerical examples demonstrate the efficiency and accuracy of the proposed method.     

A semidefinite program approach for computing the maximum eigenvalue of a class of structured tensors and its applications in hypergraphs and copositivity test

Finding the maximum eigenvalue of a symmetric tensor is an important topic in tensor computation and numerical multilinear algebra. In this paper, we introduce a new class of structured tensors called W‐tensors, which not only extends the well‐studied nonnegative tensors by allowing negative entries but also covers several important tensors arising naturally from spectral hypergraph theory. We then show that finding the maximum H‐eigenvalue of an even‐order symmetric W‐tensor is equivalent to solving a structured semidefinite program and hence can be validated in polynomial time. This yields a highly efficient semidefinite program algorithm for computing the maximum H‐eigenvalue of W‐tensors and is based on a new structured sums‐of‐squares decomposition result for a nonnegative polynomial induced by W‐tensors. Numerical experiments illustrate that the proposed algorithm can successfully find the maximum H‐eigenvalue of W‐tensors with dimension up to 10,000, subject to machine precision. As applications, we provide a polynomial time algorithm for computing the maximum H‐eigenvalues of large‐size Laplacian tensors of hyperstars and hypertrees, where the algorithm can be up to 13 times faster than the state‐of‐the‐art numerical method introduced by Ng, Qi, and Zhou in 2009. Finally, we also show that the proposed algorithm can be used to test the copositivity of a multivariate form associated with symmetric extended Z‐tensors, whose order may be even or odd.     

Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework

We review algorithms developed for nonnegative matrix factorization (NMF) and nonnegative tensor factorization (NTF) from a unified view based on the block coordinate descent (BCD) framework. NMF and NTF are low-rank approximation methods for matrices and tensors in which the low-rank factors are constrained to have only nonnegative elements. The nonnegativity constraints have been shown to enable natural interpretations and allow better solutions in numerous applications including text analysis, computer vision, and bioinformatics. However, the computation of NMF and NTF remains challenging and expensive due the constraints. Numerous algorithmic approaches have been proposed to efficiently compute NMF and NTF. The BCD framework in constrained non-linear optimization readily explains the theoretical convergence properties of several efficient NMF and NTF algorithms, which are consistent with experimental observations reported in literature. In addition, we discuss algorithms that do not fit in the BCD framework contrasting them from those based on the BCD framework. With insights acquired from the unified perspective, we also propose efficient algorithms for updating NMF when there is a small change in the reduced dimension or in the data. The effectiveness of the proposed updating algorithms are validated experimentally with synthetic and real-world data sets.     

Strictly nonnegative tensors and nonnegative tensor partition

We introduce a new class of nonnegative tensors—strictly nonnegative tensors.A weakly irreducible nonnegative tensor is a strictly nonnegative tensor but not vice versa.We show that the spectral radius of a strictly nonnegative tensor is always positive.We give some necessary and su?cient conditions for the six wellconditional classes of nonnegative tensors,introduced in the literature,and a full relationship picture about strictly nonnegative tensors with these six classes of nonnegative tensors.We then establish global R-linear convergence of a power method for finding the spectral radius of a nonnegative tensor under the condition of weak irreducibility.We show that for a nonnegative tensor T,there always exists a partition of the index set such that every tensor induced by the partition is weakly irreducible;and the spectral radius of T can be obtained from those spectral radii of the induced tensors.In this way,we develop a convergent algorithm for finding the spectral radius of a general nonnegative tensor without any additional assumption.Some preliminary numerical results show the feasibility and effectiveness of the algorithm.     

Nonnegative tensors revisited: plane stochastic tensors

In this paper, we develop and enrich the theory of nonnegative tensors. We define the sign nonsingular tensors and establish the relationship between the combinatorial determinant and the permanent of nonnegative tensors. We generalize the results from doubly stochastic matrices to totally plane stochastic tensors and obtain a probabilistic algorithm for locating a positive diagonal in a nonnegative tensor under certain conditions. We form a normalization algorithm to convert some nonnegative tensors to plane stochastic tensors. We obtain a lower bound for the minimum of the axial N-index assignment problem by means of the set of plane stochastic tensors.     

-inclusion sets for eigenvalues of a tensor

In this paper, we mainly focus on new inclusion sets for eigenvalues of a tensor. First, we propose new inclusion sets for eigenvalues of a tensor, which are sharper than some existing inclusion sets, and obtain the law of distribution of the number of eigenvalues for a tensor. Second, two new classes of tensors are introduced. Third, some bounds on the spectral radii for nonnegative tensors are given. Fourth, some checkable sufficient conditions for the positive definiteness (positive semidefiniteness) of some classes of even-order real symmetric tensors are obtained.     

An always convergent algorithm for the largest eigenvalue of an irreducible nonnegative tensor

In this paper we propose an iterative method to calculate the largest eigenvalue of a nonnegative tensor. We prove this method converges for any irreducible nonnegative tensor. We also apply this method to study the positive definiteness of a multivariate form.     

On the Nuclear Norm and the Singular Value Decomposition of Tensors

Finding the rank of a tensor is a problem that has many applications. Unfortunately, it is often very difficult to determine the rank of a given tensor. Inspired by the heuristics of convex relaxation, we consider the nuclear norm instead of the rank of a tensor. We determine the nuclear norm of various tensors of interest. Along the way, we also do a systematic study various measures of orthogonality in tensor product spaces and we give a new generalization of the singular value decomposition to higher-order tensors.     

On a Class of Semi-Positive Tensors in Tensor Complementarity Problem

Recently, the tensor complementarity problem has been investigated in the literature. In this paper, we extend a class of structured matrices to higher-order tensors; the corresponding tensor complementarity problem has a unique solution for any nonzero nonnegative vector. We discuss their relationships with semi-positive tensors and strictly semi-positive tensors. We also study the property of such a structured tensor. We show that every principal sub-tensor of such a structured tensor is still a structured tensor in the same class, with a lower dimension. We also give two equivalent formulations of such a structured tensor.     

Standard tensor and its applications in problem of singular values of tensors

In this paper, first we give the definition of standard tensor. Then we clarify the relationship between weakly irreducible tensors and weakly irreducible polynomial maps by the definition of standard tensor. And we prove that the singular values of rectangular tensors are the special cases of the eigen-values of standard tensors related to rectangular tensors. Based on standard tensor, we present a generalized version of the weak Perron-Frobenius Theorem of nonnegative rectangular tensors under weaker conditions. Furthermore, by studying standard tensors, we get some new results of rectangular tensors. Besides, by using the special structure of standard tensors corresponding to nonnegative rectangular tensors, we show that the largest singular value is really geometrically simple under some weaker conditions.     

Probabilistic inference with noisy-threshold models based on a CP tensor decomposition

The specification of conditional probability tables (CPTs) is a difficult task in the construction of probabilistic graphical models. Several types of canonical models have been proposed to ease that difficulty. Noisy-threshold models generalize the two most popular canonical models: the noisy-or and the noisy-and. When using the standard inference techniques the inference complexity is exponential with respect to the number of parents of a variable. More efficient inference techniques can be employed for CPTs that take a special form. CPTs can be viewed as tensors. Tensors can be decomposed into linear combinations of rank-one tensors, where a rank-one tensor is an outer product of vectors. Such decomposition is referred to as Canonical Polyadic (CP) or CANDECOMP-PARAFAC (CP) decomposition. The tensor decomposition offers a compact representation of CPTs which can be efficiently utilized in probabilistic inference. In this paper we propose a CP decomposition of tensors corresponding to CPTs of threshold functions, exactly ℓ-out-of-k functions, and their noisy counterparts. We prove results about the symmetric rank of these tensors in the real and complex domains. The proofs are constructive and provide methods for CP decomposition of these tensors. An analytical and experimental comparison with the parent-divorcing method (which also has a polynomial complexity) shows superiority of the CP decomposition-based method. The experiments were performed on subnetworks of the well-known QMRT-DT network generalized by replacing noisy-or by noisy-threshold models.