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
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
0.9335072
0 references
0 references
0.92569846
0 references
0.9232286
0 references
0.92087436
0 references
0 references
0.9189305
0 references
0.9144478
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