Derivation of Least Square

April 21, 2022

Least square problem solve the following equation:

$$ argmin_x |Ax-y|_2^2 $$

It can be solve in closed-form by the following equation:

$$ \hat{x} = (A^TA)^{-1}A^Ty $$

Derivation #

The objective can be unfolded via:

$$ |Ax-y|_2^2 = (Ax-y)^T(Ax-y) = x^TA^TAx - x^TA^Ty -y^TAx +y^Ty $$

Take the derivative of the objective with respect to x, we have:

$$ \frac{\partial |Ax-y|_2^2}{\partial x} = 2A^TAx - 2A^Ty $$

The minimum can be founded through setting the derivative to zero, then we have:

$$ A^TAx - A^Ty = 0 \Rightarrow A^TAx = A^Ty $$

$$ x = (A^TA)^{-1}A^Ty $$

\

The derviation of the above derivatives relies on the following equations:

$$ \frac{\partial x^Tb}{\partial x} = \frac{\partial b^Tx}{\partial x} = b $$ This is obvious by looking at the scalar form of $x^Tb$.

$$ \frac{\partial x^TAx}{\partial x} = (A+A^T)x $$

The detailed derivation of this equality can be founded in stackexchange.