Gene Golub Stanford University

Abstract:

The standard least-squares problem is to minimize , where A is an matrix, with m greater than n, b is an m-dimensional vector, and indicates the Euclidean norm of the vector. Frequently in practice, the data A and b are not known exactly. The TLS algorithm and regularization-based methods are popular schemes for handling such uncertainties.

We propose several new formulations of least-squares type problems which explicitly include bounds on the uncertainties and which regularize the solution. We also provide efficient algorithms for their solution.

The direct solution of the least squares problem may lead to a vector x that is severely contaminated with noise. Tikhonov regularization addresses this problem by solving instead the linear least squares problem

The solution  satisfies the equation

The choice of an appropriate regularization parameter  is crucial, and many methods have been proposed for this purpose. One method handles the case where the norm of the noise vector e is known:

Morozov's discrepancy principle

The value of  is chosen such that the norm of the residual  equals the norm of the error term:

Generalized cross-validation

The value of  is computed as the global minimizer of

Another formulation is the following min-max problem

which can be shown to be equivalent to

Its solution can be written in the form

where is a non-negative real number obtained as the root of a certain secular equation. We have efficient and reliable numerical algorithms for finding , which in fact can be interpreted as an automatic regularization parameter that minimises the worst-case residual.

For large scale problems iterative methods become necessary. We will discuss how the Lanczos algorithm can be used to approximate the functions  . In most cases we can compute lower and upper bounds on  , and these bounds become tighter as the number of Lanczos iterations increases. In the case of GCV a stochastic trace estimator is used to approximate the denominator in  .

This talk represents joint work with S. Chandrasekaran, M. Gu, A. H. Sayed and U. von Matt.

[Gene Golub, Department of Computer Science, Stanford University, Stanford, CA 94305-2140, golub@na-net.ornl.gov]