# Prove that the Least Squares solution is Orthogonal to the Kernel of A

The least squares problem tries to minimize $$||Ax - y ||^{2}$$ .

I'm trying to prove that $$x^{LS} \perp Ker(A)$$ where $$x^{LS} = A^{\dagger}y$$ and that $$x^{LS}$$ is the solution with the smallest $$L2$$ norm.

$$A^{\dagger}$$ is the Moore-Penrose pseudo-inverse of $$A$$, and can be written as $$A^{\dagger} = VE^{\dagger}U^{T}$$

To prove this I tried starting with the fact that showing that $$x^{LS} \perp Ker(A)$$ is the same as showing that $$x^{LS} \in Im(A^{T})$$.

My unfinished (probably wrong) proof using SVD:

Let $$z \in Im(A^{T})$$

\begin{align*} A^Tz & = A^{\dagger}y\\ (U\Sigma V^{T})^{T}z & = V \Sigma^{\dagger}U^{T}y \\ V \Sigma^{T}U^{T}z&= V \Sigma^{\dagger}U^{T}y \\\ V^{T} V \Sigma^{T}U^{T}z&= V^T V \Sigma^{\dagger}U^{T}y\\ \Sigma^{T}U^{T}z&= \Sigma^{\dagger}U^{T}y\\ \end{align*}

I get stuck here, while trying to prove that $$x^{LS} \in Im(A^{T})$$. To prove orthogonality, I could also see if the dot product of the two equates to $$0$$, but I got stuck there as well.

Could someone help me with this proof?

• Do you know how to get an orthogonal basis for the null space (kernel) of A from the SVD? Can you express $A^{\dagger}y$ in terms of columns of $V$ that are not in that basis for the null space of $A$? – Brian Borchers Nov 23 '19 at 1:41
• Could you provide a hint to how to get started with this? – AmateurMathlete Nov 23 '19 at 1:55
• You might find this post helpful as well – Ben Grossmann Nov 23 '19 at 6:26

Note that $$x$$ solves the least squares problem if and only if $$x \perp \ker(A)$$ and $$A^TAx = A^Ty$$.

Here's one way to see that $$A^\dagger y$$ is in $$\ker(A)^\perp = \operatorname{im}(A^T)$$. Suppose $$A = U\Sigma V^T$$. Let $$u_1,\dots,u_m$$ denote the columns of $$U$$, and let $$\sigma_1,\dots,\sigma_r$$ denote the non-zero diagonal entries of $$\Sigma$$.

First, note (or verify) that the vectors $$v_{r+1},\dots,v_m$$ form an orthonormal basis for $$\ker(A)$$. Let $$e_1,\dots,e_m$$ denote the columns of the identity matrix (i.e. the standard basis). We now note that for $$i = r+1,\dots,m$$, we have $$v_i^TA^\dagger y = (V e_i)^T V\Sigma^\dagger Uy = e_i^T(V^TV) \Sigma^\dagger Uy = (e_i^T\Sigma^\dagger)(Uy).$$ Verify that $$e_i^T \Sigma^\dagger$$ (the $$i$$th row of $$\Sigma^\dagger$$) is zero.

Now, to check that $$A^TAx = A^Ty$$. We have $$A^TA(A^\dagger y) = A^T(U\Sigma^T\Sigma V^T)(V \Sigma^\dagger U^T)y = A^T U(\Sigma^T\Sigma\Sigma^\dagger)U^T y \\ = A^T U \Sigma^\dagger U^Ty = (V \Sigma^T U^T)(U \Sigma^\dagger U^T) y = V(\Sigma^T \Sigma^\dagger)U^T y\\ = V \Sigma^T U^Ty = A^T y.$$

Here's a proof of those requirements. Note that a minimizer of $$\|Ax - y\|^2$$ will satisfy the equation $$A^TAx = A^Ty, \tag{1}$$ and note that $$\ker(A) = \ker(A^TA)$$. Now, we show that this equation has at least one solution satisfying $$x \perp \ker(A)$$. Given a solution $$x$$, let $$x_{\|}$$ denote the projection of $$x$$ onto $$\ker(A)$$, which is to say that $$x_{\|} \in \ker(A)$$ and $$(x - x_{\|}) \perp \ker(A)$$. We see that $$x^* = x - x_{\|}$$ must be another solution to Equation (1) since $$(A^TA)x^* = A^TA x - A^TA x_{\|} = A^Ty - A^T(Ax_{\|}) = A^Ty.$$

Now, suppose that $$x^*$$ is a solution satisfying $$x^* \perp \ker(A)$$. We can see that $$x^*$$ minimizes $$\|x\|$$ subject to the constraint that $$A^TAx = A^Ty$$ as follows:

Note that every solution to the (1) can be written as a particular solution (in this case, $$x^*$$) added to a "homogeneous solution" (in this case, any $$x_h \in \ker(A^TA)$$). In short, every $$x$$ satisfying the above equation has the form $$x^* + x_h$$ for some $$x_h \in \ker(A)$$. With that, it follows that $$\|x\|^2 = \|x^*\|^2 + \|x_h\|^2 \geq \|x^*\|^2.$$ So, $$x = x^*$$ indeed minimizes $$\|x\|$$.