Search

In this paper we develop a novel clustered matrix approximation framework, first showing the motivation behind our research. The proposed methods are particularly well suited for problems with large scale sparse matrices that represent graphs and/or bipartite graphs from information science applications. Our framework and resulting approximations have a number of benefits: (1) the approximations preserve important structure that is present in the original matrix; (2) the approximations contain both global-scale and local-scale information; (3) the procedure is eficient both in computational speed and memory usage; and (4) the resulting approximations are considerably more accurate with less memory usage than truncated SVD approximations, which are optimal with respect to rank. The framework is also quite exible as it may be modified in various ways to fit the needs of a particular application. In the paper we also derive a probabilistic approach that uses randomness to compute a clustered matrix approximation within the developed framework. We further prove deterministic and probabilistic bounds of the resulting approximation error. Finally, in a series of experiments we evaluate, analyze, and discuss various aspects of the proposed framework. In particular, all the benefits we claim for the clustered matrix approximation are clearly illustrated using real-world and large scale data. [ABSTRACT FROM AUTHOR]

An important step in the solution of a matrix nearness problem that arises in certain machine learning applications is finding the zero of f(α) = zT exp(logX + αzzT )z - b. The matrix valued exponential and logarithm in f(α) arises from the use of the von Neumann matrix divergence tr(X logX - X log Y - X + Y ) to measure the nearness between the positive definite matrices X and Y . A key step of an iterative algorithm used to solve the underlying matrix nearness problem requires the zero of f(α) to be repeatedly computed. In this paper we propose zero-finding algorithms that gain their advantage by exploiting the special structure of the objective function. We show how to efficiently compute the derivative of f, thereby allowing the use of Newton-type methods. In numerical experiments we establish the advantage of our algorithms. [ABSTRACT FROM AUTHOR]

This paper discusses a new class of matrix nearness problems that measure approximation error using a directed distance measure called a Bregman divergence. Bregman divergences offer an important generalization of the squared Frobenius norm and relative entropy, and they all share fundamental geometric properties. In addition, these divergences are intimately connected with exponential families of probability distributions. Therefore, it is natural to study matrix approximation problems with respect to Bregman divergences. This article proposes a framework for studying these problems, discusses some specific matrix nearness problems, and provides algorithms for solving them numerically. These algorithms apply to many classical and novel problems, and they admit a striking geometric interpretation. [ABSTRACT FROM AUTHOR]

In this paper, we present new algorithms that can replace the diagonal entries of a Hermitian matrix by any set of diagonal entries that majorize the original set without altering the eigenvalues of the matrix. They perform this feat by applying a sequence of (N-1) or fewer plane rotations, where N is the dimension of the matrix. Both the Bendel--Mickey and the Chan--Li algorithms are special cases of the proposed procedures. Using the fact that a positive semidefinite matrix can always be factored as $\mtx{X^\adj X}$, we also provide more efficient versions of the algorithms that can directly construct factors with specified singular values and column norms. We conclude with some open problems related to the construction of Hermitian matrices with joint diagonal and spectral properties. [ABSTRACT FROM AUTHOR]

This paper presents and analyzes a new algorithm for computing eigenvectors of symmetric tridiagonal matrices factored as LDLt, with D diagonal and L unit bidiagonal. If an eigenpair is well behaved in a certain sense with respect to the factorization, the algorithm is shown to compute an approximate eigenvector which is accurate to working precision. As a consequence, all the eigenvectors computed by the algorithm come out numerically orthogonal to each other without making use of any reorthogonalization process. The key is .first running a qd-type algorithm on the factored matrix LDLt and then applying a .fine-tuned version of inverse iteration especially adapted to this situation. Since the computational cost is O(n) per eigenvector for an n × n matrix, the proposed algorithm is the central step of a more ambitious algorithm which, at best (i.e., when all eigenvectors are well-conditioned), would compute all eigenvectors of an n × n symmetric tridiagonal at O(n2) cost, a great improvement over existing algorithms. [ABSTRACT FROM AUTHOR]