ILAS2016 — 11–15 July 2016 — KU Leuven, Belgium

20th Conference of the International Linear Algebra Society (ILAS)

20th ILAS Conference

In minisymposium: Recent Advances in the Solution of Least Squares Problems

Fri 10:30–11:00, Room AV 91.20
Application of inner-iteration preconditioning to general least squares problems
Keiichi Morikuni (University of Tsukuba)

Consider solving general least squares problems

\begin{align} \min_{\boldsymbol{x} \in \mathcal{S}} \| \boldsymbol{x} \|_2, \quad \mathcal{S} = \mathop{\mbox{arg\,min}}_{\boldsymbol{y} \in \mathbb{R}^n} \| \boldsymbol{b} - A \boldsymbol{y}\|_2, \label{eq:gls} \end{align}

where $A \in \mathbb{R}^{m \times n}$ may be rank-deficient and $\boldsymbol{b} \in \mathbb{R}^m$. A solution to \eqref{eq:gls} is unique and is the minimum-norm solution of the least squares problem $\min_{\boldsymbol{x} \in \mathbb{R}^n} \| \boldsymbol{b} - A \boldsymbol{x} \|_2$. The CGLS, LSQR, and LSMR methods with no preconditioning applied to the least squares problem $\min_{\boldsymbol{x} \in \mathbf{R}^n} \| \boldsymbol{b} - A \boldsymbol{x} \|_2$ with an initial iterate in the range of $A^\mathsf{T}$ determine the solution to \eqref{eq:gls}. However, these methods with preconditioning do not necessarily determine the solution of \eqref{eq:gls}. Now to utilize preconditioning for solving \eqref{eq:gls}, we employ a two-step procedure, whose first step is to solve a least squares problem and second step is to solve a linear system of equations. We propose applying the generalized minimal residual (GMRES) methods with left and right-preconditioning (BA and AB-GMRES methods [1], respectively) using inner iterations [2], [3] to the first and second steps, respectively, for solving \eqref{eq:gls}. Numerical experiments on benchmark problems show that the proposed method is more efficient than previous methods.

  1. K. Hayami, J.-F. Yin, and T. Ito, GMRES methods for least squares problems, SIAM Journal on Matrix Analysis and Applications, 31(5) (2010), pp. 2400–2430.
  2. K. Morikuni and K. Hayami, Inner-iteration Krylov subspace methods for least squares problems, SIAM Journal on Matrix Analysis and Applications, 34(1) (2013), pp. 1–22.
  3. K. Morikuni and K. Hayami, Convergence of inner-iteration GMRES methods for rank-deficient least squares problems, SIAM Journal on Matrix Analysis and Applications, 36(1) (2015), pp. 225–250.