Tensor properties of multilevel Toeplitz and related matrices

A general proposal is presented for fast algorithms for multilevel structured matrices. It is based on investigation of their tensor properties and develops the idea recently introduced by Kamm and Nagy in the block Toeplitz case. We show that tensor properties of multilevel Toeplitz matrices are related to separation of variables in the corresponding symbol, present analytical tools to study the latter, expose truncation algorithms preserving the structure, and report on some numerical results confirming advantages of the proposal.     

TT-cross approximation for multidimensional arrays

As is well known, a rank-r matrix can be recovered from a cross of r linearly independent columns and rows, and an arbitrary matrix can be interpolated on the cross entries. Other entries by this cross or pseudo-skeleton approximation are given with errors depending on the closeness of the matrix to a rank-r matrix and as well on the choice of cross. In this paper we extend this construction to d-dimensional arrays (tensors) and suggest a new interpolation formula in which a d-dimensional array is interpolated on the entries of some TT-cross (tensor train-cross). The total number of entries and the complexity of our interpolation algorithm depend on d linearly, so the approach does not suffer from the curse of dimensionality.We also propose a TT-cross method for computation of d-dimensional integrals and apply it to some examples with dimensionality in the range from d=100 up to d=4000 and the relative accuracy of order 10^-10. In all constructions we capitalize on the new tensor decomposition in the form of tensor trains (TT-decomposition).     

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.     

Spline collocation for strongly elliptic equations on the torus

Summary We prove convergence and error estimates in Sobolev spaces for the collocation method with tensor product splines for strongly elliptic pseudodifferential equations on the torus. Examples of applications include elliptic partial differential equations with periodic boundary conditions but also the classical boundary integral operators of potential theory on torus-shaped domains in three or more dimensions. For odd-degree splines, we prove convergence of nodal collocation for any strongly elliptic operator. For even-degree splines and midpoint collocation, we find an additional condition for the convergence which is satisfied for the classical boundary integral operators. Our analysis is a generalization to higher dimensions of the corresponding analysis of Arnold and Wendland [4].     

On the Z-eigenvalues of the adjacency tensors for uniform hypergraphs

The adjacency matrices for graphs are generalized to the adjacency tensors for uniform hypergraphs, and some fundamental properties for the adjacency tensor and its Z-eigenvalues of a uniform hypergraph are obtained. In particular, some bounds on the smallest and the largest Z-eigenvalues of the adjacency tensors for uniform hypergraphs are presented.     

Tensor ranks for the inversion of tensor-product binomials

The main result reads: if a nonsingular matrix A of order n=pq is a tensor-product binomial with two factors then the tensor rank of A⁻¹ is bounded from above by min{p,q}. The estimate is sharp, and in the worst case it amounts to .     

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.     

On nonsingularity of block two-by-two matrices

We derive necessary and sufficient conditions for guaranteeing the nonsingularity of a block two-by-two matrix by making use of the singular value decompositions and the Moore–Penrose pseudoinverses of the matrix blocks. These conditions are complete, and much weaker and simpler than those given by Decker and Keller [D.W. Decker, H.B. Keller, Multiple limit point bifurcation, J. Math. Anal. Appl. 75 (1980) 417–430], and may be more easily examined than those given by Bai [Z.-Z. Bai, Eigenvalue estimates for saddle point matrices of Hermitian and indefinite leading blocks, J. Comput. Appl. Math. 237 (2013) 295–306] from the computational viewpoint. We also derive general formulas for the rank of the block two-by-two matrix by utilizing either the unitarily compressed or the orthogonally projected sub-matrices.     

Jordan structures of alternating matrix polynomials

Alternating matrix polynomials, that is, polynomials whose coefficients alternate between symmetric and skew-symmetric matrices, generalize the notions of even and odd scalar polynomials. We investigate the Smith forms of alternating matrix polynomials, showing that each invariant factor is an even or odd scalar polynomial. Necessary and sufficient conditions are derived for a given Smith form to be that of an alternating matrix polynomial. These conditions allow a characterization of the possible Jordan structures of alternating matrix polynomials, and also lead to necessary and sufficient conditions for the existence of structure-preserving strong linearizations. Most of the results are applicable to singular as well as regular matrix polynomials.     

Direct and inverse spectral problems for a class of non-self-adjoint periodic tridiagonal matrices

The spectral properties of a class of tridiagonal matrices are investigated. The reconstruction of matrices of this special class from given spectral data is also studied. Necessary and sufficient conditions for that reconstruction are found. The obtained results extend some results on the direct and inverse spectral problems for periodic Jacobi matrices and for some non-self-adjoint tridiagonal matrices.     

H-矩阵和S-双对角占优矩阵

In this paper, the concept of the s-doubly diagonally dominant matrices is introduced and the properties of these matrices are discussed. With the properties of the s-doubly diagonally dominant matrices and the properties of comparison matrices, some equivalent conditions for H-matrices are presented. These conditions generalize and improve existing results about the equivalent conditions for H-matrices. Applications and examples using these new equivalent conditions are also presented, and a new inclusion region of k-multiple eigenvalues of matrices is obtained.     

An inverse eigenvalue problem and an associated approximation problem for generalized K-centrohermitian matrices

A partially described inverse eigenvalue problem and an associated optimal approximation problem for generalized K-centrohermitian matrices are considered. It is shown under which conditions the inverse eigenproblem has a solution. An expression of its general solution is given. In case a solution of the inverse eigenproblem exists, the optimal approximation problem can be solved. The formula of its unique solution is given.     

The solution methods for the largest eigenvalue (singular value) of nonnegative tensors and convergence analysis

In this paper we study two solution methods for finding the largest eigenvalue (singular value) of general square (rectangular) nonnegative tensors. For a positive tensor, one can find the largest eigenvalue (singular value) based on the properties of the positive tensor and the power-type method. While for a general nonnegative tensor, we use a series of decreasing positive perturbations of the original tensor and repeatedly recall power-type method for finding the largest eigenvalue (singular value) of a positive tensor with an inexact strategy. We prove the convergence of the method for the general nonnegative tensor. Under a certain assumption, the computing complexity of the method is established. Motivated by the interior-point method for the convex optimization, we put forward a one-step inner iteration power-type method, whose convergence is also established under certain assumption. Additionally, by using embedding technique, we show the relationship between the singular values of the rectangular tensor and the eigenvalues of related square tensor, which suggests another way for finding the largest singular value of nonnegative rectangular tensor besides direct power-type method for this problem. Finally, numerical examples of our algorithms are reported, which demonstrate the convergence behaviors of our methods and show that the algorithms presented are promising.     

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.     

Algorithmic copositivity detection by simplicial partition

We present new criteria for copositivity of a matrix, i.e., conditions which ensure that the quadratic form induced by the matrix is nonnegative over the nonnegative orthant. These criteria arise from the representation of the quadratic form in barycentric coordinates with respect to the standard simplex and simplicial partitions thereof. We show that, as the partition gets finer and finer, the conditions eventually capture all strictly copositive matrices. We propose an algorithmic implementation which considers several numerical aspects. As an application, we present results on the maximum clique problem. We also briefly discuss extensions of our approach to copositivity with respect to arbitrary polyhedral cones.     

On some iterations for optimal control of jump linear equations

We consider different iterative methods for computing Hermitian solutions of the coupled Riccati equations of the optimal control problem for jump linear systems. We have constructed a sequence of perturbed Lyapunov algebraic equations whose solutions define matrix sequences with special properties proved under proper initial conditions. Several numerical examples are included to illustrate the effectiveness of the considered iterations.     

Efficient numerical solution of the generalized Dirichlet-Neumann map for linear elliptic PDEs in regular polygon domains

A new and novel approach for analyzing boundary value problems for linear and for integrable nonlinear PDEs was recently introduced. For linear elliptic PDEs, an important aspect of this approach is the characterization of a generalized Dirichlet-Neumann map: given the derivative of the solution along a direction of an arbitrary angle to the boundary, the derivative of the solution perpendicularly to this direction is computed without solving on the interior of the domain. For this computation, a collocation-type numerical method has been recently developed. Here, we study the collocation’s coefficient matrix properties. We prove that, for the Laplace’s equation on regular polygon domains with the same type of boundary conditions on each side, the collocation matrix is block circulant, independently of the choice of basis functions. This leads to the deployment of the FFT for the solution of the associated collocation linear system, yielding significant computational savings. Numerical experiments are included to demonstrate the efficiency of the whole computation.     

Derivatives for antisymmetric tensor powers and perturbation bounds

In an earlier paper (R. Bhatia, T. Jain, Higher order derivatives and perturbation bounds for determinants, Linear Algebra Appl. 431 (2009) 2102-2108) we gave formulas for derivatives of all orders for the map that takes a matrix to its determinant. In this paper we continue that work, and find expressions for the derivatives of all orders for the antisymmetric tensor powers and for the coefficients of the characteristic polynomial. We then evaluate norms of these derivatives, and use them to obtain perturbation bounds.     

Drazin inverse of partitioned matrices in terms of Banachiewicz-Schur forms

Let be a partitioned matrix, where A and D are square matrices. Denote the Drazin inverse of A by A^D. The purpose of this paper is twofold. Firstly, we develop conditions under which the Drazin inverse of M having generalized Schur complement, S=D-CA^DB, group invertible, can be expressed in terms of a matrix in the Banachiewicz-Schur form and its powers. Secondly, we deal with partitioned matrices satisfying rank(M)=rank(A^D)+rank(S^D), and give conditions under which the group inverse of M exists and a formula for its computation.     

Rank one preservers between spaces of Boolean matrices

In this paper, we characterize (i) linear transformations from one space of Boolean matrices to another that send pairs of distinct rank one elements to pairs of distinct rank one elements and (ii) surjective mappings from one space of Boolean matrices to another that send rank one matrices to rank one matrices and preserve order relation in both directions. Both results are proved in a more general setting of tensor products of two Boolean vector spaces of arbitrary dimension.