Obtaining Pseudoinverse Solutions with MINRES

Yang Liu, Andre Milzarek, Fred RoostaSIAM J. Matrix Anal. Appl 2025 · DOI

TL;DR

This paper introduces a simple yet effective "MN refinement" technique that seamlessly integrates with the MINRES iterative solver. This refinement allows MINRES to reliably compute the minimum-norm (pseudo-inverse) solution for linear least-squares problems, even when the system is inconsistent, without significant additional computational cost. This is particularly valuable for large-scale, ill-conditioned problems where traditional methods are infeasible.

What Problem Does This Paper Address?

Many real-world problems, such as those in optimization, signal processing, and scientific computing, can be formulated as linear least-squares problems of the form $\min \|b - Ax\|^2$. When the system is inconsistent (i.e., $b$ is not in the range of $A$), there are infinitely many solutions. Among these, the minimum-norm solution, also known as the pseudo-inverse solution ($A^\dagger b$), is often the most desirable due to its desirable mathematical properties and applications.

While direct methods like Singular Value Decomposition (SVD) can compute the pseudo-inverse solution, they are computationally expensive for large-scale problems. Iterative methods like MINRES are more suitable for large systems. However, the standard MINRES algorithm is not guaranteed to converge to the pseudo-inverse solution when the system is inconsistent. Existing methods that do guarantee the pseudo-inverse solution (like MINRES-QLP) are often more complex and computationally demanding. This paper addresses the need for a computationally efficient and simple way to obtain the pseudo-inverse solution using the widely-used MINRES algorithm.

Methods

The core contribution is the MN refinement. This technique is applied to the final iterate of the MINRES algorithm. The idea is to leverage the structure of the MINRES solution, which can be expressed as the sum of the true pseudo-inverse solution and a component in the null space of $A$. The MN refinement effectively removes this null-space component.

The paper details the MN refinement for:

  • Hermitian systems: A straightforward refinement is derived based on the final MINRES iterate and residual.
  • Complex-symmetric systems: The refinement is extended by building upon existing MINRES extensions for such matrices.
  • Preconditioned systems: The MN refinement is further generalized to settings where preconditioning is used to improve convergence. This includes cases with positive semi-definite and even singular preconditioners.

The MN refinement is designed to be applied after the standard MINRES iterations have completed, requiring only a few additional vector operations, thus incurring negligible computational overhead.

Datasets

Not discussed in the paper. The paper uses synthetic data and standard problems (PDEs, image deblurring) for evaluation.

Key Insights and Ideas

  • Simplicity and Efficiency: The MN refinement is remarkably simple and adds minimal computational cost to the existing MINRES algorithm, making it highly practical.
  • Universality: The technique is shown to work for Hermitian, complex-symmetric, and preconditioned systems, demonstrating its broad applicability.
  • Bridging the Gap: It effectively bridges the gap between standard MINRES (which doesn't guarantee the pseudo-inverse solution for inconsistent systems) and more complex methods like MINRES-QLP.
  • Understanding MINRES Iterates: The MN refinement provides a deeper understanding of the structure of MINRES iterates, particularly how they relate to the true pseudo-inverse solution and the null space of the matrix.
  • Preconditioning Nuances: The paper highlights that for inconsistent systems, the choice of preconditioner can be more subtle than for consistent systems, and singular preconditioners can be effective but require careful consideration.

Key Results

  • Theorems 1 and 2: Formally establish the MN refinement for Hermitian and complex-symmetric systems, proving that it recovers the exact pseudo-inverse solution ($A^\dagger b$) from the final MINRES iterate.
  • Theorems 3 and 4: Generalize the MN refinement to preconditioned Hermitian and complex-symmetric systems, respectively.
  • Numerical Experiments:
    • Figure 1 demonstrates that the MN refinement iterates converge to the true pseudo-inverse solution much faster and more accurately than plain MINRES iterates for both Hermitian and complex-symmetric cases.
  • Figure 2 shows that for a Maxwell problem, the MN refinement of the MINRES iterate provides a good approximation of the exact solution, unlike the noisy MINRES iterate.
  • Figure 3 and 4 showcase image deblurring results. The MN refinement significantly improves the quality of deblurred images obtained from MINRES and MINRES-QLP, often achieving competitive results with LSMR but with much lower computational cost.
  • Figure 5 and 6 explore preconditioned image deblurring, showing that the MN refinement is crucial for obtaining good quality reconstructions, especially when using singular preconditioners.

Limitations and Future Work

  • Preconditioner Choice: The paper notes that for preconditioned systems, especially with singular preconditioners, the choice of the preconditioner is critical. If the range of the preconditioner does not align well with the range of the matrix $A$, the results can be poor (as seen in Figure 6).
  • Future Work: The authors suggest further investigations into the behavior of singular preconditioners and their impact on obtaining pseudo-inverse solutions in more general settings. They also mention that the MN refinement technique could potentially be extended to other least-squares solvers that exhibit similar null-space components in their iterates.

Summary updated

BibTeX
@article{liu2025obtaining,
  author = {Yang Liu and Andre Milzarek and Fred Roosta},
  title = {{Obtaining Pseudoinverse Solutions with MINRES}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2025},
  doi = {10.1137/24m1638422},
}

Loading related content...

Figure