Least squares solutions of matrices with redundant columns?

Question

There was a similar question here, but I either did not understand the answers or the answers were too general. I am wondering specifically how to find the solutions. For example, what are the least squares solutions of

$$ \begin{pmatrix} 1 & 2\\ 2 & 4\\ -2 & -4\\ \end{pmatrix} \vec{x}= \begin{pmatrix} 3 \\ -4\\ 2\\ \end{pmatrix}. $$

When I attempt to solving using $A^TA\vec{x}=A^T\vec{b}$, I got that $det(A^TA)=0$, and thus it is noninvertible. I ran into similar problems attempting to use $A\vec{x}=proj_{Col A}\vec{b}$.

Answer 1

I would have explained the case in the following way:

Let $\vec{x}=(x \ y )^T$.

For your matrix equation we have three linear equations:

$x+2y=3$
$2x+4y=-4$
$-2x-4y=2$

which can be transformed into three similarly looking equations

$x+2y=3$
$x+2y=-2$
$x+2y=-1$

So we have in fact three equations of parallel straight lines crossing $Ox$ axis at different points.

There is no sense to ask what is the most appropriate single vector $(x,y)^T$ to be the closest to satisfy this system of equations.

What we can ask instead of it:

• what could be the most appropriate equation of the line $x+2y=a$ "representing" this system.

We can for example take crossings of the lines with $Ox$ axis ( when $y=0$) and calculate from them the mean crossing - from this method we obtain $a=0$.

Finally $\vec{x}$ can be parametrized with parameter $y$.

$\vec{x}=(-2y \ \ y )^T$

Answer 2

More generally, let $n>m$, $A\in M_{n,m},b\in\mathbb{R}^n$, $f:x\in\mathbb{R^m}\rightarrow ||Ax-b||^2$.

We seek $\min_x(f(x))$; since $f$ is convex, the $\min$ of $f$ is reached in any $x$ s.t. $\nabla(f)(x)=0$, that is, in any $x$ s.t. $A^TAx=A^Tb$. Note that, if $rank(A)<m$, then $x$ is not unique.

Such a $x$ is for example $x=(A^TA)^+A^Tb$ and $\min(f)=||AA^+b-b||^2$ where $U^+$ is the Moore-Penrose inverse of $U$.cf.

https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse

Answer 3

In general, you can take a matrix $A$ and form the SVD

$$ Ax =b \tag{1}$$

$$ U \Sigma V^{T} x = b \tag{2} $$ $$ x \approx V \Sigma^{\dagger} U^{T} b \tag{3}$$

I've written about this here. , if you need to do it out by hand that is longer.