Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$
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$.
