A regularization of large linear least squares problems via rank revealing Hauseholder postmultiplications

In this paper we discuss a new iterative method that is suited for regularization of the series of large linear least squares problems. In each problem in the series the same rank-deficient coecient matrix A is used and weighted in a specific manner. The main feature of these problems is that the matrix A (not necessarily sparse) is having a cluster of small singular values, and there is a well-determined gap between its large and small singular values. The new algorithm uses (only once) properly chosen Hauseholder postmultiplications. These transformations provide an elegant way to extract a well-conditioned core subproblems of minimum dimension both for the linear least squares and the total least squares problem. Next, a modified version of the LSQR algorithm of Paige and Saunders is used to solve the particular weighted problems in a row. A partial reorthogonalization for maintaining semi-orthogonality among the Lanczos vectors is used. Examples showing promising results from numerical experiments are presented. As a by-product a new and eective spectral matrix norm estimator is given. Possible applications to signal processing, image processing, multiple linear regression and geographically weighted regression (GWR) are mentioned.