# 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 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 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 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 at 23:10
• Thanks, @AbdullahAliSivas! Aug 8 at 12:49

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