In minisymposium: Recent Advances in the Solution of Least Squares Problems
Fri 10:30–11:00, Room AV 91.20Application 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.
- 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.
- 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.
- 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.