Search

This paper provides an advanced mathematical theory of the generalized singular value decomposition (GSVD) and its applications. We explore the geometry of the GSVD providing a long-sought-for picture which includes a horizontal and a vertical multiaxis. We further propose that the GSVD provides natural coordinates for the Grassmann manifold. This paper proves a theorem showing how the finite generalized singular values do or do not relate to the singular values of AB†. We then turn to applications, arguing that this geometrical theory is natural for understanding existing applications and recognizing opportunities for new applications. In particular the generalized singular vectors play a direct and as natural a mathematical role for certain applications as the singular vectors do for the SVD. In the same way that experts on the SVD often prefer not to cast SVD problems as eigenproblems, we propose that the GSVD, often cast as a generalized eigenproblem, is perhaps best cast in its natural setting. We illustrate this theoretical approach and the natural multiaxes (with labels from technical domains) in the context of applications where the GSVD arises: Tikhonov regularization (unregularized versus regularized), genome reconstruction (humans versus yeast), signal processing (signal versus noise), and statistical analysis such as analysis of variance and discriminant analysis (between clusters versus within clusters.) With the aid of our ellipse figure, we encourage the labeling of the natural multiaxes in any GSVD problem. [ABSTRACT FROM AUTHOR]

Oblique projection matrices arise in problems in weighted least squares, signal processing, and optimization. While these matrices can be potentially very large, their low-rank structure can be exploited for efficient computation. We propose fast and scalable algorithms for computing their eigendecomposition and singular value decomposition (SVD). Numerical experiments that compare our proposed approaches to existing methods, including randomized SVD, are presented. In addition, we test their accuracy on linear systems from equality constrained optimization problems. [ABSTRACT FROM AUTHOR]

In this paper we propose an approach to approximate a truncated singular value decomposition of a large structured matrix. By first decomposing the matrix into a sum of Kronecker products, our approach can be used to approximate a large number of singular values and vectors more efficiently than other well-known schemes, such as iterative algorithms based on Golub--Kahan-- Lanczos bidiagonalization. We provide theoretical results and numerical experiments to demonstrate the accuracy of our approximation and show how the approximation can be used to solve large scale ill-posed inverse problems, either as an approximate filtering method, or as a preconditioner to accelerate iterative algorithms. [ABSTRACT FROM AUTHOR]

A new generalized matrix inverse is derived which is consistent with respect to arbitrary nonsingular diagonal transformations, e.g., it preserves units associated with variables under state space transformations, thus providing a general solution to a longstanding open problem relevant to a wide variety of applications in robotics, tracking, and control systems. The new inverse complements the Drazin inverse (which is consistent with respect to similarity transformations) and the Moore--Penrose inverse (which is consistent with respect to unitary/orthogonal transformations) to complete a trilogy of generalized matrix inverses that exhausts the standard family of analytically important linear system transformations. Results are generalized to obtain unit-consistent and unitinvariant matrix decompositions, and examples of their use are described. [ABSTRACT FROM AUTHOR]

In this paper, we discuss the following two minimum rank matrix approximation problems in the spectral norm: minx rank(X), subject to ||A - BXC||2 = θ, where θ … minY ||A - BY C||2; minX rank(X), subject to ||A - BXC||2 < ξ, where ξ > θ. We solve the first problem by applying the norm-preserving dilation theorem and the restricted singular value decomposition (R-SVD) to characterize three expressions of the minimum rank, and we derive general forms of minimum rank solutions. We also characterize the expressions of the minimum rank of the second problem, which is a generalization known results in the literature. [ABSTRACT FROM AUTHOR]

In this paper, we propose a robust Cholesky factorization method for symmetric positive definite (SPD), hierarchically semiseparable (HSS) matrices. Classical Cholesky factorizations and some semiseparable methods need to sequentially compute Schur complements. In contrast, we develop a strategy involving orthogonal transformations and approximations which avoids the explicit computation of the Schur complement in each factorization step. The overall factorization requires fewer floating point operations and has better data locality when compared to the recent HSS method in [J. Xia and M. Gu, SIAM J. Matrix Anal. Appl., 31 (2010), pp. 2899-2920]. Our strategy utilizes a robustness technique so that an approximate generalized Cholesky factorization is guaranteed to exist. We test three different methods for compressing the off-diagonal blocks in each iteration, i.e., rank-revealing QR, SVD, and SVD with random sampling. In our comparisons, we find that, with high probability, using SVD with random sampling is fast and stable. The complexity of the methods proposed in this paper is analyzed and shown to be O(N²k), where N is the dimension of matrix and k is the maximum off-diagonal (numerical) rank. Numerical results from applications show the efficiency of our method and its effectiveness as a preconditioner. Moreover, our techniques are helpful in improving the scalability and robustness of other rank-structured methods. [ABSTRACT FROM AUTHOR]

We define the hierarchical singular value decomposition (SVD) for tensors of order d ≥ 2. This hierarchical SVD has properties like the matrix SVD (and collapses to the SVD in d = 2), and we prove these. In particular, one can find low rank (almost) best approximations in a hierarchical format (H-Tucker) which requires only O((d − 1)k3 + dnk) parameters, where d is the order of the tensor, n the size of the modes, and k the (hierarchical) rank. The H-Tucker format is a specialization of the Tucker format and it contains as a special case all (canonical) rank k tensors. Based on this new concept of a hierarchical SVD we present algorithms for hierarchical tensor calculations allowing for a rigorous error analysis. The complexity of the truncation (finding lower rank approximations to hierarchical rank k tensors) is in O((d−1)k4+dnk2) and the attainable accuracy is just 2–3 digits less than machine precision. [ABSTRACT FROM AUTHOR]

Numerically stable methods for the computations required in the expectationmaximization (EM) algorithm for maximum-likelihood structured covariance estimation are presented. It is shown that the basic computational task at each iteration is the calculation of a pseudoinverse of a certain linear system of equations. In the no-noise case this is a hard-decision, or Moore-Penrose, pseudoinverse, whereas in the additive noise case it is a soft-decision pseudoinverse. An approach to computing the soft-decision pseudoinverse, which can handle all combinations of dimension and rank in this system of equations, based on the singular value decomposition (SVD), is proposed. An alternative method based on the LQ factorization, which is applicable in certain circumstances, is also proposed. The intermediate calculations required in the EM algorithm can be used to calculate the log-likelihood and the gradient of the log-likelihood. [ABSTRACT FROM AUTHOR]

We present a numerical method for computing the SVD-like decomposition B = QDS-1, where Q is orthogonal, S is symplectic, and D is a permuted diagonal matrix. The method can be applied directly to compute the canonical form of the Hamiltonian matrices of the form JBTB, where $J=[{0 \atop -I}{I \atop 0}]$. It can also be applied to solve the related application problems such as the gyroscopic systems and linear Hamiltonian systems. Error analysis and numerical examples show that the eigenvalues of JBTB computed by this method are more accurate than those computed by the methods working on the explicit product JBTB or BJBT. [ABSTRACT FROM AUTHOR]

Treating matrices as points in n2-dimensional space, we apply geometry to study and explain algorithms for the numerical determination of the Jordan structure of a matrix. Traditional notions such as sensitivity of subspaces are replaced with angles between tangent spaces of manifolds in n2-dimensional space. We show that the subspace sensitivity is associated with a small angle between complementary subspaces of a tangent space on a manifold in n2-dimensional space. We further show that staircase algorithm failure is related to a small angle between what we call staircase invariant space and this tangent space. The matrix notions in n2-dimensional space are generalized to pencils in 2mn-dimensional space. We apply our theory to special examples studied by Boley, Demmel, and Kågström. [ABSTRACT FROM AUTHOR]