The truncated SVD as a method for regularization (Q1096333)

The paper deals with the unconstrained linear least squares problem (1) \(\min \| Ax-B\|\), \(A\in {\mathbb{R}}^{m\times n}\), \(m\geq n\), for an ill-conditioned matrix A. There are two well-known attempts to deal with such ill-posed problems: the method of regularization by Tikhonov and Phillips and the truncated singular value decomposition (TSVD). Let \(A=U\Sigma V^ T\) be the singular value decomposition (SVD) of the matrix A; here \(U\in {\mathbb{R}}^{m\times m}\), \(V\in {\mathbb{R}}^{n\times n}\) are orthogonal, \(\Sigma =diag\{\sigma_ 1,\sigma_ 2,...,\sigma_ n\}\) and \(\sigma_ i\) are singular values of A. The TSVI solution of (1) is defined as \(x_ k=A^+_ kB\), where \(A^+_ k\) is the pseudoinverse of \(A_ k=U\Sigma_ kV^ T,\Sigma_ k=diag\{\sigma_ 1,...,\sigma_ k,0,...,0\}.\) To analyze the behaviour of TSVD solutions a perturbation theory is developed. It states that the perturbed TSVD solution can be guaranteed to be closed to the true solution if the relative gap \(\omega_ k=\| A-A_ k\| \cdot \| A^+_ k\| =\sigma_{k+1}/\sigma_ k\) between the singular values \(\sigma_ k\) and \(\sigma_{k+1}\) is small. This divides all ill-conditioned matrices into two classes: those with well-determined numerical rank and with ill-determined numerical rank. It is proved that for the matrices of the first class the TSVD solution is close to the regularized solution provided the regularization parameter is chosen properly. Finally, the case of matrices with ill-determined numerical rank is discussed.