A new zero-finder for Tikhonov regularization (Q960039)

The author considers the problem of determining an approximate solution to the least-squares problem \(\min_{x\in {\mathbb R}^n}\|Ax-b\|\) with contaminated \(b\in {\mathbb R}^m\), where \(m\geq n\) is allowed. The matrix \(A\) has ill-determined rank, that is, it has several singular values of different size close to zero. Tikhonov's regularization uses an equivalent penalized least-square problem, \[ \min_{x\in {\mathbb R}^n}\{\|Ax-b\|^2+\|Lx\|^2/\beta\}, \] where \(\beta>0\) is a regularization parameter and \(L\in {\mathbb R}^{p\times n}\), \(p<n\), is a regularization operater. The discrepancy principle, \(\|Ax_\beta -b\|=\eta\epsilon\), is used to determine \(\beta\). The positive value of \(\beta\) is obtained by finding the zero of the decreasing convex function \(\phi(\beta)=\|b-Ax_\beta\|^2-\eta^2\epsilon^2\) by means of a cubically convergent method instead of Newton's quadradically convergent method, thus reducing numerically the cost by approximately 1/3.