Title:

Stopping Criteria for the Iterative Solution of Large Sparse Linear Least
Squares Problems

Abstract:

The linear least squares (LS) problem has applications in numerous areas
of science and engineering, such as statistics, signal processing, machine
learning, geodesy, and navigation.  Iterative methods for the solution of
large sparse LS problems produce a sequence of iterates which hopefully
converges to the true LS solution.  One important question to ask when
using an iterative method is when to stop the iteration, in other words
when is a given iterate ``good enough"?  This is the main topic of the
present talk.

We first give an overview of the algorithm LSQR of Paige and Saunders for
solving large sparse LS problems.  We then define what we mean by an
acceptable LS solution and show that currently-used stopping criteria can
sometimes be much too conservative in detecting an acceptable iterate.  We
propose two new conditions, one of which is both necessary and sufficient,
to determine if a given iterate is an acceptable LS solution.  Finally, we
discuss how to efficiently estimate the quantities involved in these
stopping criteria at each iteration of LSQR.

This is joint work with Xiao-Wen Chang and Chris Paige.