The pivoted QLP decomposition, introduced by Stewart, represents the first two steps in an algorithm which approximates the SVD. If A is an m-by-n matrix, the matrix AΠ0 is first factored as AΠ0 = QR, and then the matrix RTΠ1 is factored as R TΠ1=PLT, resulting in A = QΠ 1LPTΠ,0 T with Q and P orthogonal, L lower-triangular, and Π0 and Π1 permutation matrices. The Q and P matrices provide approximations of the left and right singular subspaces, and the diagonal elements of L are excellent approximations of the singular values of A. Stewart observed that pivoting is not necessary in the second step, allowing one to efficiently truncate the decomposition, computing only the first few columns of R and L and choosing the stopping point dynamically. In this paper, we demonstrate that this truncating actually works by extending our theory for the complete pivoted QLP decomposition (UCLA CAM Report # 02-29, 2002). In particular, say there is a gap between σ k and σk+1, and partition the matrix L into diagonal blocks L11 and L22 and off-diagonal block L 21, where L11 is k-by-k. If we compute only the block L11, the convergence of (σj(L11) -1 -σj -1)/σj -1 for j = 1,...,k are all quadratic in the gap ratio σ k+1/σk. Hence, if the gap ratio is small, as it usually is when A has numerical rank k (independent of m and n), then all of the singular values are likely to be well approximated. This truncated pivoted QLP decomposition can be computed in (mnk) time, making it ideal for accurate SVD approximations of low-rank matrices.
- Singular values
- Stewarts's pivoted QLP decomposition
ASJC Scopus subject areas
- Algebra and Number Theory
- Applied Mathematics