# How do you solve a least square problem with a noninvertible matrix?

How do you find a solution to a matrix $A$ that minimizes $\|x\|$ when $A^TA$ is not invertible? The matrix is $$A = \pmatrix{1 &1&2&2\\1&2&3&4}$$

I don't know if this helps but also in the question above this one, we are asked to find all solutions to $Ax = \pmatrix{0\\11}$

Thank you.

-
The number of elements in row 1 and row 2 of A are not the same. There is a typo either in the first or the second row. –  tards Nov 4 '11 at 14:29
sorry the second row is comprised of [1 2 3 4] without the 0 –  Confused Nov 4 '11 at 14:32
Is this question also supposed to assume that $Ax=\pmatrix{0\\1}$? Something else is needed, otherwise, $x=0$ is a trivial solution. –  robjohn Nov 4 '11 at 19:32

As others have assumed, I am assuming that this problem is linked to the previous one and that we are looking to minimize $\|x\|$ where $Ax=\pmatrix{0\\11}$ and $A = \pmatrix{1&1&2&2\\1&2&3&4}$. To minimize $\|x\|$, we can minimize $\|x\|^2=x^Tx$. To minimize $x^Tx$ over all $x$ so that $Ax=\pmatrix{0\\11}$, $x^T$ must be in the row space of $A$.

Suppose $AA^Tu=\pmatrix{0\\11}$. Then, it is simple to show that $\|A^Tu-x\|^2=\|x\|^2-u^T\pmatrix{0\\11}$, and from there, it is easy to show that $x=A^Tu$ minimizes $\|x\|$.

If $AA^T$ is invertible, then you can find such a $u$.

Pseudoinverses:

It should be mentioned that when $AA^T$ is invertible, $A^T(AA^T)^{-1}$ is called the Moore-Penrose Pseudoinverse, or simply the pseudoinverse.

Mathematica:

-

In practice, one uses the singular value decomposition, $\mathbf A=\mathbf U\mathbf \Sigma\mathbf V^\top$ for solving underdetermined problems like these. Taking the SVD approach assumes that you are optimizing with respect to the Euclidean norm, $\|\cdot\|_2$. (If you need to optimize with respect to the 1-norm or max-norm, linear programming methods are required, but I won't get into those.)

For this particular example, we have the decomposition

\begin{align*} \mathbf U&=\begin{pmatrix} 0.4964775289157638 & -0.8680495742074279 \\ 0.8680495742074279 & 0.4964775289157638 \end{pmatrix} \\ \mathbf \Sigma&=\begin{pmatrix} 6.302625081925469 & 0 \\ 0 & 0.5262291104490325 \end{pmatrix} \\ \mathbf V&=\begin{pmatrix} 0.2165013919416455 & -0.7061031742896186 \\ 0.3542296500759905 & 0.2373595096582885 \\ 0.5707310420176360 & -0.4687436646313301 \\ 0.7084593001519810 & 0.4747190193165770 \end{pmatrix} \end{align*}

Computing the least-squares solution $\min\|\mathbf A\mathbf x-\mathbf b\|_2$ is a matter of computing $\mathbf x=\mathbf V\mathbf \Sigma^{-1}\mathbf U^\top\mathbf b$; for the particular case of $\mathbf b=(0\quad 11)^\top$, we obtain the solution $$\mathbf x=\pmatrix{-7\\3\\-4\\6}$$ There are other solutions, like $\mathbf x=(0\quad 0\quad -11\quad 11)^\top$. All take the form $\mathbf x=\left(a\quad b\quad -11-a\quad 11+\frac{a-b}{2}\right)^\top$

-
It seems to me that SVD is a bit overkill. –  robjohn Nov 4 '11 at 17:41
In practice, @rob. :) It does look as if a different route is expected of them here, seeing it's a classroom problem. –  Guess who it is. Nov 4 '11 at 17:53
However, the answer you got, is the same answer that is gotten using the method I suggest below (good thing, too). :-) –  robjohn Nov 4 '11 at 18:33

I suppose that you are looking to find the value of $x$ for which $(Ax−b)^\intercal(Ax−b)$ attains the minimum. As you said this problem cannot be solved as $A$ is noninvertible and I cannot see how there can be a unique solution unless we impose additional constraints on $x$.

-
Yes i found a solution to the second part of the question. But the first part is asking you to find the minimum value of x that satisfies Ax=b. Usually we used the formula x*=(ATA)-1 ATb but in this case since ATA is not invertible it doesn't work. So I attempted to use the formula for projections but I am not confident that that worked, or that it is right. The formula I used to try to solve was xp - (u1(dot)xp)u1 - (u2(dot)xp)u2 where u1 and u2 are the orthanormal basis of the kernel and xp is the xparticular we found by setting Ax=b and solving. –  Confused Nov 4 '11 at 14:51
@confused what would a 'minimum' value mean for a vector valued variable $x$? Are there any other constraints on $x$? If there are no other constraints in $x$ apart from $Ax=b$ then I do not see how the problem can be solved. –  tards Nov 4 '11 at 14:59
We are looking for a minimum of the vector x which I believe would include x1 x2 x3 and x4. And by minimum I think it is the least square minimum...the smallest distance of the vector. Does that make any sense? –  Confused Nov 4 '11 at 15:03
@Confused You are not looking for a minimum $x$. Rather, you are looking to find the value of $x$ for which $(Ax-b)^\intercal (Ax-b)$ attains the minimum. As you said this problem cannot be solved as $A$ is noninvertible and I cannot see how there can be a unique solution unless we impose additional constraints on $x$. –  tards Nov 4 '11 at 15:09
Thanks so much for your help! I ran into the same problem you did, and its nice to have conformation that it isnt solvable. So thank you! –  Confused Nov 4 '11 at 15:11