Approximating minimum norm solutions of rank-deficient least squares problems (Q4940815)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1406962
Language Label Description Also known as
default for all languages
No label defined
    English
    Approximating minimum norm solutions of rank-deficient least squares problems
    scientific article; zbMATH DE number 1406962

      Statements

      0 references
      0 references
      27 February 2000
      0 references
      bidiagonalization
      0 references
      linear least squares problem
      0 references
      minimum norm solution
      0 references
      rank deficient
      0 references
      regularization
      0 references
      Riley-Golub iteration
      0 references
      singular value decomposition
      0 references
      Approximating minimum norm solutions of rank-deficient least squares problems (English)
      0 references
      The authors consider the solution of the linear least squares problem \[ \min _x \|Ax-b\|^2_2. \] The matrix \(A\in R^{m\times n}\) is rank deficient. Let us put \(p=\min \{m,n\}\), \(\sigma _i, i = 1,\ldots ,p\) denote the singular values of \(A\) and \(u_i,v_i\) denote the corresponding left and right singular vectors. Then the minimum norm solution of the least squares problem has the form \[ x^* = \sum ^r_{i=1} (u^T_i b/\sigma _i)v_i, \] where \(r\leq p\) is the rank of \(A\). It is known that the Riley-Golub iteration method originally due to \textit{J. D. Riley} [Math. Tables Aids Comput. 9, 96-101 (1955; Zbl 0033.10102)] and modified by \textit{G. Golub} [Numer. Math. 7, 206-216 (1965; Zbl 0142.11502)], it is \[ x_{k+1} =\mathop{\arg \min }_x \{\|Ax-b\|^2_2 + \lambda \|x- x_k \|^2_2\}, \] converges to the minimum norm solution if \(x_0 = 0\) is chosen. The iteration should be implemented by taking advantage of a bidiagonal decomposition of \(A\) which needs \(O(p)\) operations only. Both the singular values \(\sigma _i\) and the scalar products \(u^T_ib\) can be computed at marginal extra cost. The regularization parameter \(\lambda \) and the number of iterations \(k\) are to be determined. The numerical rank is easily computed by using singular values. The solution \(x^*\) is approximated without computing the singular vectors of \(A\). Numerical experiments illustrate that the authors' method gives more accurate approximations than that based on a \(QR\) decomposition with column pivoting.
      0 references

      Identifiers