This notebook derives the ordinary least squares (OLS) solution $\\hat{x} = (A^\\top A)^{-1} A^\\top b$ from first principles using matrix algebra.<\/p>\n\n\n\n
We want to solve the linear system:<\/p>\n\n\n\n
$$A x = b$$ <\/p>\n\n\n\n
where: <\/p>\n\n\n\n
$A \\in \\mathbb{R}^{m \\times n}$ is a known matrix (typically $m > n$, more equations than unknowns)<\/p>\n\n\n\n
$x \\in \\mathbb{R}^n$ is the unknown vector we want to find<\/p>\n\n\n\n
$b \\in \\mathbb{R}^m$ is a known vector<\/p>\n\n\n\n
When $m > n$, this system is overdetermined<\/strong> \u2014 there are more constraints than degrees of freedom, so an exact solution generally does not exist. Instead, we seek the $\\hat{x}$ that comes closest to satisfying all equations simultaneously.<\/p>\n\n\n\n For any candidate solution $x$, define the residual<\/strong>: This vector measures how far $Ax$ is from $b$. We want to minimize the sum of squared residuals<\/strong>, i.e., the squared Euclidean norm of $r$:<\/p>\n\n\n\n $$\\min_{x} \\; |r|^2 = \\min_{x} \\; |b – Ax|^2$$<\/p>\n\n\n\n Expanding using the inner product definition $|v|^2 = v^\\top v$:<\/p>\n\n\n\n $$|b – Ax|^2 = (b – Ax)^\\top (b – Ax)$$<\/p>\n\n\n\n Expand $(b – Ax)^\\top(b – Ax)$:<\/p>\n\n\n\n $$ Since $b^\\top A x$ is a scalar, it equals its own transpose: So the two middle terms are equal, and we can write:<\/p>\n\n\n\n $$\\boxed{|b – Ax|^2 = b^\\top b – 2x^\\top A^\\top b + x^\\top A^\\top A x}$$<\/p>\n\n\n\n Call this objective function $f(x)$. It is a quadratic function<\/strong> of $x$, and since $A^\\top A$ is positive semi-definite, $f(x)$ is convex \u2014 any local minimum is a global minimum.<\/p>\n\n\n\n To minimize $f(x)$, we take the gradient with respect to $x$ and set it to zero.<\/p>\n\n\n\n Using standard matrix calculus identities:<\/p>\n\n\n\n Note that $A^\\top A$ is symmetric by construction: $(A^\\top A)^\\top = A^\\top A$.<\/p>\n\n\n\n Applying these identities to $f(x)$:<\/p>\n\n\n\n $$\\nabla_x f(x) = 0 – 2A^\\top b + 2A^\\top A x$$<\/p>\n\n\n\n Setting $\\nabla_x f(x) = 0$:<\/p>\n\n\n\n $$2A^\\top A x – 2A^\\top b = 0$$<\/p>\n\n\n\n $$A^\\top A x = A^\\top b$$<\/p>\n\n\n\n These are called the Normal Equations<\/strong>.<\/p>\n\n\n\n $$A^\\top A \\hat{x} = A^\\top b$$<\/p>\n\n\n\n Geometric interpretation:<\/strong> The normal equations enforce that the residual $r = b – A\\hat{x}$ is orthogonal to every column of $A$:<\/p>\n\n\n\n $$A^\\top (b – A\\hat{x}) = 0 \\iff A^\\top r = 0$$<\/p>\n\n\n\n In other words, $\\hat{x}$ is the solution for which $A\\hat{x}$ is the orthogonal projection<\/strong> of $b$ onto the column space of $A$. The residual points in a direction that $A$ cannot represent \u2014 it is orthogonal to $\\text{col}(A)$.<\/p>\n\n\n\n If $A$ has full column rank<\/strong> (rank $= n$), then $A^\\top A$ is symmetric positive definite and therefore invertible. We can solve the normal equations directly:<\/p>\n\n\n\n $$\\hat{x} = (A^\\top A)^{-1} A^\\top b$$<\/p>\n\n\n\n This is the Ordinary Least Squares (OLS) estimator<\/strong>.<\/p>\n\n\n\n The matrix $A^\\dagger = (A^\\top A)^{-1} A^\\top$ is called the Moore-Penrose pseudoinverse<\/strong> of $A$ (in the full column rank case).<\/p>\n\n\n\n The fitted values $\\hat{b} = A\\hat{x}$ are the projection of $b$ onto $\\text{col}(A)$:<\/p>\n\n\n\n $$\\hat{b} = A(A^\\top A)^{-1} A^\\top b = P b$$<\/p>\n\n\n\n where $P = A(A^\\top A)^{-1} A^\\top$ is the orthogonal projection matrix<\/strong> (also called the hat matrix).<\/p>\n\n\n\n $P$ has two key properties that confirm it is a valid orthogonal projector:<\/p>\n\n\n\n Verification of idempotency:<\/strong> The Hessian of $f(x)$ with respect to $x$ is:<\/p>\n\n\n\n $$H = \\nabla^2_x f(x) = 2A^\\top A$$<\/p>\n\n\n\n For any nonzero vector $v$: So $A^\\top A$ is positive semi-definite, and strictly positive definite when $A$ has full column rank (since $Av = 0 \\Rightarrow v = 0$). Therefore $H \\succ 0$, confirming that the stationary point $\\hat{x}$ is a strict global minimum.<\/p>\n\n\n\n The full column rank condition on $A$ is the precise requirement that makes the least squares solution unique \u2014 consistent with the earlier discussion of full rank implications.<\/p>\n","protected":false},"excerpt":{"rendered":" This notebook derives the ordinary least squares (OLS) solution $\\hat{x} = (A^\\top A)^{-1} A^\\top b$ from first principles using matrix algebra. 1. Problem Setup We want to solve […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16,25],"tags":[24],"class_list":["post-979","post","type-post","status-publish","format-standard","hentry","category-base","category-in-english","tag-machine-learning"],"_links":{"self":[{"href":"https:\/\/tensorzen.online\/index.php?rest_route=\/wp\/v2\/posts\/979","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tensorzen.online\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tensorzen.online\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tensorzen.online\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tensorzen.online\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=979"}],"version-history":[{"count":7,"href":"https:\/\/tensorzen.online\/index.php?rest_route=\/wp\/v2\/posts\/979\/revisions"}],"predecessor-version":[{"id":987,"href":"https:\/\/tensorzen.online\/index.php?rest_route=\/wp\/v2\/posts\/979\/revisions\/987"}],"wp:attachment":[{"href":"https:\/\/tensorzen.online\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=979"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tensorzen.online\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=979"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tensorzen.online\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=979"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}2. Defining the Residual<\/h2>\n\n\n\n
$$r = b – Ax$$<\/p>\n\n\n\n3. Expanding the Objective<\/h2>\n\n\n\n
|b – Ax|^2 = b^\\top b – b^\\top A x – x^\\top A^\\top b + x^\\top A^\\top A x
$$<\/p>\n\n\n\n
$$b^\\top A x = (b^\\top A x)^\\top = x^\\top A^\\top b$$<\/p>\n\n\n\n4. Taking the Gradient<\/h2>\n\n\n\n
\n
5. The Normal Equations<\/h2>\n\n\n\n
6. Solving for $\\hat{x}$<\/h2>\n\n\n\n
7. The Projection Matrix<\/h2>\n\n\n\n
Property<\/th> Statement<\/th> Meaning<\/th><\/tr><\/thead> Idempotent<\/td> $P^2 = P$<\/td> Projecting twice is the same as projecting once<\/td><\/tr> Symmetric<\/td> $P^\\top = P$<\/td> Projection is orthogonal (not oblique)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
$$P^2 = A(A^\\top A)^{-1} A^\\top \\cdot A(A^\\top A)^{-1} A^\\top = A(A^\\top A)^{-1} (A^\\top A)(A^\\top A)^{-1} A^\\top = A(A^\\top A)^{-1} A^\\top = P \\checkmark$$<\/p>\n\n\n\n8. Confirming the Minimum (Second-Order Condition)<\/h2>\n\n\n\n
$$v^\\top (A^\\top A) v = (Av)^\\top (Av) = |Av|^2 \\geq 0$$<\/p>\n\n\n\nSummary<\/h2>\n\n\n\n
Step<\/th> Key result<\/th><\/tr><\/thead> Objective<\/td> Minimize $|b – Ax|^2$<\/td><\/tr> Expand<\/td> $f(x) = b^\\top b – 2x^\\top A^\\top b + x^\\top A^\\top A x$<\/td><\/tr> Gradient<\/td> $\\nabla_x f = 2A^\\top A x – 2A^\\top b$<\/td><\/tr> Normal equations<\/td> $A^\\top A \\hat{x} = A^\\top b$<\/td><\/tr> OLS solution<\/td> $\\hat{x} = (A^\\top A)^{-1} A^\\top b$ (when $A$ is full column rank)<\/td><\/tr> Geometric meaning<\/td> $A\\hat{x}$ is the orthogonal projection of $b$ onto $\\text{col}(A)$<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n