Technical Report ERGO 08-001

Trust-region and other regularisations of linear least-squares problems
Coralia Cartis, Nicholas I. M. Gould and Philippe L. Toint

Abstract:

We consider methods for regularising the least-squares solution of the linear system Ax = b. In particular, we propose iterative methods for solving large problems in which a trust-region bound ||x||<= Delta is imposed on the size of the solution, and in which the least value of linear combinations of ||Ax-b||2q and a regularisation term ||x||2p for various p and q=1,2 is sought. In each case, one of more "secular" equations are derived, and fast Newton-like solution procedures are suggested. The resulting algorithms are available as part of the GALAHAD optimization library.

Keywords:

Linear least-squares problems, Tikhonov regularisation, ridge regression, trust-region method, Newton's method, secular equation

Download:

ERGO-08-001.pdf

History:

Written: 3 February 2008

Status:

Published in BIT.