Stewart's pivoted QLP decomposition for low-rank matrices

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Π₀ is first factored as AΠ₀ = QR, and then the matrix R^TΠ₁ is factored as R ^TΠ₁=PL^T, resulting in A = QΠ ₁LP^TΠ,₀^T with Q and P orthogonal, L lower-triangular, and Π₀ and Π₁ 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 L₁₁ and L₂₂ and off-diagonal block L ₂₁, where L₁₁ is k-by-k. If we compute only the block L₁₁, the convergence of (σ_j(L₁₁) ^-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.