The pivoted QLP decomposition, introduced by G. W. Stewart, represents the first two steps in an algorithm which approximates the SVD. The matrix A P₀ is first factored as A P₀ = QR, and then the matrix R^T P₁ is factored as R^T P₁ = PL^T, resulting in A = Q P₁LP^TP₀^T, with Q and P orthogonal, L lower-triangular, and P₀ and P₁ permutation matrices. Stewart noted that the diagonal elements of L approximate the singular values of A with surprising accuracy. We provide mathematical justification for this phenomenon. If there is a gap between s_k and s_k+1, partition the matrix L into diagonal blocks L₁₁ and L₂₂ and off-diagonal block L₂₁, where L₁₁ is k-by-k. We show that the convergence of ||L₁₁^-1|| to s_k^-1 and of ||L₂₂|| to s_k+1 is cubic in s_k^-1 and s_k+1, respectively. One order is due to the rank-revealing pivoting in the first step; then, two more orders are achieved in the second step. We show that the relative errors between ||L₁₁^-1|| and s_k^-1 and between ||L₂₂|| and s_k+1 are quadratic in the gap, s_k+1/s_k. Our analysis assumes that P₁ = I, that is, that pivoting need be done only on the first step. The algorithm can be continued beyond the first two steps, and we give some results concerning the assymptotic convergence. For example, we point out that repeated singular values can accelerate convergence, indicating that the QLP decomposition can be powerful even when the ratios between neighboring singular values are small. We also follow Stewart in considering truncating and interleaving the algorithm, with an eye toward obtaining an efficient approximation to the truncated SVD for low-rank problems. Instead of computing the matrix R in its entirety and then computing the matrix L, the algorithm can be truncated, computing only the first k rows of R and columns of L. Moreover, the computation can be interleaved, alternately computing rows of R and columns of L. This is possible because of the nonnecessity of pivoting in the second step. We demonstrate that truncating (and interleaving) actually works by extending our theory for the complete pivoted QLP decomposition. In particular, we show that if we compute only an r-by-r matrix L (instead of the full n-by-n), the convergence of ||L^-1|| to s_r^-1 is cubic in s_r^-1. The relative error between ||L^-1|| and s_r^-1 is quadratic in the gap, s_r+1/s_r. For a matrix having numerical rank r, the truncated pivoted QLP decomposition can be computed in \EuScript O(mnr) time, making it ideal for accurate SVD approximations for low-rank problems. We propose iterating the algorithm once or twice more, obtaining even better approximations of the first r singular values for almost no extra cost.

Footnotes:

¹ Joint work with David A. HUCKABY.