# Generalizing the conjugate gradient like this works?

Given $$A \in \mathbb{R}^{n \times n}$$, a SPD matrix, and a vector $$b \in \mathbb{R}^n$$, it is possible to solve the problem $$\min_x \| Ax - b\|$$
with the conjugate gradient method. Its algorithm basically is

$$r_0 = b - Ax_0\\ p_0 = r_0\\ k = 0\\ \text{while } r_k \text{ is not small enough}\\ \ \ \ \ \ \ \alpha_k = \displaystyle \frac{ \|r_k\|^2 }{\langle p_k, Ap_k \rangle}\\ \ \ \ \ \ \ x_{k+1} = x_k + \alpha_k p_k\\ \ \ \ \ \ \ r_{k+1} = r_k - \alpha_k Ap_k\\ \ \ \ \ \ \ \beta_k = \frac{ \| r_{k+1} \|^2}{ \| r_k \|^2 }\\ \ \ \ \ \ \ p_{k+1} = r_{k+1} + \beta_k p_k\\ \ \ \ \ \ \ k = k+1\\ \text{end while}\\ \text{return } x_{k+1}$$

I wonder what happens if I used the same algorithm for a function like $$f(x) = Ax + r(x)$$, where $$r(x)$$ usually is much smaller then $$f(x)$$ (in the norm sense). To be more precise, I use the same algorithm but changing the formulas for $$\alpha_k$$ and $$r_{k+1}$$ by

$$\alpha_k = \displaystyle \frac{ \|r_k\|^2 }{\langle p_k, f(p_k) \rangle},\\ r_{k+1} = r_k - \alpha_k f(p_k).$$

Is the conjugate gradient method flexible at the point I can do this? What condition I need on $$r$$ to make it work? One possibility is $$r$$ being a SPD matrix, but this is an obvious one.

Unlikely without special assumptions placed on $$f$$. The CG algorithm requires $$x^T A x \not = 0$$ to avoid division by zero. If $$A$$ is symmetric positive definite and if $$v$$ is an unit eigenvector of $$A$$ corresponding to the eigenvalue $$\lambda$$, then $$B = A - \lambda vv^T$$ is a symmetric positive semi-definite matrix. In particular, $$v^T B v = 0$$. If $$\lambda$$ is the smallest eigenvalue of $$A$$, then many would consider $$f(x) = Bx$$ to be only a small perturbation of the original map, especially if the largest eigenvalue of $$A$$ is much larger than $$\lambda$$.
• Ok, $B$ is a small perturbation o the original map and has the problem of $v^T B v$ vanishing, where $v$ is the eigenvector associated to the smallest eigenvalue of $A$. It means that the algorithm crashes in a certain subspace. Since this subspace has null measure, I think you would agree that there is zero probability of observe crashing. Regardless, what happens when the algorithm doesn't touch this subspace? Is it going to converge? – Integral Aug 22 at 16:38