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.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.identifier.uri | http://hdl.handle.net/1903/920 | |
| dc.language.iso | 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 |
| 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 |