¿Cuál es el límite superior para este 2-norma

Question

Deje $\mathbf{x}$ ser la solución para el siguiente problema

$$\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}$ y ambos son conocidos y $\mathbf{A}$ ha ortogonal columnas. $\mathbf{x} \in \mathbb{C}^{M\times 1}$ $\alpha$ es un escalar. Estoy tratando de encontrar una cota superior para $\|\mathbf{y+Ax}\|_2^2$.

Después de resolver el problema numéricamente, cuando me parcela $\|\mathbf{y+Ax}\|_2^2$ contra $\alpha\|\mathbf{y}\|_2^2$, veo que $\|\mathbf{y+Ax}\|_2^2$ es constante después de un cierto $\alpha$, es decir, se satura y no se incrementa con la $\alpha$.

Es allí una manera de tener una prueba concreta de esta observación?

Answer 1

La restricción $\|\mathbf x\|_2^2 \leq \alpha \|\mathbf y\|_2^2$ es inactivo cuando $\alpha$ es lo suficientemente grande como para que la solución al problema sin restricciones es la solución a la limitación de problema.

Entonces, las restricciones del problema no depende de la $\alpha$.

Answer 2

Hay un valor de $\vec{x}$ que $||\vec{y}+A\vec{x}||$ es mínimo.
Creo que de $\vec{y}$ como un vector en un espacio de 3 dimensiones, $A\vec{x}$ es todos los puntos en un plano que pasa por el origen, y $y+Ax$ es el conjunto de puntos en un plano a través del punto de $y$.
Hay un punto en este plano más cercano al origen. Llamarlo $y+Ax_0$. Tan pronto como $\alpha$ es lo suficientemente grande como $||x_0||_2^2<\alpha||y||_2^2$, su algoritmo encontrará $x_0$, y permanecer allí, sin importar cuán grande $\alpha$ recibe.
$$F(x)=||y+Ax||_2^2=(y+Ax)^T(y+Ax)=y^Ty+y^de Impuestos+x^TA^Ty+x^TA^de Impuestos\\ =\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$$
Este es cuadrática en todas las $x_i$. Como mínimo, todos los derivados $\partial F/\partial x_i=0$. Si usted se diferencian con respecto a cada una de las $x_i$ a su vez, y poner el $m$ ecuaciones volvais a estar juntos de nuevo, usted encontrará $$2A^TAx+2A^Ty=0$$