## 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}Π,_{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 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} -σ_{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.

Original language | English (US) |
---|---|

Pages (from-to) | 153-159 |

Number of pages | 7 |

Journal | Numerical Linear Algebra with Applications |

Volume | 12 |

Issue number | 2-3 |

DOIs | |

State | Published - Mar 2005 |

Externally published | Yes |

## Keywords

- Low-rank
- Singular values
- Stewarts's pivoted QLP decomposition

## ASJC Scopus subject areas

- Algebra and Number Theory
- Applied Mathematics