Subspace Computations via Matrix Decompositions and Geometric Optimization
2006 (English)Doctoral thesis, monograph (Other academic)
This thesis is concerned with the computation of certain subspaces connected to a given matrix, where the closely related problem of approximating the matrix with one of lower rank is given special attention.
To determine the rank and obtain bases for fundamental subspaces such as the range and null space of a matrix, computing the singular value decomposition (SVD) is the standard method. When new data are added, like in adaptive signal processing, a more economic alternative to the SVD is to use a rank-revealing UTV (ULV or URV) decomposition since it can be updated more easily.
The scenario in part I of the thesis is that the matrix to be updated is either a product or a quotient of two other matrices. There exist implicit algorithms for computing the SVD of a product or quotient that operate on the two matrices separately. For the corresponding problem of an URV decomposition of a product or quotient, originally sketched by S. Qiao, we give the details of the updating algorithms. Sample numerical experiments confirm that the quality of the approximate subspaces compared to the ones obtained by the implicitly computed URV, is degraded if the product is formed explicitly in some cases. We argue that the same pros and cons that affect the choice between the URV and ULV decomposition of one matrix, carry over to the choice between the implicit URV decomposition and the more established ULLV decomposition in the quotient case. As a signal processing application, we track the range of an estimated cross-covariance matrix.
We also describe the updating issues of a decomposition that reveals the ranks of the individual matrices in a product. That decomposition suffers from a difficult decision about the rank of the product and will not be tested as a competitor to the implicit URV decomposition referred to above.
A common situation in scientific computing is that the matrix is too lagre to admit a full factorization within reasonable time. In that case iterative methods must be employed, where Lanczos type algorithms are the most widely used. In part II we discuss the formulation of standard numerical optimization methods on the Grassmann manifold whose objects are subspaces and focus on the application to numerical linear algebra problems. This approach allow us to (re-)derive algorithms for the partial symmetric eigenvalue problem and the inexact Newton method is given special attention.
A recent method is the Jacobi-Davidson (JD) algorithm that can be seen both as a variation of an inexact Newton method for solving a set of nonlinear equations/minimizing a function and as an expanding subspace algorithm that is equivalent to Lanczos if the equation in each step is solved exactly. Our contribution is an algorithm that is fairly robust with a subspace that is only twice as large as the desired one. A large part treats the implementation issues associated with the solution of a correction equation including stopping rules and the use of preconditioners.
Other numerical linear algebra problems call for a pair of subspaces. We give Grassmann type algorithms for the partial SVD problem and low rank approximation of matrices with missing entries, but will restrain ourselves by demonstrating their efficiency for exact solution of the Newton equation.
Place, publisher, year, edition, pages
Matematiska institutionen , 2006. , 183 p.
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1052
Mathematics, Numerical Analysis, Rank-revealing UTV, Jacobi-Davidson algorithm, Decomposition, Grassmann type algorithms
IdentifiersURN: urn:nbn:se:liu:diva-8235ISBN: 91-85643-63-7OAI: oai:DiVA.org:liu-8235DiVA: diva2:23076
2006-12-21, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Ruhe, Axel, Professor