Rank-\(k\) modification methods for recursive least squares problems
type: Item
instance of: scholarly article
title: Rank-\(k\) modification methods for recursive least squares problems
zbMATH Open document ID: 0813.65079
DOI: 10.1007/BF02140689
author: Serge J. Olszanskyj
author: James M. Lebak
author: Adam W. Bojanczyk
published in: Numerical Algorithms
publication date: 1994-10-17T00:00:00Z
review text: A linear least squares problem based on the QR factorization is referred to as the recursive least squares problem if it is desired to solve the same problem with one or more rows added or deleted from the data. The authors introduce the concept of rank-\(k\) modifications for recursive least squares problems, with the emphasis on developing numerically accurate rank-\(k\) downdating algorithms because downdating is numerically harder than updating. They extend known rank-1 downdating algorithms, such as corrected seminormal equations (CSNE), the LINPACK method, and downdating via classical Gram-Schmidt (CGS) with re-orthogonalization and develop some new rank-\(k\) downdating algorithms, e.g. based on modified-Gram-Schmidt (MGS) and block-Gram-Schmidt (BGS). They provide experimental results comparing the numerical accuracy of the various algorithms and other computational aspects of the algorithms. On the basis of the computer experiments, they are able to state, that a single rank-\(k\) downdate for the various methods is faster than \(k\) consecutive rank-1 downdates and the Gram-Schmidt methods are faster methods but not numerically accurate for ill-conditioned problems.
Mathematics Subject Classification ID: 65F20
Mathematics Subject Classification ID: 65F25
zbMATH DE Number: 640748
zbMATH Keywords: rank-\(k\) modifications
zbMATH Keywords: QR factorization
zbMATH Keywords: recursive least squares problem
zbMATH Keywords: downdating algorithms
zbMATH Keywords: corrected seminormal equations
zbMATH Keywords: LINPACK method
zbMATH Keywords: experimental results
zbMATH Keywords: Gram-Schmidt methods
zbMATH Keywords: ill-conditioned problems
reviewed by: Otu Vaarmann
describes a project that uses: LINPACK
MaRDI profile type: Publication
cites work: Analysis of a recursive least squares hyperbolic rotation algorithm for signal processing
cites work: Stability analysis of the method of seminormal equations for linear least squares problems
cites work: Loss and Recapture of Orthogonality in the Modified Gram–Schmidt Algorithm
cites work: Solving linear least squares problems by Gram-Schmidt orthogonalization
cites work: Q3974749
cites work: Numerics of Gram-Schmidt orthogonalization
cites work: Stabilized hyperbolic Householder transformations
cites work: Reorthogonalization and Stable Algorithms for Updating the Gram-Schmidt QR Factorization
cites work: Methods for Modifying Matrix Factorizations
cites work: Q3359644
cites work: Q4000104
cites work: Stability Analysis and Improvement of the Block Gram–Schmidt Algorithm
cites work: Iterative refinement implies numerical stability
cites work: Least squares modifications with inverse factorizations: Parallel implications
cites work: Q3868672
cites work: Hyperbolic householder transformations
cites work: The Effects of Rounding Error on an Algorithm for Downdating a Cholesky Factorization
Recommended article: Efficient recursive least squares solver for rank-deficient matrices
Recommended article: Efficient Solution Of The Rank-Deficient Linear Least Squares Problem
Recommended article: On least squares solutions subject to a rank restriction
Recommended article: Accurate solution of structured least squares problems via rank-revealing decompositions
Recommended article: Least squares methods in Krylov subspaces
Recommended article: Krylov Methods for Low-Rank Regularization
Recommended article: Approximating minimum norm solutions of rank-deficient least squares problems
Recommended article: On an iterative method for solving the least squares problem of rank-deficient systems
Recommended article: Q4503855
description: scientific article; zbMATH DE number 640748