Help with "Smallest Euclidean Norm problem".

Question

I'm trying to find the smallest euclidian norm of the general solution of an algebraic equation $Ax=y,$ where $A$ is an $n\times m$ matrix and the gral solution is:

$x=x_{p}+\alpha_{1}n_{1}+\alpha_{2}n_{2}=\begin{pmatrix} 0\\ -4\\ 0\\ 0 \end{pmatrix}+\alpha_{1}\begin{pmatrix} 1\\ 1\\ -1\\ 0 \end{pmatrix}+\alpha_{2}\begin{pmatrix} 0\\ 2\\ 0\\ -1 \end{pmatrix}$

So, $x$ is undetermined, $\alpha_{1}, \alpha_{2}$ can be any real number and $n_{1},n_{2}$ are null vectors of A.

My first approcah is the following:

$x=\begin{pmatrix} \alpha_{1}\\ -4+\alpha_{1}+2\alpha_{2}\\ -\alpha_{1}\\ -\alpha_{2} \end{pmatrix}$

and since $\left\lVert x \right\lVert_{2}=\sqrt{x^{T}x}\Rightarrow\left\lVert x \right\lVert^{2}_{2}=x^{T}x$, thus

$\left\lVert x \right\lVert^{2}_{2}=3\alpha^{2}_{1}+5\alpha^{2}_{2}-8\alpha_{1}-16\alpha_{2}+4\alpha_{1}\alpha_{2}+16$

And I know from the definition of a norm that

1. $\left\lVert x \right\lVert\geq 0$

2. $\left\lVert x_{1}+x_{2} \right\lVert\leq \left\lVert x_{1} \right\lVert+\left\lVert x_{2} \right\lVert$

So, if these contitions hold for $\left\lVert x \right\lVert$ then it should hold for $\left\lVert x \right\lVert^{2}$, but from here I'm not sure how to proceed, you guys have any advice?

update: I tried the Least-norm solution $x_{ln}=A^{T}(AA^{T})^{-1}y$, the issue here is that my matrix A is singular, since $det(A)=0$ and not invetible since $rank(A) \neq n$.

Answer 1

setting the gradient to the zero vector gives system $$ 6 \alpha_1 + 4 \alpha_2 = 8 \; , $$ $$ 4 \alpha_1 + 10 \alpha_2 = 16 \; . $$ Or augmented matrix $$ \left( \begin{array}{cc|c} 6 & 4 & 8 \\ 4 & 10 & 16 \end{array} \right) $$

$$ \left( \begin{array}{cc|c} 3 & 2 & 4 \\ 2 & 5 & 8 \end{array} \right) $$

$$ \left( \begin{array}{cc|c} 1 & -3 & -4 \\ 2 & 5 & 8 \end{array} \right) $$

$$ \left( \begin{array}{cc|c} 1 & -3 & -4 \\ 0 & 11 & 16 \end{array} \right) $$

$$ \left( \begin{array}{cc|c} 1 & -3 & -4 \\ 0 & 1 & \frac{16}{11} \end{array} \right) $$

$$ \left( \begin{array}{cc|c} 1 & 0 & \frac{4}{11} \\ 0 & 1 & \frac{16}{11} \end{array} \right) $$

Answer 2

For the least squares problem $\min_x \|Ax-y\|_2$ the optimal solution is $x=A^+ y$ where $A^+$ is the Moore Penrose pseudo inverse of the matrix $A$. Note that if $AA^T$ is invertible, then $A^+ = A^(AA^)^{-1}$, and if $(A^ A)$ is invertible then $A^+ = (A^ A)^{-1} A^$. However the pseudo inverse exists even when neither of them is invertible. It can be computed via the Singular Value Decomposition (SVD): If

$$ A = U\Sigma V^T = \begin{bmatrix}U_1 &U_2\end{bmatrix} \begin{bmatrix}D & 0 \\ 0&0\end{bmatrix} \begin{bmatrix}V_1^\\ V_2^\end{bmatrix} \qquad D= \left[\begin{smallmatrix}\sigma_1&&\\&\ddots&\\&&\sigma_r\end{smallmatrix}\right] $$

is a SVD of $A$, i.e. $U$, $V$ are orthonormal such that

• $U$ orthonormal, $\operatorname{Im}(A) = \operatorname{Im}(U_1) = \mathcal U_1$, $\operatorname{Im}(U_2) = \mathcal U_2 = \mathcal U_1^\perp$
• $V$ orthonomral, $\ker(A) = \operatorname{Im}(V_2) = \mathcal V_2$, $\operatorname{Im}(V_1) = \mathcal V_1 = \mathcal V_2^\perp$
• $D=\operatorname{diag}(\sigma_1,\ldots,\sigma_r)$ with $\sigma_i>0$ is the diagonal matrix containing the singular values

The pseudoinverse is then given as

$$ A^+ = V\Sigma^+ U^T = \begin{bmatrix}V_1 & V_2\end{bmatrix} \begin{bmatrix}D^+ & 0 \\ 0&0\end{bmatrix} \begin{bmatrix}U_1^\\ U_2^\end{bmatrix} \qquad D= \left[\begin{smallmatrix}1/\sigma_1&&\\&\ddots&\\&&1/\sigma_r\end{smallmatrix}\right] $$

i.e. $\Sigma^+$ is obtained by transposing $\Sigma$ and inverting all singular values.

It is straightforward to check that $x= A^+y$ satisfies the normal equation, even when all of the involved matrices are singular. On the other hand one can also show directly that is minimizes the problem. Given that there are $r$ singular values, let $\Pi=\left[\begin{smallmatrix} 0_{r\times r} & 0 \\ 0 & \mathbb I_{n-r}\end{smallmatrix}\right]$ then

$$\begin{aligned} &\|Ax-y\| \\&= \|U\Sigma V^ x - y\| &\text{using SVD} \\&= \|\Sigma V^x - U^T y \| &\text{since $V$ orthonormal} \\&=\|\Sigma V^ x - (\Sigma\Sigma^+ +\Pi) U^y\| &\text{as $\Sigma\Sigma^++\Pi=\mathbb I_n$} \\&= \|\Sigma(V^x-\Sigma^+U^y) - \Pi U^ y \| &\text{regrouping} \\&= \|\Sigma(V^x-\Sigma^+U^y)\| + \|\Pi U^ y\| &\text{vectors are orthogonal} \\&=\left\| \left[ \begin{smallmatrix}D & 0 \\ 0&0\end{smallmatrix}\right] \left( \left[\begin{smallmatrix}V_1^\\ V_2^\end{smallmatrix}\right] x - \left[\begin{smallmatrix}D^+ & 0 \\ 0&0\end{smallmatrix}\right] \left[\begin{smallmatrix}U_1^ \\ U_2^\end{smallmatrix}\right]y \right) \right\| + \left\| \left[\begin{smallmatrix}0 & 0 \\ 0&\mathbb I\end{smallmatrix}\right] \left[\begin{smallmatrix}U_1^ \\ U_2^ \end{smallmatrix}\right] y \right\| &\text{block form} \\&= \left\|\left[\begin{smallmatrix}D(V_1^x - D^+U_1^y) \\ 0\end{smallmatrix}\right]\right\| + \left\| \left[\begin{smallmatrix} 0 \\ U_2^y \end{smallmatrix}\right] \right\| &\text{simplifying} \\&= \left\|D\big(V_1^x - D^+U_1^y\big)\right\| + \|U_2^ y \| &\text{since} \left\|\left[\begin{smallmatrix}z\\0_m \end{smallmatrix}\right]\right\| = \|z\| \end{aligned}$$

which is minimal, in fact zero, iff $V^_1 x = D^+ U_1^ y$. Expanding $x$ in terms of the basis $V$, i.e.: $$\require{mathtools}$$ $$ x = Vz = \left[\begin{smallmatrix}V_1 & V_2\end{smallmatrix}\right] \left[\begin{smallmatrix}z_1 \\ z_2\end{smallmatrix}\right] = V_1 z_1 + V_2 z_2 $$

Shows that $V^_1 x = D^+ U_1^ y \iff z_1 = D^+ U_1^ y$. Since $x = V_1D^+ U_1^ = A^+$, this means:

$$ \min_x \|Ax-y\| = \{A^+y + v_2\mid v_2\in \mathcal V_2\} = A^+y + \ker(A) $$ Moreover, as $A^+y\in \mathcal V_1 = \ker(A)^\perp$ is orthogonal to $\mathcal V_2$ holds $\|A^+y + v_2\| = \|A^+y\| + \|v_2\|$, which implies that

$$ A^+y = \arg\min\{ \|z\| \mid z\in\min_x \|Ax-y\| \} $$

I.e. $x=A^+y$ is special among all the minimizers of $\|Ax-y\|$, in the sense that it is the so called minimum-norm solution.