liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Simonsson, Lennart
Publications (4 of 4) Show all publications
Simonsson, L. & Elden, L. (2010). Grassmann algorithms for low rank approximation of matrices with missing values. BIT NUMERICAL MATHEMATICS, 50(1), 173-191
Open this publication in new window or tab >>Grassmann algorithms for low rank approximation of matrices with missing values
2010 (English)In: BIT NUMERICAL MATHEMATICS, ISSN 0006-3835, Vol. 50, no 1, p. 173-191Article in journal (Refereed) Published
Abstract [en]

The problem of approximating a matrix by another matrix of lower rank, when a modest portion of its elements are missing, is considered. The solution is obtained using Newtons algorithm to find a zero of a vector field on a product manifold. As a preliminary the algorithm is formulated for the well-known case with no missing elements where also a rederivation of the correction equation in a block Jacobi-Davidson method is included. Numerical examples show that the Newton algorithm grows more efficient than an alternating least squares procedure as the amount of missing values increases.

Keywords
Grassmann manifold, Matrix, Low rank approximation, Newtons method, Singular value decomposition, Least squares, Missing values
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-54404 (URN)10.1007/s10543-010-0253-9 (DOI)000274956300010 ()
Note
The final publication is available at www.springerlink.com: Lennart Simonsson and Lars Elden, Grassmann algorithms for low rank approximation of matrices with missing values, 2010, BIT NUMERICAL MATHEMATICS, (50), 1, 173-191. http://dx.doi.org/10.1007/s10543-010-0253-9 Copyright: Springer Science Business Media http://www.springerlink.com/ Available from: 2010-03-12 Created: 2010-03-12 Last updated: 2013-08-30
Simonsson, L. (2006). Subspace Computations via Matrix Decompositions and Geometric Optimization. (Doctoral dissertation). : Matematiska institutionen
Open this publication in new window or tab >>Subspace Computations via Matrix Decompositions and Geometric Optimization
2006 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

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. p. 183
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1052
Series
Keywords
Mathematics, Numerical Analysis, Rank-revealing UTV, Jacobi-Davidson algorithm, Decomposition, Grassmann type algorithms
National Category
Computational Mathematics
Identifiers
urn:nbn:se:liu:diva-8235 (URN)91-85643-63-7 (ISBN)
Public defence
2006-12-21, Glashuset, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Available from: 2007-02-01 Created: 2007-02-01 Last updated: 2009-06-04
Simonsson, L. (2004). Lågrang-approximation av en matris med saknade element. In: Workshop i tillämpad matematik,2004.
Open this publication in new window or tab >>Lågrang-approximation av en matris med saknade element
2004 (Swedish)In: Workshop i tillämpad matematik,2004, 2004Conference paper, Published paper (Other academic)
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-23231 (URN)2644 (Local ID)2644 (Archive number)2644 (OAI)
Available from: 2009-10-07 Created: 2009-10-07
Simonsson, L. (2003). Computing a Partial SVD of a Matrix with Missing Data. In: Numerical Linear Algebra and its Applications: XXI International School and Workshop,2003.
Open this publication in new window or tab >>Computing a Partial SVD of a Matrix with Missing Data
2003 (English)In: Numerical Linear Algebra and its Applications: XXI International School and Workshop,2003, 2003Conference paper, Published paper (Other academic)
National Category
Mathematics
Identifiers
urn:nbn:se:liu:diva-22310 (URN)1503 (Local ID)1503 (Archive number)1503 (OAI)
Available from: 2009-10-07 Created: 2009-10-07
Organisations

Search in DiVA

Show all publications