An efficient rank detection procedure for modifying the ULV decomposition

The ULV decomposition (ULVD) is an important member of a class of rank-revealing two-sided orthogonal decompositions used to approximate the singular value decomposition (SVD). The problem of adding and deleting rows from the ULVD (called updating and downdating, respectively) is considered. The ULVD can be updated and downdated much faster than the SVD, hence its utility. When updating or downdating the ULVD, it is necessary to compute its numerical rank. In this paper, we propose an efficient algorithm which almost always maintains rank-revealing structure of the decomposition after an update or downdate without standard condition estimation. Moreover, we can monitor the accuracy of the information provided by the ULVD as compared to the SVD by tracking exact Frobenius norms of the two small blocks of the lower triangular factor in the decomposition.