# Preconditioning a least-squares problem?

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?

• 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. Aug 7, 2021 at 18:46
• 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$? Aug 7, 2021 at 21:29
• @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. Aug 7, 2021 at 21:32
• @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. Aug 7, 2021 at 23:10
• @AbdullahAliSivas How is the solution of the preconditioned problem the same as the original problem? See Federico's reply. Aug 8, 2021 at 13:04

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).