Consider the following Least Square Minimization problem:$min_{x \in \mathbb C^3} |x_1 +x_3-3|^2+|x_2 -x_3|^2+|x_1+x_3-4|^2$ Find the pseudo-inverse of the matrix $A=\begin{bmatrix} 1 & 0 & 1 \\ 0 & 1 & -1 \\ 1 & 0 & 1 \end{bmatrix}$ without computing singular values of $A$.
It seems we cannot use normal equations to denote $A^{+}=(A^{T}A)^{-1}A^{T}$ since $A^{T}A^{-1}$ is not invertible. Any hints would be appreciated.
On
There are several methods to calculate $A^+$ without calculating singular values. Here are two of them.
Method 1.
Use the formula $A^+=\lim_{t\to0}A^T(AA^T+tI)^{-1}$. In your case, you should get something like \begin{align*} A^+&=\lim_{t\to0}A^T(AA^T+tI)^{-1}\\ &=\lim_{t\to0}\pmatrix{1&0&1\\ 0&1&0\\ 1&-1&1}\pmatrix{t+2&-1&2\\ -1&t+2&-1\\ 2&-1&t+2}^{-1}\\ &=\lim_{t\to0}\frac1{t^2+6t+6} \pmatrix{t+2&2&t+2\\ 1&t+4&1\\ t+1&-t-2&t+1}\\ &=\frac16\pmatrix{2&2&2\\ 1&4&1\\ 1&-2&1}. \end{align*}
Use the property that if $X$ has orthonormal columns or $Y$ has orthonormal rows, then $(XY)^+=Y^+X^+$. Decompose $A$ as the product $\pmatrix{1&0\\ 0&1\\ 1&0}\pmatrix{1&0&1\\ 0&1&-1}$. Gram-Schmidt orthogonalisation gives \begin{align*} A &=\left[ \pmatrix{\frac1{\sqrt{2}}&0\\ 0&1\\ \frac1{\sqrt{2}}&0} \pmatrix{\sqrt{2}\\ &1} \right] \left[ \pmatrix{\sqrt{2}&0\\ -\frac1{\sqrt{2}}&\sqrt{\frac32}} \pmatrix{\frac1{\sqrt{2}}&0&\frac1{\sqrt{2}}\\ \frac1{\sqrt{6}}&\sqrt{\frac23}&-\frac1{\sqrt{6}}} \right]\\ &=\underbrace{\pmatrix{\frac1{\sqrt{2}}&0\\ 0&1\\ \frac1{\sqrt{2}}&0}}_{X} \underbrace{\pmatrix{2&0\\ -\frac1{\sqrt{2}}&\sqrt{\frac32}}}_{Y} \underbrace{\pmatrix{\frac1{\sqrt{2}}&0&\frac1{\sqrt{2}}\\ \frac1{\sqrt{6}}&\sqrt{\frac23}&-\frac1{\sqrt{6}}}}_{Z}. \end{align*} Since $X$ has orthonormal columns, $Y$ is invertible and $Z$ has orthonormal rows, we have $$ A^+=(XYZ)^+=Z^+Y^+X^+=Z^TY^{-1}X^T. $$
$$ \mathbf{A}^{\dagger} = \frac{1}{6} \left[ \begin{array}{rrr} 2 & -2 & 2 \\ 1 & -4 & 1 \\ 1 & 2 & 1 \\ \end{array} \right] $$