Open AccessMethods for Updating the Singular Value Decomposition
Author(s) -
Linda Kaufman
Publication year - 1974
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v3i26.6445
Subject(s) - singular value decomposition , singular value , decomposition , mathematics , matrix (chemical analysis) , column (typography) , value (mathematics) , matrix decomposition , combinatorics , discrete mathematics , algorithm , eigenvalues and eigenvectors , physics , geometry , statistics , chemistry , organic chemistry , quantum mechanics , chromatography , connection (principal bundle)
The linear least squares problem of minimizing ||Ax~ - b~||_(2) where A is an m X n matrix, m >= n, may be solved using the singular value decomposition in approximately 2mn^(3) + 4n^(3) multiplications. In this paper the problem of solving ||A'x~ - b~||_(2) is considered where A' results from deleting or adding a column to A. This might occur when a change is made in the model of a process. Instead of computing the singular value decomposition of A' from scratch, the singular value decomposition of A is updated. Since the updating require about 6n^(3) multiplications the algorithms are useful when m >> n. The problem of recalculation some or all of the singular values of a matrix A', which is obtained by deleting or adding a row or a column from a matrix A, whose singular value decomposition is known, is also studied.