Yang Liu

Yang Liu

Postdoc in math @ University of Oxford.

Obtaining Pseudo-inverse Solutions With MINRES

1 minute read

Published:

Introduction

Consider the least-squares problem

\[\min_{\mathbf{x} \in \mathbb{R}^d} || \mathbf{b} - \mathbf{A} \mathbf{x} ||^2,\]

where $ \mathbf{A} $ is symmetric. In order to solver it efficiently, one common approch is to use iterative solvers. Among them, MINRES is one of the most efficient solver with one Matrix-vector multiplication per iteration. However, MINRES can not obtain the pseudo-inverse solution $ \mathbf{x}^+ \triangleq \mathbf{A}^\dagger \mathbf{b} $ (also called the least-norm solution) when $ \mathbf{b} \not\in \text{Range}(\mathbf{A}) $.

Lifting Formula

We propose a simple lifting strategy to obtain $ \mathbf{x}^+ $, which is

\[\mathbf{y}_t = \mathbf{x}_t - \frac{<\mathbf{r}_t, \mathbf{x}_t>}{|| \mathbf{r}_t ||^2} \mathbf{r}_t\]

where $ \mathbf{r}_t \triangleq \mathbf{b} - \mathbf{A} \mathbf{x}_t $ and $ t $ is the iteration counter. When MINRES terminated at $ t=g $, we must have $ \mathbf{y}_g = \mathbf{A}^\dagger \mathbf{b} $. (Note that the lifting strategy can also be used in conjugate residual methods (CR).)

Numerical Experiments

We apply Nédélec finite elements to solve the following Maxwell PDE problem

\[\begin{aligned} \text{curl} \text{ curl } \mathbf{u} &= \mathbf{f} \quad \text{in } \Omega \\ \mathbf{u} \times \mathbf{n} &= 0 \quad \text{on } \partial \Omega \end{aligned}\]

with Firedrake and PETSc using our lifting strategy. We are particularly interested in this problem since it has infinitely many solutions for a general $ \mathbf{f} $. While we would like to find the least-norm solution among them using our lifting formula. Let us construct our problem in $ \mathbb{R}^2 $ with $ \mathbf{f} = \text{curl} \text{ curl } \mathbf{u}_{\text{exact}} + \mathbf{e} $, where $ \mathbf{e} $ is the projection of uniformly distributed random noise $ \mathcal{U}(-1, 1) $ onto the null space of the operator.

We can see that the lifting strategy recovered $ \mathbf{u}_{\text{exact}} $ successfully via the following recorded video. (From top to bottom: The MINRES iterates, The corresponding lifted MINRES iterates (of the above). From left to right: the Magnitude, the X-axis component, the Y-axis component of the current iterate.)