3
$\begingroup$

I need to solve an equation system $$ \begin{pmatrix} A \\ I \end{pmatrix} x = \begin{pmatrix} b_0\\b_1 \end{pmatrix} $$ in the least-squares sense. Let's assume $I$ is the $n$-by-$n$ identity matrix, $A$ is some $m$-by-$n$ matrix, e.g., Laplace with Poisson boundary conditions.

I know a good preconditioner $M$ for $A$, so solving $$ M^{-1} A x = M^{-1} b $$ is easy. Can I make use of this when solving the least-squares problem?

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Of course, your new preconditioner is $$P = \begin{bmatrix} M & 0 \\ 0 & I \end{bmatrix}$$ and you solve the preconditioned system $$P^{-1}\begin{bmatrix} A\\ I \end{bmatrix} x = P^{-1}\begin{bmatrix} b_0 \\ b_1\end{bmatrix}$$. Depending on the language/software package you use, implementation may be different; but in MATLAB, preconditioning LSQR (mathworks.com/help/matlab/ref/lsqr.html) is no different from preconditioning GMRES. $\endgroup$
    – Abdullah Ali Sivas
    Aug 7, 2021 at 18:46
  • $\begingroup$ I could be wrong but this looks to me that this is not the correct representation. Isn't $x=b_1$ a constraint that needs to be satisfied together with the equation $A x = b_0$? $\endgroup$
    – Chenna K
    Aug 7, 2021 at 21:29
  • $\begingroup$ @AbdullahAliSivas, if the objective is to solve the equation in the least-squares sense, then isn't the final equation $\left[ A^T A + I \right] x = A^T b_0 + b_1$? If so, I am not sure if one can still use M as the preconditioner. $\endgroup$
    – Chenna K
    Aug 7, 2021 at 21:32
  • $\begingroup$ @ChennaK, firstly, that system is rarely explicitly formed in practice since SpMM is expensive. Secondly, it depends. It will do the job in the sense that one can solve the preconditioned linear system faster than the original system. But as Federico Poloni pointed out, you may not obtain the "unique" solution (assuming [A;I] is full-column rank) to the original system, but another solution. If the target is to solve the linear system then this should work. If it is to find the least squares solution, it may not. $\endgroup$
    – Abdullah Ali Sivas
    Aug 7, 2021 at 23:10
  • $\begingroup$ @AbdullahAliSivas How is the solution of the preconditioned problem the same as the original problem? See Federico's reply. $\endgroup$
    – Nico Schlömer
    Aug 8, 2021 at 13:04

1 Answer 1

Reset to default
2
$\begingroup$

The naive idea doesn't work immediately. The solutions of $$ \min \Bigg\|\begin{pmatrix} A \\ I \end{pmatrix} x - \begin{pmatrix} b_0\\b_1 \end{pmatrix} \Bigg\|$$ and $$ \min \Bigg\|\begin{pmatrix} P^{-1}A \\ I \end{pmatrix} x - \begin{pmatrix} P^{-1}b_0\\b_1 \end{pmatrix} \Bigg\|$$ are different, in general (unless $P$ is orthogonal).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.