Let $\mathbf{x}$ be the solution to the following problem
$$\displaystyle\min_{\mathbf{x}} \|\mathbf{y+Ax}\|_\infty \quad{} \text{subject to} \quad{} \|\mathbf{x}\|_2^2\leq \alpha\|\mathbf{y}\|_2^2$$
$\mathbf{y} \in \mathbb{C}^{N\times 1}$, $\mathbf{A} \in \mathbb{C}^{N\times M}$ and both are known and $\mathbf{A}$ has orthogonal columns. $\mathbf{x} \in \mathbb{C}^{M\times 1}$ and $\alpha$ is a scalar. I'm trying to find an upper bound for $\|\mathbf{y+Ax}\|_2^2$.
After solving the problem numerically, when I plot $\|\mathbf{y+Ax}\|_2^2$ against $\alpha\|\mathbf{y}\|_2^2$, I see that $\|\mathbf{y+Ax}\|_2^2$ is constant after a certain $\alpha$, i.e., it saturates and does not increase with $\alpha$.
Is there a way to have a concrete proof of this observation?
There is a value of $\vec{x}$ for which $||\vec{y}+A\vec{x}||$ is minimized.
Think of $\vec{y}$ as a vector in 3-space, $A\vec{x}$ is all the points in a plane through the origin, and $y+Ax$ is the set of points in a plane through the point $y$.
There is one point in this plane closest to the origin. Call it $y+Ax_0$. As soon as $\alpha$ is large enough that $||x_0||_2^2<\alpha||y||_2^2$, your algorithm will find $x_0$, and stay there no matter how large $\alpha$ gets.
$$F(x)=||y+Ax||_2^2=(y+Ax)^T(y+Ax)=y^Ty+y^TAx+x^TA^Ty+x^TA^TAx\\ =\sum_{i=1}^ny_i^2+2\sum_{i=1}^n\sum_{j=1}^my_iA_{ij}x_j+\sum_{i=1}^m\sum_{j-1}^m\sum_{k=1}^nx_iA_{ki}A_{kj}x_j$$
This is quadratic in all the $x_i$. At the minimum, all the derivatives $\partial F/\partial x_i=0$. If you differentiate with respect to each $x_i$ in turn, and put the $m$ equations you get back together again, you find $$2A^TAx+2A^Ty=0$$