On an Inexpensive Triangular Approximation to the Singular Value Decomposition

 Title On an Inexpensive Triangular Approximation to the Singular Value Decomposition Publication Type Reports Year of Publication 1998 Authors Stewart G.W Date Published 1998/10/15/ Institution Instititue for Advanced Computer Studies, Univ of Maryland, College Park Keywords Technical Report Abstract In this paper we introduce a new decomposition called the pivotedQLP~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) URL http://drum.lib.umd.edu/handle/1903/920