Stewart's pivoted QLP decomposition for low‐rank matrices
Dale A. Huckaby, Tony Fan-Cheong Chan · Numerical Linear Algebra with Applications · 2004
Abstract 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 R T ∏ 1 is factored as R T ∏ 1 = PL T , resulting in A = Q ∏ 1 LP 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 L 11 and L 22 and off‐diagonal block L 21 , where L 11 is k ‐by‐ k . If we compute only the block L 11 , the convergence of (σ j ( L 11 ) −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. Copyright © 2004 John Wiley & Sons, Ltd.