## Abstract

The pivoted QLP decomposition, introduced by Stewart [20], represents the first two steps in an algorithm which approximates the SVD. The matrix A ∏_{0} is first factored as A ∏_{0} = QR, and then the matrix A^{T}∏_{1} is factored as K^{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} i permutation matrices. Stewart noted that the diagonal elements of L approximate the singular values of A with surprising accuracy. In this paper, we provide mathematical justification for this phenomenon. If there is a gap between σ_{k} and σ_{k}+1, 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. We show that the convergence of (σ_{j}-(L_{11})^{-1} -σ_{j} ^{-1})/σ_{j}^{-1} for j = 1, . . . , k, and of (σ_{j}-(L_{22}) - σ_{k+j})/σ _{k+j} for j = 1, . . ., n - k, are all quadratic in the gap ratio σ_{k+1}/σ_{k}. The worst case is therefore at the gap, where the absolute errors !!L_{11}^{-1}!! - σ _{k}^{-1} and !!L_{22}!! - σ_{k+1} are thus cubic in σ_{k}^{-1} and σ_{k+1}, respectively. One order of convergence is due to the rank-revealing pivoting in the first step; then, because of the pivoting in the first step, two more orders are achieved in the second step. Our analysis assumes that ∏ _{1} = I, that is, that pivoting is done only on the first step. Although our results explain some of the properties of the pivoted QLP decomposition, they hypothesize a gap in the singular values. However, a simple example shows that the decomposition can perform well even in the absence of a gap. Thus there is more to explain, and we hope that our paper encourages others to tackle the problem. The QLP algorithm can be continued beyond the first two steps, and we make some observations concerning the asymptotic convergence. For example, we point out that repeated singular values can accelerate convergence of individual elements. This, in addition to the relative convergence to all of the singular values being quadratic in the gap ratio, further indicates that the QLP decomposition can be powerful even when the ratios between neighboring singular values are close to one.

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

Pages (from-to) | 287-316 |

Number of pages | 30 |

Journal | Numerical Algorithms |

Volume | 32 |

Issue number | 2 |

State | Published - Jan 2003 |

Externally published | Yes |

### Bibliographical note

Funding Information:∗The work in this paper was supported by NSF grants DMS-9973341 and ACI-0072112. ∗∗Corresponding author.

## Keywords

- Pivoted QLP decomposition
- QLP
- QR
- SVD
- Singular values

## ASJC Scopus subject areas

- Applied Mathematics