# Finding the solution $\xi$ of $(M + \xi)x = y$ with the smallest 2-norm.

## Problem

Show $$\xi = \frac{(y - Mx)x^\ast}{x^\ast x}$$ is the solution of the following

$$(M + \xi)x = y$$

with the minimum $$\Vert \xi\Vert_2$$, where $$M \in \mathbb{C}^{m \times n}, x \neq 0 \in \mathbb{C}^n, y \in \mathbb{C}$$.

## Try

We have the form as follows:

$$M + \xi = \frac{M x^\ast x}{x^\ast x} + \frac{(y - Mx)x^\ast}{x^\ast x}$$

I have noticed the form's similarity with the operator 2-norm:

$$\sup_{x\neq0} \frac{\Vert Ax \Vert_2}{\Vert x \Vert_2} = \sup_{x\neq0} \frac{x^\ast A^\ast A x}{x^\ast x}$$

But here I cannot proceed. Any help will be appreciated.

From $$\xi x = y - Mx$$ we have $$\|\xi\|_2\geq\frac{\|\xi x\|_2}{\|x\|_2}=\frac{\|y-Mx\|_2}{\|x\|_2}.$$ It means that whatever $$\xi$$ such that $$(M+\xi)x=y$$ we have, its 2-norm cannot be smaller than $$\|y-Mx\|_2/\|x\|_2$$.
Now just verify we get equality above with $$\xi_\star=(y-Mx)x^*/\|x\|_2^2$$.
Note that this solution is also unique. Any other solution $$\xi$$ can be expressed as $$\xi=\xi_\star+\eta X_\perp^*,$$ where the columns of $$X_\perp\in\mathbb{C}^{n\times (n-1)}$$ are linearly independent and orthogonal to $$x$$ and $$\eta\in\mathbb{C}^{m\times (n-1)}$$ is a "parameter" matrix. If we also assume that the columns of $$X_\perp$$ are orthonormal then $$\xi=\left[\frac{y-Mx}{\|x\|_2},\eta\right]\left[\frac{x}{\|x\|_2},X_\perp\right]^*$$ Since the matrix on the right side is unitary, we have $$\|\xi\|_2=\left\|\left[\frac{y-Mx}{\|x\|_2},\eta\right]\right\|_2>\frac{\|y-Mx\|_2}{\|x\|_2}=\|\xi_\star\|$$ if $$\eta\neq 0$$.