Chain rule for a least-square regression, where does the transpose come from? I am reading a machine learning book, and I can't understand a couple of things from the following explanation:

Suppose we want to ﬁnd the value of $x$ that minimizes
$$f(x) = \frac{1}{2} \left \| Ax - b \right \|^2_2$$
There are specialized linear algebra algorithms that can solve this problem eﬃciently. However, we can also explore how to solve it using gradient-based optimization as a simple example of how these techniques work. First, we need to obtain the gradient:
$$\triangledown_xf(x) = A^{T}(Ax-b)$$
...

Am I correct with my understanding that by "specialized linear algebra algorithms" they mean finding inverse (or pseudoinverse) and calculating $A^{-1}b$.
But my main question is why do they have $A^{T}$ in the derivative? As far as I understood they apply chain rule, but I still can't understand where the transpose comes from.
 A: First question:
yes, if you were to implement the pseudo inverse of $A$ and multiply it to $b$ then you would get a similar answer but probably less accurate and probably in more time too. 
Typically software will exploit the properties of $A$ as much as possible to come up with an accurate answer quickly . 
As a side note (but it's probably for another question) often the complete inverse or pseudo-inverse is not formed, rather $A^{-1}b$ is computed directly (as a vector, not as a matrix multiplied by a vector). For more about this, you may be interested in looking up LINPACK / LAPACK. Also a slightly humorous reference: http://www.johndcook.com/blog/2010/01/19/dont-invert-that-matrix/
Second question:
If you write $\langle a,b\rangle$ the inner product of $a$ and $b$ i.e., $\sum_i a_i b_i$ then
$$ \| Ax-b\|^2 = \langle Ax-b, Ax-b\rangle$$
there are standard formulas for differentiating inner products but here the easiest is probably to look entry-wise what happens:
$$ \|Ax-b\|^2 = \sum_i (Ax-b)_i^2  $$
by linearity of the gradient, you have
$$ \nabla  \|Ax-b\|^2 = 2\sum_i (Ax-b)_i (\nabla(Ax-b)_i  )$$
now the $k$th element of the term in the right hand side is
$$ [\nabla(Ax-b)_i]_k = {\partial\over\partial x_k} \sum_j (A_{ij}x_j -b_i) = A_{ik}$$
indeed the derivative of all the terms will be zero apart from when the term is $j=k$. 
plugging that back, you now have an explicit expression for the $k$th element of the gradient of the function of interest:
$$ (\nabla  \|Ax-b\|^2)_k = 2\sum_i (Ax-b)_i A_{ik}$$
rearranging this can be written (transposing and swapping indices of a matrix is the same thing)
$$ (\nabla  \|Ax-b\|^2)_k = 2\sum_i A^T_{ki} (Ax-b)_i $$
and the right hand side is now simply $2(A^T(Ax-b))_k$. 
Considering the original form was $\frac{1}{2}||Ax-b||^2_2$ we an see that $\Delta_xf(x) = A^T(Ax-b)$
