0
$\begingroup$

I've seen the preconditioned least squares objective function $\arg\min_{x}\Vert P^{-1}Ax-P^{-1}b\Vert_2$, where $P^{-1}$ is positive definite. However, I'm not sure how we show that this is the equivalent to the original $\arg\min_x \Vert Ax-b\Vert_2$. My attempt is that if $\sigma$ is the smallest eigenvalue of $P^{-1}$, then \begin{align} \sigma\Vert Ax-b\Vert_2 \leq \Vert P^{-1}Ax-P^{-1}b\Vert_2 \leq \Vert P^{-1}\Vert \Vert Ax-b\Vert_2 \end{align} and noting that $\arg\min_x \sigma \Vert Ax-b\Vert_2=\arg\min_x \Vert P^{-1}\Vert \Vert Ax-b\Vert_2$, we have \begin{align} \arg\min_x \Vert Ax-b\Vert&=\arg\min_{x}\Vert P^{-1}Ax-P^{-1}b\Vert_2 \end{align} but I'm not sure that this argument is correct.

$\endgroup$

1 Answer 1

1
$\begingroup$

This problem is not equivalent to the original one, essentially now you are minimizing with respect to another inner product, the one given by $\langle x , y\rangle := xP^{-T}P^{-1}y$. Up to an orthogonal transformation this is a weighted least squares for some weights $w_1,\dots, w_n$, hence this is not equivalent to the original minimization (no weights).

$\endgroup$
1
  • $\begingroup$ Thanks. I was wondering about this, but I see from p 312 of www-users.cs.umn.edu/~saad/PS/iter3.pdf that they use the normal equations derived via the objective function I mentioned, and here math.stackexchange.com/questions/2971189/… they mentioned the same objective function. Is there some assumption from each of them I'm missing? I actually implemented the first one and it gives the same results as solving for least squares. $\endgroup$
    – mlstudent
    Apr 19, 2020 at 20:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .