I have an application where I have to minimize a cost function of the form:
$J(\mathbf x) = \| \mathbf A \mathbf x - \mathbf b \|^2 \quad (1)$
By calculating the gradient, I derived that I have to solve the system of equations:
$\mathbf A^T \mathbf A \mathbf x = \mathbf A^T \mathbf b \quad (2)$
Now my question is, when can I solve the following system instead?
$\mathbf A \mathbf x = \mathbf b \quad (3)$
From my point of view, this depends on $\mathbf A$ to be invertible. In my application $\mathbf A$ is a square matrix of the form $\mathbf A = \mathbf I - \mathbf W$ where $\mathbf I$ is the identity matrix and $\mathbf W$ is a square matrix with zeros on the main diagonal and small values on a few secondary diagonals. The values of $\mathbf W$ are arbitrary but normalized, so that each row of $\mathbf W$ sums to 1. However, some lines of $\mathbf W$ can also be zero.
For example $\mathbf A$ may look like this:
$\mathbf A = \pmatrix{ 1 & -0.2 & 0 & 0 & -0.3 & -0.2 & -0.3 & 0 & 0 \cr -0.1 & 1 & -0.2 & 0 & 0 & -0.4 & -0.2 & -0.1 & 0 \cr 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \cr 0 & 0 & -0.2 & 1 & -0.1 & 0 & 0 & -0.6 & -0.1 \cr -0.2 & 0 & 0 & -0.2 & 1 & -0.5 & 0 & 0 & -0.1 \cr -0.4 & -0.3 & 0 & 0 & -0.1 & 1 & -0.2 & 0 & 0 \cr -0.1 & -0.1 & -0.1 & 0 & 0 & -0.6 & 1 & -0.1 & 0 \cr 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \cr 0 & 0 & -0.2 & -0.4 & -0.1 & 0 & 0 & -0.3 & 1 \cr }$
Have I argued correctly? Then how can I show that $\mathbf A$ is invertible? Or is there any other argument for solving (3) instead of (2)?
I tried to solve both systems (2) and (3) with MATLAB and the Intel MKL, but surprisingly only (3) gave me the expected result. I would expect that it also works with (2). Maybe a numerical problem?