2
$\begingroup$

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.

  • 0
    Is this question also supposed to assume that $Ax=\pmatrix{0\\1}$? Something else is needed, otherwise, $x=0$ is a trivial solution.2011-11-04

3 Answers 3

6

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:

Mathematica solution

2

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$

  • 0
    However, the answer you got, is the same answer that is gotten using the method I suggest below (good thing, too). :-)2011-11-04
0

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$.

  • 0
    Tha$n$ks so much for your help! I ra$n$ into the same problem you did, and its nice to have conformation that it isnt solvable. So thank you!2011-11-04