Rang revealing QR factorizations (Q578845)

This paper presents an algorithm for computing a column permutation, \(\Pi\), of an \(m\times n\) matrix A (m\(\geq n)\) so that in the QR factorization, \(A=QR\), rank deficiency of A is revealed in the lower right block of R. Such a factorization is convenient in many applications, such as least-squares for example. If r is the near-rank deficiency R is partitioned as \(R=\left[ \begin{matrix} R_{11}\\ 0\end{matrix} \begin{matrix} R_{12}\\ R_{22}\end{matrix} \right]\) \((R_{22}\) is \(r\times r)\) and certainly, if \(\| R_{22}\|\) is small in the \(\ell_ 2\) norm, A has at least r small singular values, though the converse is not true. \textit{G. H. Golub}, \textit{V. Klema} and \textit{G. W. Stewart} [Tech. Rep. STAN-CS-76-559 (1976)] have published a method based on the SVD of A. The present method does not make use of SVD but generalizes a method for revealing rank-one deficiency. The first step requires any QR-factorization of A, followed by a sequence of r iterations, each of which requires computation of the singular vector v of \(R_{11}\) by inverse iteration and the QR factorization of \(R_{11}P\), where P is a permutation matrix. It is shown that the elements of the final \(R_{11}\) are bounded by \(| r_{ij}| \leq 2^{j-i} \sigma_ in^{1/2},\) \(n-r<i\leq j\leq n\) where \(\sigma_ i\) is the ith singular value of A. The author also shows that the total work involved in the algorithm is roughly half that for the usual SVD of A. Numerical examples indicate that the algorithm, which is guaranteed to work for matrices of low rank deficiency, will almost always work for the high rank case as well.