Erna Begovic

Vjeran Hari, Erna Begovic

The paper studies the global convergence of the block Jacobi me\-thod for symmetric matrices. Given a symmetric matrix $A$ of order $n$, the method generates a sequence of matrices by the rule $A^{(k+1)}=U_k^TA^{(k)}U_k$, $k\geq0$, where $U_k$ are orthogonal elementary block matrices. A class of generalized serial pivot strategies is introduced, significantly enlarging the known class of weak wavefront strategies, and appropriate global convergence proofs are obtained. The results are phrased in the stronger form: $S(A')\leq c S(A)$, where $A'$ is the matrix obtained from $A$ after one full cycle, $c<1$ is a constant and $S(A)$ is the off-norm of $A$. Hence, using the theory of block Jacobi operators, one can apply the obtained results to prove convergence of block Jacobi methods for other eigenvalue problems, such as the generalized eigenvalue problem. As an example, the results are applied to the block $J$-Jacobi method. Finally, all results are extended to the corresponding quasi-cyclic strategies.

Vjeran Hari, Erna Begovic

In this paper we prove the global convergence of the complex Jacobi method for Hermitian matrices for a large class of generalized serial pivot strategies. For a given Hermitian matrix $A$ of order $n$ we find a constant $γ<1$ depending on $n$, such that $S(A')\leqγ{S(A)}$, where $A'$ is obtained from $A$ by applying one or more cycles of the Jacobi method and $S(\cdot)$ stands for the off-norm. Using the theory of complex Jacobi operators, the result is generalized so it can be used for proving convergence of more general Jacobi-type processes. In particular, we use it to prove the global convergence of Cholesky-Jacobi method for solving the positive definite generalized eigenvalue problem.

Erna Begovic, Vjeran Hari

The paper analyzes special cyclic Jacobi methods for symmetric matrices of order $4$. Only those cyclic pivot strategies that enable full parallelization of the method are considered. These strategies, unlike the serial pivot strategies, can force the method to be very slow or very fast within one cycle, depending on the underlying matrix. Hence, for the global convergence proof one has to consider two or three adjacent cycles. It is proved that for any symmetric matrix $A$ of order~$4$ the inequality $S(A^{[2]})\leq(1-10^{-5})S(A)$ holds, where $A^{[2]}$ results from $A$ by applying two cycles of a particular parallel method. Here $S(A)$ stands for the Frobenius norm of the strictly upper-triangular part of $A$. The result holds for two special parallel strategies and implies the global convergence of the method under all possible fully parallel strategies. It is also proved that for every $ε>0$ and $n\geq4$ there exist a symmetric matrix $A(ε)$ of order $n$ and a cyclic strategy, such that upon completion of the first cycle of the appropriate Jacobi method the inequality $S(A^{[1]})> (1-ε)S(A(ε))$ holds.

Erna Begovic, Anita Carevic, Ivana Sain Glibic

Coupled decompositions are a widely used tool for data fusion. As the volume of data increases, so does the dimensionality of matrices and tensors, highlighting the need for more efficient coupled decomposition algorithms. This paper studies the problem of coupled matrix factorization (CMF), where two matrices represented in low-rank form share a common factor. Additionally, it explores coupled matrix and tensor factorization (CMTF), where a matrix and a tensor are represented in low-rank form, also sharing a common factor matrix. We show that these problems can be solved using a direct approach with singular value decomposition (SVD), rather than relying on an iterative method. Knowing that matrices coming from real-world applications are often very large, the computational cost can be substantial. To address this issue and improve the efficiency, we propose new techniques for randomizing these algorithms. This includes a novel strategy for selecting a projection subspace that takes into account the contribution from both matrices involved in the decomposition equally. We present extensive results of numerical tests that confirm the efficiency of our algorithms. Furthermore, as a novel approach and with a high success rate, we apply our randomized algorithms to the face recognition problem.

Erna Begovic, Vjeran Hari

The paper studies the global convergence of the Jacobi method for symmetric matrices of size $4$. We prove global convergence for all $720$ cyclic pivot strategies. Precisely, we show that inequality $S(A^{[t+3]})\leqγS(A^{[t]})$, $t\geq1$, holds with the constant $γ<1$ that depends neither on the matrix $A$ nor on the pivot strategy. Here $A^{[t]}$ stands for the matrix obtained from $A$ after $t$ full cycles of the Jacobi method and $S(A)$ is the off-diagonal norm of $A$. We show why three consecutive cycles have to be considered. The result has a direct application on the $J$-Jacobi method.

Erna Begovic, Daniel Kressner

This paper is concerned with low multilinear rank approximations to antisymmetric tensors, that is, multivariate arrays for which the entries change sign when permuting pairs of indices. We show which ranks can be attained by an antisymmetric tensor and discuss the adaption of existing approximation algorithms to preserve antisymmetry, most notably a Jacobi algorithm. Particular attention is paid to the important special case when choosing the rank equal to the order of the tensor. It is shown that this case can be addressed with an unstructured rank-$1$ approximation. This allows for the straightforward application of the higher-order power method, for which we discuss effective initialization strategies.