Problema de optimización de matriz

Question

Estoy teniendo algunas dificultades para la comprensión de un argumento en un libro. Los autores afirman que el siguiente Teorema es una consecuencia directa del lema anterior, pero no dan detalles. O sea es completamente trivial y no estoy viendo, o hay algunos detalles que faltan.

Lema:

Deje $A$ ser $n\times n$ simétrica positiva definida la matriz de más de $\mathbb{R}$ con autovalores $\lambda_1>\lambda_2>\ldots>\lambda_n$ y los vectores propios asociados $v_1,v_2,\ldots v_n$. Entonces tenemos $$ \max\{x^Impuestos: ||x||=1, \langle x,v_j\rangle=0 \,\,\text{para}\,\, 1\leq j\leq i-1\}=\lambda_i, $$

donde el máximo se alcanza precisamente en los puntos de $v_i$ e $-v_i$.

Teorema: Deje $p\leq n$. Considere el siguiente problema de optimización \begin{align} \max\sum_{k=1}^p &\langle Au_k,u_k\rangle\\ s.t:\,\,(u_1,\ldots u_p)&\,\,\,\text{is an orthonormal system} \end{align}

El reclamo es que el valor óptimo es $\sum_{k=1}^p \lambda_k$con solución óptima $(v_1,v_2,\ldots,v_p)$, y que la solución es única, hasta firmar y permutación.

A mí me parece que la optimización se lleva a cabo sucesivamente la maximización de cada sumando. No entiendo por qué esto es legítimo. Lo que me estoy perdiendo aquí?

Gracias

Answer 1

Observe que la suma de $\sum_{k=1}^p\langle Au_k,u_k\rangle$ sólo depende del subespacio $S$ generado por los $u_k$s, pero no en el ortonormales sistema de $(u_1,\ldots,u_p)$ sí. De hecho, si ampliamos el ortonormales a un sistema de base ortonormales $(u_1,\ldots,u_n)$ de $\mathbb R^n$ y denotan por $P_S$ el proyector ortogonal en $S$, luego $$ \sum_{k=1}^p\langle Au_k,u_k\rangle =\sum_{k=1}^n\langle AP_Su_k,P_Su_k\rangle =\operatorname{tr}(U^TP_S^TAP_SU) =\operatorname{tr}(AP_S) $$ y la última expresión anterior sólo depende de $S$ más que en ninguna base de $S$.

Por lo tanto, como se ha señalado por parte de un usuario en un comentario, la singularidad de reclamación en el teorema está mal.

Dicho esto, el teorema se sigue del lema más o menos directamente. Está claro que sigue del lema si $p=1$. Cuando $p>1$, vamos a $S$ ser un maximizador de $\operatorname{tr}(AP_S)$. Si $v_1\not\in S$, $S$ debe contener una $(p-1)$-dimensiones subespacio $S'$ que es ortogonal a $v_1$ (si $v_1\perp S$, simplemente elija cualquiera de los $(p-1)$-dimensiones subespacio de $S$; de lo contrario, deje $w\ne0$ ser la proyección ortogonal de $v_1$ en $S$ y tome $S'$ como el complemento ortogonal de $\operatorname{span}(w)$ en $S$). Pero entonces, por el lema, $\operatorname{span}(v_1)+S'$ sería una mejor solución que $S$, lo cual es una contradicción.

Por lo tanto $v_1$ debe estar dentro de $S$ e $\operatorname{tr}(AP_S)=v_1^TAv_1+\operatorname{tr}(AP_{S'})$. La dimensión del problema se reduce ahora a uno, y por el lema, $u^TAu\le v_2^TAv_2$ por cada $u\perp v_1$ y, en particular, para cada $u\in S'$. Por un argumento similar al anterior, llegamos a la conclusión de que $v_2$ debe estar dentro de los óptimos $S'$. Proceder de forma recursiva, vemos que el óptimo $S$ está dado por el lapso de $v_1,\ldots,v_p$.