The paper is concerned with methods for computing the best low multilinear rank approximation of large and sparse tensors. Krylov-type methods have been used for this problem; here block versions are introduced. For the computation of partial eigenvalue and singular value decompositions of matrices the Krylov-Schur (restarted Arnoldi) method is used. A generalization of this method to tensors is described, for computing the best low multilinear rank approximation of large and sparse tensors. In analogy to the matrix case, the large tensor is only accessed in multiplications between the tensor and blocks of vectors, thus avoiding excessive memory usage. It is proved that if the starting approximation is good enough, then the tensor Krylov-Schur method is convergent. Numerical examples are given for synthetic tensors and sparse tensors from applications, which demonstrate that for most large problems the Krylov-Schur method converges faster and more robustly than higher order orthogonal iteration.

The problem of partitioning a large and sparse tensor is considered, where the tensor consists of a sequence of adjacency matrices. Theory is developed that is a generalization of spectral graph partitioning. A best rank-(2,2,lambda) approximation is computed for lambda=1,2,3, and the partitioning is computed from the orthogonal matrices and the core tensor of the approximation. It is shown that if the tensor has a certain reducibility structure, then the solution of the best approximation problem exhibits the reducibility structure of the tensor. Further, if the tensor is close to being reducible, then still the solution of the exhibits the structure of the tensor. Numerical examples with synthetic data corroborate the theoretical results. Experiments with tensors from applications show that the method can be used to extract relevant information from large, sparse, and noisy data.

Axel Ruhe passed away April 4, 2015. He was cross-country-skiing with friends in the Swedish mountains when after 21 km he suddenly died. He is survived by his wife Gunlaug and three children from his first marriage....

Partial least squares is a common technique for multivariate regression. The pro- cedure is recursive and in each step basis vectors are computed for the explaining variables and the solution vectors. A linear model is fitted by projection onto the span of the basis vectors. The procedure is mathematically equivalent to Golub-Kahan bidiagonalization, which is a Krylov method, and which is equiv- alent to a pair of matrix factorizations. The vectors of regression coefficients and prediction are non-linear functions of the right hand side. An algorithm for computing the Frechet derivatives of these functions is derived, based on perturbation theory for the matrix factorizations. From the Frechet derivative of the prediction vector one can compute the number of degrees of freedom, which can be used as a stopping criterion for the recursion. A few numerical examples are given.

n/a

In this paper, we propose a method to find the best Kronecker product approximationof the blurring operator which arises in three dimensional image restoration problems. We show thatthis problem can be reduced to a well known rank-1 approximation of the scaled three dimensionalpoint spread function (PSF) array, which is much smaller. This approximation can be used as apreconditioner in solving image restoration problems with iterative methods. The comparison ofthe approximation by the new scaled PSF array and approximation by the original PSF array that is used in [J. G. Nagy and M. E. Kilmer, IEEE Trans. Image Process., 15 (2006), pp. 604–613],confirms the performance of the new proposed approximation.

An ill-posed Cauchy problem for a 3D elliptic partial differential equation with variable coefficients is considered. A well-posed quasi-boundary-value (QBV) problem is given to approximate it. Some stability estimates are given. For the numerical implementation, a large sparse system is obtained from discretizing the QBV problem using the finite difference method. A left-preconditioned generalized minimum residual method is used to solve the large system effectively. For the preconditioned system, a fast solver using the fast Fourier transform is given. Numerical results show that the method works well.

The sideways parabolic equation (SPE) is a model of the problem of determiningthe temperature on the surface of a body from the interior measurements. Mathematically it can beformulated as a noncharacteristic Cauchy problem for a parabolic partial differential equation. Thisproblem is severely ill-posed in an L2 setting. We use a preconditioned generalized minimum residualmethod (GMRES) to solve a two-dimensional SPE with variable coefficients. The preconditioner issingular and chosen in a way that allows efficient implementation using the FFT. The preconditioneris a stabilized solver for a nearby problem with constant coefficients, and it reduces the numberof iterations in the GMRES algorithm significantly. Numerical experiments are performed thatdemonstrate the performance of the proposed method.

Using the technique of semantic mirroring a graph is obtained that represents words and their translationsfrom a parallel corpus or a bilingual lexicon. The connectedness of the graph holds information about the semanticrelations of words that occur in the translations. Spectral graph theory is used to partition the graph, which leadsto a grouping of the words in different clusters. We illustrate the method using a small sample of seed words froma lexicon of Swedish and English adjectives and discuss its application to computational lexical semantics andlexicography.

Several Krylov-type procedures are introduced that generalize matrix Krylov methods for tensor computations. They are denoted minimal Krylov recursion, maximal Krylov recursion, and contracted tensor product Krylov recursion. It is proved that, for a given tensor A with multilinear rank-(p; q; r), the minimal Krylov recursion extracts the correct subspaces associated to the tensor in p+q+r number of tensor-vector-vector multiplications. An optimized minimal Krylov procedure is described that, for a given multilinear rank of an approximation, produces a better approximation than the standard minimal recursion. We further generalize the matrix Krylov decomposition to a tensor Krylov decomposition. The tensor Krylov methods are intended for the computation of low multilinear rank approximations of large and sparse tensors, but they are also useful for certain dense and structured tensors for computing their higher order singular value decompositions or obtaining starting points for the best low-rank computations of tensors. A set of numerical experiments, using real-world and synthetic data sets, illustrate some of the properties of the tensor Krylov methods.