Accuracy of TSVD solutions computed from rank-revealing decompositions (Q1893500)

The minimum norm solution of a least squares problem with an ill- conditioned matrix \(A\) does not contain valuable information if we assume that \(A\) is afflicted with some noise. In these cases, one can regularize the least squares problem by replacing the matrix \(A\) by the rank-\(k\) nearest neighbour in the 2-norm, where \(k\) is the number of the significantly small singular values of \(A\). The minimum norm solution of the regularized problem is termed the truncated singular value decomposition (TSVD) solution. Calculating the singular value decomposition (SVD) is computationally demanding and the SVD cannot easily be up- or downdated as is required in signal processing applications, e.g. Therefore, there is a need for cheaper methods which calculate sufficiently good approximations to the TSVD solution. This paper considers three such methods: The rank-revealing QR, URV and ULV factorizations. The authors establish that the accuracy of the approximations is determined by the quality of the approximation of `exact' numerical subspaces in \(A\) (defined through the SVD) by corresponding subspaces in the factorizations. They also show how iterative subspace refinement can be used to increase the accuracy of the approximation. Their results are illustrated by numerical examples for \(10 \times 30\) matrices.