# On an Inexpensive Triangular Approximation to the Singular Value Decomposition

 dc.contributor.author Stewart, G. W. en_US dc.date.accessioned 2004-05-31T22:48:13Z dc.date.available 2004-05-31T22:48:13Z dc.date.created 1997-10 en_US dc.date.issued 1998-10-15 en_US dc.identifier.uri http://hdl.handle.net/1903/920 dc.description.abstract In this paper we introduce a new decomposition called the pivoted QLP~decomposition. It is computed by applying pivoted orthogonal triangularization to the columns of the matrix \$X\$ in question to get an upper triangular factor \$R\$ and then applying the same procedure to the rows of \$R\$ to get a lower triangular matrix \$L\$. The diagonal elements of \$R\$ are called the R-values of \$X\$; those of \$L\$ are called the L-values. Numerical examples show that the L-values track the singular values of \$X\$ with considerable fidelity\,---\,far better than the R-values. At a gap in the L-values the decomposition provides orthonormal bases of analogues of row, column, and null spaces provided of \$X\$. The decomposition requires no more than twice the work required for a pivoted QR~decomposition. The computation of \$R\$ and \$L\$ can be interleaved, so that the computation can be the rows of \$R\$ to get a lower triangular matrix \$L\$. The diagonal elements of \$R\$ are called the R-values of \$X\$; those of \$L\$ are called the L-values. Numerical examples show that the L-values track the singular values of \$X\$ with considerable fidelity\,---\,far better than the R-values. At a gap in the L-values the decomposition provides orthonormal bases of analogues of row, column, and null spaces provided of \$X\$. The decomposition requires no more than twice the work required for a pivoted QR~decomposition. The computation of \$R\$ and \$L\$ can be interleaved, so that the computation can be terminated at any suitable point, which makes the decomposition especially suitable for low-rank determination problems. The interleaved algorithm also suggests a new, efficient 2-norm estimator. (Also cross-referenced as UMIACS-TR-97-75) en_US dc.format.extent 220896 bytes dc.format.mimetype application/postscript dc.language.iso en_US dc.relation.ispartofseries UM Computer Science Department; CS-TR-3840 en_US dc.relation.ispartofseries UMIACS; UMIACS-TR-97-75 en_US dc.title On an Inexpensive Triangular Approximation to the Singular Value Decomposition en_US dc.type Technical Report en_US dc.relation.isAvailableAt Digital Repository at the University of Maryland en_US dc.relation.isAvailableAt University of Maryland (College Park, Md.) en_US dc.relation.isAvailableAt Tech Reports in Computer Science and Engineering en_US dc.relation.isAvailableAt UMIACS Technical Reports en_US
﻿