Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

3 Answers

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

share|improve this answer
add comment

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$

share|improve this answer
    
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. –  J. M. 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
add comment

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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