Bounds on singular values revealed by QR factorizations

摘要

The authors introduce a pair of dual concepts: pivoted blocks and reverse pivoted blocks. These blocks are the outcome of a special column pivoting strategy in QR factorization. The main result is that under such a column pivoting strategy, the Qr factorization of a given matrix can give tight estimates on any two a priori-chosen consecutive singular values of that matrix. In particular, a rank-revealing QR factorization is guaranteed when the two chosen consecutive singular values straddle a gap in the singular value spectrum that gives rise to the rank degeneracy of the given matrix. The pivoting strategy, called cyclic pivoting, can be viewed as a generalization of Golub's column pivoting and Stewart's reverse column pivoting. Numerical experiments confirm the tight estimates that the theory asserts.