On some problems of tensor calculus. I

Basic definitions of linear algebra and functional analysis are given. In particular, the definitions of a semigroup, group, ring, field, module, and linear space are given [1, 2, 3, 6]. A local theorem on the existence of homeomorphisms is stated. Definitions of the inner r-product, local inner product of tensors whose rank is not less than r, and of local norm of a tensor [22] are also given. Definitions are given and basic theorems and propositions are stated and proved concerning the linear dependence and independence of a system of tensors of any rank. Moreover, definitions and proofs of some theorems connected with orthogonal and biorthonormal tensor systems are given. The definition of a multiplicative basis (multibasis) is given and ways of construction bases of modules using bases of modules of smaller dimensions. In this connection, several theorems are stated and proved. Tensor modules of even orders and problems on finding eigenvalues and eigentensors of any even rank are studied in more detail than in [22]. Canonical representations of a tensor of any even rank are given. It is worth while to note that it was studied by the Soviet scientist I. N. Vekua, and an analogous problem for the elasticity modulus tensor was considered by the Polish scientist Ya. Rikhlevskii in 1983–1984.     

A categorical approach to Weyl modules

Global and local Weyl modules were introduced via generators and relations in the context of affine Lie algebras in [CP2] and were motivated by representations of quantum affine algebras. In [FL] a more general case was considered by replacing the polynomial ring with the coordinate ring of an algebraic variety and partial results analogous to those in [CP2] were obtained. In this paper we show that there is a natural definition of the local and global Weyl modules via homological properties. This characterization allows us to define the Weyl functor from the category of left modules of a commutative algebra to the category of modules for a simple Lie algebra. As an application we are able to understand the relationships of these functors to tensor products, generalizing results in [CP2] and [FL]. We also analyze the fundamental Weyl modules and show that, unlike the case of the affine Lie algebras, the Weyl functors need not be left exact.     

On the fast solution of Toeplitz-block linear systems arising in multivariate approximation theory

When constructing multivariate Padé approximants, highly structured linear systems arise in almost all existing definitions [10]. Until now little or no attention has been paid to fast algorithms for the computation of multivariate Padé approximants, with the exception of [17]. In this paper we show that a suitable arrangement of the unknowns and equations, for the multivariate definitions of Padé approximant under consideration, leads to a Toeplitz-block linear system with coefficient matrix of low displacement rank. Moreover, the matrix is very sparse, especially in higher dimensions. In Section 2 we discuss this for the so-called equation lattice definition and in Section 3 for the homogeneous definition of the multivariate Padé approximant. We do not discuss definitions based on multivariate generalizations of continued fractions [12, 25], or approaches that require some symbolic computations [6, 18]. In Section 4 we present an explicit formula for the factorization of the matrix that results from applying the displacement operator to the Toeplitz-block coefficient matrix. We then generalize the well-known fast Gaussian elimination procedure with partial pivoting developed in [14, 19], to deal with a rectangular block structure where the number and size of the blocks vary. We do not aim for a superfast solver because of the higher risk for instability. Instead we show how the developed technique can be combined with an easy interval arithmetic verification step. Numerical results illustrate the technique in Section 5.Research partly funded by FWO-Vlaanderen.     

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.     

Low‐rank approximation of tensors via sparse optimization

The goal of this paper is to find a low‐rank approximation for a given nth tensor. Specifically, we give a computable strategy on calculating the rank of a given tensor, based on approximating the solution to an NP‐hard problem. In this paper, we formulate a sparse optimization problem via an l₁‐regularization to find a low‐rank approximation of tensors. To solve this sparse optimization problem, we propose a rescaling algorithm of the proximal alternating minimization and study the theoretical convergence of this algorithm. Furthermore, we discuss the probabilistic consistency of the sparsity result and suggest a way to choose the regularization parameter for practical computation. In the simulation experiments, the performance of our algorithm supports that our method provides an efficient estimate on the number of rank‐one tensor components in a given tensor. Moreover, this algorithm is also applied to surveillance videos for low‐rank approximation.     

Spectral Algorithms for Tensor Completion

In the tensor completion problem, one seeks to estimate a low‐rank tensor based on a random sample of revealed entries. In terms of the required sample size, earlier work revealed a large gap between estimation with unbounded computational resources (using, for instance, tensor nuclear norm minimization) and polynomial‐time algorithms. Among the latter, the best statistical guarantees have been proved, for third‐order tensors, using the sixth level of the sum‐of‐squares (sos ) semidefinite programming hierarchy. However, the sos approach does not scale well to large problem instances. By contrast, spectral methods—based on unfolding or matricizing the tensor—are attractive for their low complexity, but have been believed to require a much larger sample size. This paper presents two main contributions. First, we propose a new method, based on unfolding, which outperforms naive ones for symmetric k^th‐order tensors of rank r. For this result we make a study of singular space estimation for partially revealed matrices of large aspect ratio, which may be of independent interest. For third‐order tensors, our algorithm matches the sos method in terms of sample size (requiring about rd^3/2 revealed entries), subject to a worse rank condition (r ≪ d^3/4 rather than r ≪ d^3/2). We complement this result with a different spectral algorithm for third‐order tensors in the overcomplete (r ≥ d) regime. Under a random model, this second approach succeeds in estimating tensors of rank d ≤ r ≪ d^3/2 from about rd^3/2 revealed entries. © 2018 Wiley Periodicals, Inc.     

A class of torsion-free abelian groups characterized by the ranks of their socles

Butler groups formed by factoring a completely decomposable group by a rank one group have been studied extensively. We call such groups, bracket groups. We study bracket modules over integral domains. In particular, we are interested in when any bracket R-module is R tensor a bracket group.     

Tensor ranks on tangent developable of Segre varieties

We describe the stratification by tensor rank of the points belonging to the tangent developable of any Segre variety. We give algorithms to compute the rank and a decomposition of a tensor belonging to the secant variety of lines of any Segre variety. We prove Comon's conjecture on the rank of symmetric tensors for those tensors belonging to tangential varieties to Veronese varieties.     

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.     

Chern Forms on Mapping Spaces

We state a Chern–Weil type theorem which is a generalization of a Chern–Weil type theorem for Fredholm structures stated by Freed in [4]. Using this result, we investigate Chern forms on based manifold of maps following two approaches, the first one using the Wodzicki residue, and the second one using renormalized traces of pseudo-differential operators along the lines of [1, 19, 20]. We specialize to the case to study current groups. Finally, we apply these results to a class of holomorphic connections on the loop group . In this last example, we precise Freed's construction [5] on the loop group: The cohomology of the first Chern form of any holomorphic connection in the class considered is given by the Kähler form.     

Convergence Properties of a Self-adaptive Levenberg-Marquardt Algorithm Under Local Error Bound Condition

We propose a new self-adaptive Levenberg-Marquardt algorithm for the system of nonlinear equations F(x) = 0. The Levenberg-Marquardt parameter is chosen as the product of ‖F_k‖^δ with δ being a positive constant, and some function of the ratio between the actual reduction and predicted reduction of the merit function. Under the local error bound condition which is weaker than the nonsingularity, we show that the Levenberg-Marquardt method converges superlinearly to the solution for δ∈ (0, 1), while quadratically for δ∈ [1, 2]. Numerical results show that the new algorithm performs very well for the nonlinear equations with high rank deficiency. This work is supported by Chinese NSFC grants 10401023 and 10501013, Research Grants for Young Teachers of Shanghai Jiao Tong University, and E-Institute of Shanghai Municipal Education Commission, N. E03004.     

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 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.     

Interpolation algorithm of Leverrier–Faddev type for polynomial matrices

We investigated an interpolation algorithm for computing outer inverses of a given polynomial matrix, based on the Leverrier–Faddeev method. This algorithm is a continuation of the finite algorithm for computing generalized inverses of a given polynomial matrix, introduced in [11]. Also, a method for estimating the degrees of polynomial matrices arising from the Leverrier–Faddeev algorithm is given as the improvement of the interpolation algorithm. Based on similar idea, we introduced methods for computing rank and index of polynomial matrix. All algorithms are implemented in the symbolic programming language MATHEMATICA , and tested on several different classes of test examples.     

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.     

New subclasses of block H-matrices with applications to parallel decomposition-type relaxation methods

The parallel decomposition-type relaxation methods for solving large sparse systems of linear equations on SIMD multiprocessor systems have been proposed in [3] and [2]. In case when the coefficient matrix of the linear system is a block -matrix, sufficient conditions for the convergence of methods given in [2], [3] have been further improved in [5] and [4]. From the practical point of view, the convergence area obtained there is not always suitable for computation, so we propose new, easily computable ones, for some special subclasses of block -matrices. Furthermore, this approach improves the already known convergence area for the class of block strictly diagonally dominant (SDD) matrices.     

Leibniz cohomology and the calculus of variations

A geometric interpretation of the Leibniz coboundary is given in terms of the calculus of variations. For a differentiable manifold M, Leibniz cohomology generalizes de Rham cohomology by including all tensors as cochains. When applied to two-tensors, the conditions for the vanishing of a Leibniz cochain are related to the necessary conditions to achieve an extreme value of the integral of the tensor over an immersed surface. A local formula for the coboundary of any tensor is given in terms of a coordinate chart, and the Leibniz coboundary of the Riemann curvature tensor is computed in terms of the derivative of sectional curvature.     

On the rank of 3×3×3-tensors

Let U, V and W be finite dimensional vector spaces over the same field. The rank of a tensor τ in U???V???W is the minimum dimension of a subspace of U???V???W containing τ and spanned by fundamental tensors, i.e. tensors of the form u???v???w for some u in U, v in V and w in W. We prove that if U, V and W have dimension three, then the rank of a tensor in U???V???W is at most six, and such a bound cannot be improved, in general. Moreover, we discuss how the techniques employed in the proof might be extended to prove upper bounds for the rank of a tensor in U???V???W when the dimensions of U, V and W are higher.     

Infinitesimal index: cohomology computations

In this note we study the equivariant cohomology with compact supports of the zeroes of the moment map for the cotangent bundle of a linear representation of a torus and some of its notable subsets, using the theory of the infinitesimal index, developed in [8]. We show that, in analogy to the case of equivariant K-theory dealt with in [7] using the index of transversally elliptic operators, we obtain isomorphisms with notable spaces of splines studied in [2], [3].