I'm working on an underdetermined linear system and I need to characterize a possible set of soluitions. Let me properly formulate the problem.
Consider the following linear system:
$$\mathbf{A}x = y$$
with $\mathbf{A} \in \mathbb{R}^{M \times N}$, with $N > M$ (i.e., $\mathbf{A}$ is a flat matrix, with more columns than rows), $x \in \mathbb{R}^{N}$ and $y \in \mathbb{R}^{M}$.
Since $\mathbf{A}$ is not injective, we have
$$\textrm{dim}(\textrm{kernel}(\mathbf{A})) = N-M = K$$
Hence, we can construct another solution to the linear system as follows
$$\mathbf{A}z = y$$ where $$z = x + e$$
and $e \in \textrm{kernel}(\mathbf(A))$.
I'm interested in studying the $||\cdot||_{\infty}$ of $z$. I've already an upper bound, given by
$$||z||_\infty \leq ||x||_\infty + ||e||_\infty$$
Question: is there a lower bound for $||z||_{\infty}$ as a function of $x$ and $e$ ?
There is no lower bound in terms of $x$ and $e$. The only lower bound there is is 0.
However, you can find $x$ and $e$ such that $z$ has minimum norm. This can be cast as the following optimization problem:
$$\min_x ||x||_\infty\ \mathrm{such\ that }\ y-Ax=0.$$
This a linear program that can be efficiently solved but there is no closed-form solution.
This is equivalent to solving
$$\min_z ||A^+y+(I-A^+A)z||_\infty,$$
where $A^+$ is the Moore-Penrose pseudo inverse of $A$.