On the Successive Projections Approach to Least-Squares Problems

In this paper, we suggest a generalized Gauss-Seidel approach to sparse linear and nonlinear least-squares problems. The algorithm, closely related to one given by Elfving (1980), uses the work of Curtis, Powell, and Reid (1974) as extended by Coleman and Moré (1983) to divide the variables into nondisjoint groups of structurally orthogonal columns and then projects the updated residual into each column subspace of the Jacobian in turn. In the linear case, this procedure can be viewed as an alternate ordering of the variables in the Gauss-Seidel method. Preliminary tests indicate that this leads quickly to cheap solutions of limited accuracy for linear problems, and that this approach is promising for an inexact Gauss-Newton analog of the inexact Newton approach of Dembo, Eisenstat, and Steihaug (1981)