I saw this theorem on the lecture slides (http://www2.aueb.gr/users/douros/docs_master/Least_Square_pr.pdf) with topic Rank-Deficient Least Squares Problem

Given $A\in R^{m\times n}, m > n, \, r = \text{rank(A)}<n \, \text{and} \, b \in R^m$ and we want to find $x$ such that $\min_x \Vert Ax-b \Vert_2$, then there are n-r dimensional set of vectors x that minimize $\Vert Ax-b \Vert_2$

What's the reason behind the "$n-r$" theorem?

  • $\begingroup$ $n-r$ is the dimension of Nullity of $A$. $\endgroup$ – Yadati Kiran Nov 22 '18 at 3:47
  • $\begingroup$ @YadatiKiran Why is the least square solution in the nullity of A?? I thought it will be in the nullity of $A^T$ so it will have a dimension of m-r? $\endgroup$ – WeiShan Ng Nov 22 '18 at 4:50
  • $\begingroup$ Rank of $A^{T}$ is less than or equal to $n$ right since $m>n$? $\endgroup$ – Yadati Kiran Nov 22 '18 at 4:55

I think I get it now....Given a matrix $A \in R^{m\times n}, \, m>n$ and $b \in R^m$, if we want to find a least square solution $\mathbf{\hat{x}}$ for the system $A\vec{x} = \vec{b}$, we are actually trying to solve the normal equation $$A^T A \vec{x} = A^T \vec{b}$$
And we also know that

$R(A^T)=R(A) = R(A^T A)$ and $N(A) = N(A^T A)$

So if the A is rank deficient, $r < n$ then the $nullity(A^T A)= n-r$, which means the the solution space of $A^T A \vec{v}=0$ is non-trivial and of $n-r$ dimension. We will now have infinity solution for the normal equation $A^T A \vec{x} = A^T \vec{b}$

Let $\vec{v} \in N(A^T A)$, then $$\vec{v} = \sum_{i=1}^{n-r} \alpha_i \mathbf{n_i} $$ where $N(A^T A) = span \{\mathbf{n_1, \cdots , n_{n-r}\}}$

And let $\vec{w} \in R(A^T A)$. So the least square solution can now be written as $$\mathbf{\hat{x}} = \vec{w} + \alpha_1 \mathbf{n_1} + \cdots + \alpha_{n-r} \mathbf{n_{n-r}}$$
which is of $n-r$ dimension


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.