Abstract
An alternative to performing the singular value decomposition is to factor a matrixA into\(A = U\left( {\begin{array}{*{20}c} C \\ 0 \\ \end{array} } \right)V^T \), whereU andV are orthogonal matrices andC is a lower triangular matrix which indicates a separation between two subspaces by the size of its columns. These subspaces are denoted byV = (V 1,V 2), where the columns ofC are partitioned conformally intoC = (C 1,C 2) with ‖C 2 ‖ F ≤ ε. Here ε is some tolerance. In recent years, this has been called the ULV decomposition (ULVD).
If the matrixA results from statistical observations, it is often desired to remove old observations, thus deleting a row fromA and its ULVD. In matrix terms, this is called a downdate. A downdating algorithm is proposed that preserves the structure in the downdated matrix\(\bar C\) to the extent possible. Strong stability results are proven for these algorithms based upon a new perturbation theory.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. L. Barlow,Stability analysis of the G-algorithm and a note on its application to sparse least squares problems, BIT, 25 (1985), pp. 507–520.
J. L. Barlow and J. W. Demmel,Computing accurate eigensystems of scaled diagonally dominant matrices, SIAM J. Numer. Anal., 27 (1990), pp. 762–791.
J. L. Barlow and S. L. Handy,The direct solution of weighted and equality constrained least squares problems, SIAM J. Sci. Stat. Computing, 9 (1988), pp. 704–716.
J. L. Barlow, P. A. Yoon, and H. Zha,An algorithm and a stability theory for downdating the ULV decomposition, Technical Report CSE-95-010, Department of Computer Science and Engineering, The Pennsylvania State University, April 1995.
J. L. Barlow, H. Zha, and P. A. Yoon,Efficient and stable algorithms for modifying the singular value decomposition and partial singular value decomposition, Technical Report CSE-93-19, Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA, September 1993. Submitted to Numer. Math.
A. Björck,Stability analysis of the method of semi-normal equations for linear least squares problems, Linear Algebra Appl., 88/89 (1987), pp. 31–48.
Å. Björck, H. Park, and L. Eldén,Accurate downdating of least squares solutions, SIAM J. Matrix Anal. Appl., 15 (1994), pp. 549–568.
J. W. Demmel and K. Veselić,Jacobi's method is more accurate than QR, SIAM J. Matrix Anal. Appl., 13 (1992), pp. 1204–1243.
J.J. Dongarra, J.R. Bunch, C.B. Moler, and G.W. Stewart,LINPACK User's Guide, SIAM Publications, Philadelphia, 1979.
L. Eldén and H. Park,Perturbation analysis of block downdating of a Cholesky decomposition, Numer. Math., to appear.
R. D. Fierro,Perturbation analysis for two-sided (or complete) orthogonal decompositions, Technical Report 94-02, Department of Mathematics, California State University, San Marcos, CA, February 1994.
R. D. Fierro and J.R. Bunch,Bounding the subspaces from rank revealing two-sided orthogonal decompositions, Technical Report 94-05, Department of Mathematics, California State University, San Marcos, CA, May 1994.
R. D. Fierro and P. C. Hansen,Approximating the LS and TLS solutions by rank revealing two-sided orthogonal decomposition, Technical Report 93-16, Department of Mathematics, University of California at Los Angeles, Los Angeles, CA, 1993.
P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders,Methods for modifying matrix factorizations, Math. Comp., 28 (1974), pp. 505–535.
G. H. Golub and C. F. Van Loan,Matrix Computations, Second Edition, The Johns Hopkins Press, Baltimore, 1989.
S. Van Huffel and J. Vandewalle,The Total Least Squares Problem: Computational Aspects and Analysis, SIAM Publications, Philadelphia, 1991.
S. Van Huffel and H. Zha,An efficient total least squares algorithm based on a rank revealing two-sided orthogonal decomposition, Numerical Algorithms, 4 (1993), pp. 101–133.
T. Kato,A Short Introduction to Perturbation Theory for Linear Operators, Springer-Verlag, New York, 1982.
C. L. Lawson and R. J. Hanson,Solving Least Squares Problems, Prentice-Hall, Englewood Cliff, NJ, 1974.
C.-T. Pan.A modification to the LINPACK downdating algorithm. BIT, 30:707–722, 1990.
C.-T. Pan,A perturbation analysis on the problem of downdating a Cholesky factorization, Linear Algebra Appl., 183 (1993), pp. 103–115.
H. Park and L. Elden.Downdating the rank-revealing URV decomposition, SIAM J. Matrix Anal. Appl., 16 (1995), pp. 138–156.
G. W. Stewart,The effects of rounding error on an algorithm for downdating a Cholesky factorization, J. Inst. Maths. Applies., 23 (1979), pp. 203–213.
G. W. Stewart,Two simple residual bounds for the eigenvalues of a Hermitian matrix, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 205–209.
G. W. Stewart,Updating a rank-revealing ULV decomposition, SIAM J. Matrix Anal. Appl., 14 (1993), pp. 494–499.
Author information
Authors and Affiliations
Additional information
The research of Jesse L. Barlow and Hongyuan Zha was supported by the National Science Foundation under grant no. CCR-9201612(Barlow) and CCR-9308399(Zha). The research of Peter A. Yoon was supported by the Office of Naval Research under the Fundamental Research Initiatives Program. Peter A. Yoon also has an appointment with the Applied Research Laboratory, The Pennsylvania State University, University Park, PA 16802, USA
Rights and permissions
About this article
Cite this article
Barlow, J.L., Yoon, P.A. & Zha, H. An algorithm and a stability theory for downdating the ULV decomposition. Bit Numer Math 36, 14–40 (1996). https://doi.org/10.1007/BF01740542
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01740542