Low-rank Revealing QR Factorizations

Rank revealing factorizations are used extensively in signal processing in connection with, for example, linear prediction and signal subspace algorithms. We present an algorithm for computing rank revealing QR factorizations of low-rank matrices. The algorithm produces tight upper and lower bounds for all the largest singular values, thus making it particularly useful for treating rank deficient problems by means of subset selection, truncated QR, etc. The algorithm is similar in spirit to an algorithm suggested earlier by Chan for matrices with a small nullity, and it can also be considered as an extension of ordinary column pivoting.