CP decomposition for tensors via alternating least squares with QR decomposition

The CP tensor decomposition is used in applications such as machine learning and signal processing to discover latent low-rank structure in multidimensional data. Computing a CP decomposition via an alternating least squares (ALS) method reduces the problem to several linear least squares problems. The standard way to solve these linear least squares subproblems is to use the normal equations, which inherit special tensor structure that can be exploited for computational efficiency. However, the normal equations are sensitive to numerical ill-conditioning, which can compromise the results of the decomposition. In this paper, we develop versions of the CP-ALS algorithm using the QR decomposition and the singular value decomposition, which are more numerically stable than the normal equations, to solve the linear least squares problems. Our algorithms utilize the tensor structure of the CP-ALS subproblems efficiently, have the same complexity as the standard CP-ALS algorithm when the input is dense and the rank is small, and are shown via examples to produce more stable results when ill-conditioning is present. Our MATLAB implementation achieves the same running time as the standard algorithm for small ranks, and we show that the new methods can obtain lower approximation error.     

A semidefinite algorithm for completely positive tensor decomposition

A symmetric tensor, which has a symmetric nonnegative decomposition, is called a completely positive tensor. In this paper, we characterize the completely positive tensor as a truncated moment sequence, and transform the problem of checking whether a tensor is completely positive to checking whether its corresponding truncated moment sequence admits a representing measure, then present a semidefinite algorithm to solve it. If a tensor is not completely positive, a certificate for it can be obtained; if it is completely positive, a nonnegative decomposition can be obtained.     

Completely positive tensors in the complex field

In this paper, we introduce the complex completely positive tensor, which has a symmetric complex decomposition with all real and imaginary parts of the decomposition vectors being non-negative. Some properties of the complex completely positive tensor are given. A semidefinite algorithm is also proposed for checking whether a complex tensor is complex completely positive or not. If a tensor is not complex completely positive, a certificate for it can be obtained; if it is complex completely positive, a complex completely positive decomposition can be obtained.     

Symmetric tensor decomposition by alternating gradient descent

The symmetric tensor decomposition problem is a fundamental problem in many fields, which appealing for investigation. In general, greedy algorithm is used for tensor decomposition. That is, we first find the largest singular value and singular vector and subtract the corresponding component from tensor, then repeat the process. In this article, we focus on designing one effective algorithm and giving its convergence analysis. We introduce an exceedingly simple and fast algorithm for rank-one approximation of symmetric tensor decomposition. Throughout variable splitting, we solve symmetric tensor decomposition problem by minimizing a multiconvex optimization problem. We use alternating gradient descent algorithm to solve. Although we focus on symmetric tensors in this article, the method can be extended to nonsymmetric tensors in some cases. Additionally, we also give some theoretical analysis about our alternating gradient descent algorithm. We prove that alternating gradient descent algorithm converges linearly to global minimizer. We also provide numerical results to show the effectiveness of the algorithm.     

Singular values of a real rectangular tensor

Real rectangular tensors arise from the strong ellipticity condition problem in solid mechanics and the entanglement problem in quantum physics. In this paper, we systematically study properties of singular values of a real rectangular tensor, and give an algorithm to find the largest singular value of a nonnegative rectangular tensor. Numerical results show that the algorithm is efficient.     

Blockwise acceleration of alternating least squares for canonical tensor decomposition

The canonical polyadic (CP) decomposition of tensors is one of the most important tensor decompositions. While the well-known alternating least squares (ALS) algorithm is often considered the workhorse algorithm for computing the CP decomposition, it is known to suffer from slow convergence in many cases and various algorithms have been proposed to accelerate it. In this article, we propose a new accelerated ALS algorithm that accelerates ALS in a blockwise manner using a simple momentum-based extrapolation technique and a random perturbation technique. Specifically, our algorithm updates one factor matrix (i.e., block) at a time, as in ALS, with each update consisting of a minimization step that directly reduces the reconstruction error, an extrapolation step that moves the factor matrix along the previous update direction, and a random perturbation step for breaking convergence bottlenecks. Our extrapolation strategy takes a simpler form than the state-of-the-art extrapolation strategies and is easier to implement. Our algorithm has negligible computational overheads relative to ALS and is simple to apply. Empirically, our proposed algorithm shows strong performance as compared to the state-of-the-art acceleration techniques on both simulated and real tensors.     

Regularity of ghosts in tensor tomography

We study on a compact Riemannian manifold with boundary the ray transform I which integrates symmetric tensor fields over geodesics. A tensor field is said to be a nontrivial ghost if it is in the kernel of I and is L²-orthogonal to all potential fields. We prove that a nontrivial ghost is smooth in the case of a simple metric. This implies that the wave front set of the solenoidal part of a field f can be recovered from the ray transform If. We give an explicit procedure for recovering the wave front set.     

Tensor Product Weight Representations of the Neveu–Schwarz Algebra

We study the tensor product of a highest weight module with an intermediate series module over the Neveu–Schwarz algebra. If the highest weight module is nontrivial, the weight spaces of such a tensor product are infinite dimensional. We show that such a tensor product is indecomposable. Using a “shifting technique” developed by H. Chen, X. Guo, and K. Zhao for the Virasoro algebra case, we give necessary and sufficient conditions for such a tensor product to be irreducible. Furthermore, we give necessary and sufficient conditions for two such tensor products to be isomorphic.     

A general approach to the analysis of controlled perturbation algorithms

Controlled Perturbation (CP, for short) is an approach to obtaining efficient and robust implementations of a large class of geometric algorithms using the computational speed of multiple precision floating point arithmetic (compared to exact arithmetic), while bypassing the precision problems by perturbation. It also allows algorithms to be written without consideration of degenerate cases. CP replaces the input objects by a set of randomly perturbed (moved, scaled, stretched, etc.) objects and protects the evaluation of geometric predicates by guards. The execution is aborted if a guard indicates that the evaluation of a predicate with floating point arithmetic may return an incorrect result. If the execution is aborted, the algorithm is rerun on a new perturbation and maybe with a higher precision of the floating point arithmetic. If the algorithm runs to completion, it returns the correct output for the perturbed input.The analysis of CP algorithms relates various parameters: the perturbation amount, the arithmetic precision, the range of input values, and the number of input objects. We present a general methodology for analyzing CP algorithms. It is powerful enough to analyze all geometric predicates that are formulated as signs of polynomials.     

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.     

Tensor absolute value equations

This paper is concerned with solving some structured multi-linear systems, which are called tensor absolute value equations. This kind of absolute value equations is closely related to tensor complementarity problems and is a generalization of the well-known absolute value equations in the matrix case. We prove that tensor absolute value equations are equivalent to some special structured tensor complementary problems. Some sufficient conditions are given to guarantee the existence of solutions for tensor absolute value equations. We also propose a Levenberg-Marquardt-type algorithm for solving some given tensor absolute value equations and preliminary numerical results are reported to indicate the efficiency of the proposed algorithm.     

Investigation of boundary value problems for plane-parallel fluid flows in an anisotropic porous medium

We pose and consider the first and second boundary value problems and the transmission boundary value problem for plane-parallel steady flows in an anisotropic porous medium characterized by the permeability tensor, which is not necessarily symmetric. If the anisotropic medium is homogeneous, then the solutions of the problems in the case of canonical boundaries (a straight line or an ellipse) can be found in closed form, and in the case of arbitrary smooth boundaries, the study of these problems can be reduced with the use of Cauchy type integrals to the solution of inhomogeneous integral equations of the second kind. These problems are mathematical models of topical practical problems that arise, for example, in fluid (water or oil) recovery from natural soil strata of complicated geological structure.     

Low-rank tensor completion by Riemannian optimization

In tensor completion, the goal is to fill in missing entries of a partially known tensor under a low-rank constraint. We propose a new algorithm that performs Riemannian optimization techniques on the manifold of tensors of fixed multilinear rank. More specifically, a variant of the nonlinear conjugate gradient method is developed. Paying particular attention to efficient implementation, our algorithm scales linearly in the size of the tensor. Examples with synthetic data demonstrate good recovery even if the vast majority of the entries are unknown. We illustrate the use of the developed algorithm for the recovery of multidimensional images and for the approximation of multivariate functions.     

具有等级约束的三台机排序问题的可中断在线算法

研究具有等级约束的三台机在线排序问题．机器和工件的等级数均为1或2,工件只能在等级数不超过自身等级的机器上加工,且加工允许中断,目标是极小化最大工件完工时间．如果有两台机器等级为1,给出竞争比为3／2的在线算法,并证明算法是最好可能的;如果只有一台等级为1的机器,也给出竞争比为3／2的在线算法．     

Computational homogenization of materials with small deformation to determine configurational forces

In this work the mechanical boundary condition for the micro problem in a two-scaled homogenization using a FE² approach is discussed. The strain tensor is often used in the literature for small deformation problem to determine the boundary conditions for the boundary value problem on the micro level. This strain tensor based boundary condition gives consistent homogenized mechanical quantities, e.g. stress tensor and elasticity tensor, but the present work points out that it leads to unphysical homogenized configurational forces. Instead, we propose a displacement gradient based boundary condition for the micro problem. Results show that the displacement gradient based boundary condition can give not only the consistent homogenized mechanical quantities but also the appropriate homogenized configurational forces. The interpretation of the displacement gradient based boundary condition is discussed. (© 2012 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimal invariant Markov basis for sampling contingency tables with fixed marginals

In this paper we define an invariant Markov basis for a connected Markov chain over the set of contingency tables with fixed marginals and derive some characterizations of minimality of the invariant basis. We also give a necessary and sufficient condition for uniqueness of minimal invariant Markov bases. By considering the invariance, Markov bases can be presented very concisely. As an example, we present minimal invariant Markov bases for all 2 × 2 × 2 × 2 hierarchical models. The invariance here refers to permutation of indices of each axis of the contingency tables. If the categories of each axis do not have any order relations among them, it is natural to consider the action of the symmetric group on each axis of the contingency table. A general algebraic algorithm for obtaining a Markov basis was given by Diaconis and Sturmfels (The Annals of Statistics, 26, 363–397, 1998). Their algorithm is based on computing Gröbner basis of a well-specified polynomial ideal. However, the reduced Gröbner basis depends on the particular term order and is not symmetric. Therefore, it is of interest to consider the properties of invariant Markov basis.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

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.     

Robust tensor completion using transformed tensor singular value decomposition

In this article, we study robust tensor completion by using transformed tensor singular value decomposition (SVD), which employs unitary transform matrices instead of discrete Fourier transform matrix that is used in the traditional tensor SVD. The main motivation is that a lower tubal rank tensor can be obtained by using other unitary transform matrices than that by using discrete Fourier transform matrix. This would be more effective for robust tensor completion. Experimental results for hyperspectral, video and face datasets have shown that the recovery performance for the robust tensor completion problem by using transformed tensor SVD is better in peak signal‐to‐noise ratio than that by using Fourier transform and other robust tensor completion methods.     

Graph algorithm for partially-linear problems obtained by absolute value functions

The increasing interest in partially-linear models is caused by their role in economics, technology and mathematics. Every continuous partially-linear function with a finite number of linear parts can be formulated by means of linear function and absolute value functions. If we presebt every absolote value function as vertex of a graph we obtain the graph interpretaion of this optimization problem. The Partially-linear problems are often not only nondifferentiable but nonconvex as well,which makes their solving by standard optimization methods difficult. In this work we give the necessary and sufficient conditions for local optimality. An algorithm for solving such problems, based on the constructive optimization methods is suggested.