Block RLS using row Householder reflections. (English) Zbl 0781.65032
The authors introduce new row Householder and row hyperbolic Householder reflections to zero a contiguous sequence of entries in a row of a matrix when applied from the left. These reflections are used to develop efficient algorithms for recursive least squares (RLS) problems of the sliding window type. These algorithms are based upon rank-\(k\) modification to the inverse Cholesky factor \(R^{-1}\) of the covariance matrix.
Numerical experiments show that these algorithms are rich in matrix- matrix BLAS-3 computations, making them even more economical on high performance architectures than \(k\) applications of rank-1 modification schemes.
Numerical experiments show that these algorithms are rich in matrix- matrix BLAS-3 computations, making them even more economical on high performance architectures than \(k\) applications of rank-1 modification schemes.
Reviewer: P.Narain (Bombay)
MSC:
| 65F30 | Other matrix algorithms (MSC2010) |
| 65Y20 | Complexity and performance of numerical algorithms |
Keywords:
Cholesky factorization; recursive least squares problems; row hyperbolic Householder reflections; algorithms; Numerical experiments; matrix-matrix BLAS-3 computations; performanceSoftware:
LAPACKReferences:
| [1] | Anderson, E.; Bai, Z.; Bischof, C.; Demmel, J.; Dongarra, J.; Du Croz, J.; Greenbaum, A.; Hammarling, S.; McKenney, A.; Ostrouchov, S.; Sorensen, D., LAPACK Users’ Guide, Release 1.0 (1992), SIAM Press: SIAM Press Philadelphia · Zbl 0843.65018 |
| [2] | Alexander, S. T.; Pan, C.-T.; Plemmons, R. J., Analysis of a recursive least squares hyperbolic rotation algorithm for signal processing, Linear Algebra Appl., 98, 3-40 (1988) · Zbl 0639.94004 |
| [3] | Bartels, R.; Kaufman, L., Cholesky factor updating techniques for rank 2 matrix modifications, SIAM J. Matrix. Anal. Appl., 10, 557-592 (1989) · Zbl 0682.65013 |
| [4] | Björck, Å., Least squares methods, (Ciarlet, P.; Lions, J., Handbook of Numerical Methods, Vol. 1 (1989), Elsevier North Holland) · Zbl 0734.65031 |
| [5] | Å. Björck, H. Park, and L. Eldén, Accurate downdating of least squares solutions, SIAM J. Matrix Anal. Appl.; Å. Björck, H. Park, and L. Eldén, Accurate downdating of least squares solutions, SIAM J. Matrix Anal. Appl. · Zbl 0811.65034 |
| [6] | Bojanczyk, A. W.; Steinhardt, A. O., Stability analysis of a Householder-based algorithm for downdating the Cholesky factorization, SIAM J. Sci. Statist. Comput., 12, No. 5 (1991) · Zbl 0737.65013 |
| [7] | A.W. Bojanczyk, R.E. Funderlic, J.G. Nagy, and R.J. Plemmons, Multi-row Householder reflections, in preparation.; A.W. Bojanczyk, R.E. Funderlic, J.G. Nagy, and R.J. Plemmons, Multi-row Householder reflections, in preparation. · Zbl 0781.65032 |
| [8] | Daniel, J.; Gragg, W. B.; Kaufman, L.; Stewart, G. W., Reorthogonalization and stable algorithms for updating the Gram-Schmidt QR factorization, Math. Comp., 30, 772-795 (1976) · Zbl 0345.65021 |
| [9] | Ferng, W. R., Lanczos-Based Condition Estimation in Signal Processing and Optimization, (Ph.D. Thesis (1991), North Carolina State Univ: North Carolina State Univ Raleigh) |
| [10] | Ferng, W. R.; Golub, G. H.; Plemmons, R. J., Adaptive Lanczos methods in recursive condition estimation, Numer. Algorithms, 1, 1-20 (1991) · Zbl 0794.65043 |
| [11] | Gill, P. E.; Golub, G. H.; Murray, W.; Saunders, M. A., Methods for modifying matrix factorizations, Math. Comp., 20, 505-535 (1975) · Zbl 0289.65021 |
| [12] | Golub, G. H.; Van Loan, C., Matrix Computations (1989), Johns Hopkins U.P · Zbl 0733.65016 |
| [13] | Liu, K. J.R.; Hseih, S. F.; Yao, K., RLS filtering using Householder transformations, Proceedings of ICASSP, 1631-1634 (1990), Albuquerque, N. Mex. |
| [14] | Oppenheim, A. V.; Schafer, R. W., Discrete-Time Signal Processing (1989), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J · Zbl 0676.42001 |
| [15] | Pan, C.-T.; Plemmons, R. J., Least squares modifications with inverse factorizations: Parallel implications, Comput. Appl. Math., 27, 109-127 (1989) · Zbl 0677.65037 |
| [16] | Pierce, D. J.; Plemmons, R. J., Fast adaptive condition estimation, SIAM J. Matrix Anal. Appl., 13, 274-291 (1992) · Zbl 0747.65029 |
| [17] | C. Puglisi, Modification of the Householder method based on the compact WYSIAM J. Sci. Sstatist. Comput.; C. Puglisi, Modification of the Householder method based on the compact WYSIAM J. Sci. Sstatist. Comput. · Zbl 0756.65040 |
| [18] | Rader, C. M.; Steinhardt, A. O., Hyperbolic Householder reflections, IEEE Trans. Acoust. Speech Signal Process, 34, 6, 1589-1602 (1986) · Zbl 0629.93063 |
| [19] | Sakai, H., A vectorized systolic array for block RLS using inverse factorizations, Proceedings of ICASSP (1992), San Francisco |
| [20] | Schreiber, R.; Van Loan, C., A storage-efficient WY representation for products of Householder transformations, SIAM J. Sci. Statist. Comput., 10, 52-57 (1989) · Zbl 0664.65025 |
| [21] | Stewart, G. W., Perturbations bounds for the QR factorization of a matrix, SIAM J. Numer. Anal., 14, 509-518 (1977) · Zbl 0358.65038 |
| [22] | Stewart, G. W., The effects of rounding errors on an algorithm for downdating a Cholesky factorization, J. Inst. Math. Appl., 23, 203-213 (1979) · Zbl 0405.65019 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
