Intuición sobre cierta clase de problemas de optimización cuadrática

Question

Sea $\mathcal{X} = \{\mathbf{X}\in\mathbb{C}^{d\times d}:\|\mathbf{X}\|\leq 1\}$ donde $\|\cdot\|$ es la norma de Frobenius. Sea $\mathbf{y}\in\mathbb{C}^{d\times 1}$ . Estamos familiarizados con la siguiente maximización: \begin{align} \max_{\mathbf{X}\in\mathcal{X}}\|\mathbf{X}\mathbf{y}\| \end{align} Tenemos $\|\mathbf{X}\mathbf{y}\|\leq\|\mathbf{X}\|\|\mathbf{y}\| \leq \|\mathbf{y}\|$ con igualdad si, por ejemplo $\mathbf{X} = \frac{\mathbf{y}\mathbf{y}^{\dagger}}{\|\mathbf{y}\|^2}$ . Por lo tanto, decimos que hay un rango- $1$ solución óptima. Esto es Cauchy-Scharwz disfrazado y el resultado es bastante intuitivo. La forma en que yo lo veo es tomando la descomposición espectral $\mathbf{X}^{\dagger}\mathbf{X} = \sum_i \lambda_i \mathbf{v}_i\mathbf{v}_i^{\dagger}$ . Entonces, $\|\mathbf{X}\mathbf{y}\|^2 = \sum_i \lambda_i |\langle \mathbf{y},\mathbf{v}_i\rangle|^2$ . Tengo un conjunto ortonormal de vectores propios que puedo optimizar, con sus respectivas "potencias" (valores propios) que deben sumar como máximo $1$ . Lo mejor es elegir uno de los $\mathbf{v}_i$ "en dirección a" $\mathbf{y}$ con la potencia máxima de $1$ .

Mi pregunta se refiere a la siguiente generalización. Sea $\mathbf{y}_1,\ldots,\mathbf{y}_K\in\mathbb{C}^{d\times 1}$ y considerar \begin{align} \max_{\mathbf{X}\in\mathcal{X}}\min_{k\in\{1,\ldots,K\}}\|\mathbf{X}\mathbf{y}_k\| \end{align} El problema de optimización analizado anteriormente es un caso particular en el que $K=1$ . Ahora, para cualquier $K>1$ "Intuitivamente", dado que ahora tenemos muchos vectores en muchas direcciones, siempre deberíamos gastar energía en varias direcciones diferentes. Curiosamente, cuando $K\in\{2,3\}$ existe -de nuevo- un rango- $1$ solución óptima (véase, por ejemplo http://www1.se.cuhk.edu.hk/~zhang/Informes/seem2005-02.pdf ). En general, existe un rango aproximado- $\sqrt{K}$ solución óptima, pero el valor exacto parece estar abierto.

Como en el caso de $K=1$ me esforcé mucho para tener una intuición geométrica de por qué el rango $1$ soluciones serían óptimas para $K=2$ o $K=3$ y por qué la escala sería como máximo $\sqrt{K}$ para grandes $K$ pero no he encontrado una explicación razonable. Me preguntaba si alguien tiene alguna idea en este contexto.

Answer 1

Para $K=2$ como los unitarios conservan la norma de Frobenius, podemos suponer que nuestros dos vectores se encuentran en el plano $\mathbb R^2$ y su imagen bajo $M$ también se encuentra en el plano $\mathbb R^2$ . Así que las esperanzas en la intuición geométrica parecen brillantes.

Tenemos dos vectores en el plano, y nos gustaría una transformación lineal que los hiciera grandes a ambos, sin hacer demasiado grande un par de vectores ortogonales.

Si nuestros dos vectores son ortogonales, entonces cualquier transformación que los envíe a dos vectores de la misma longitud será óptima. También podríamos enviarlos al mismo vector o a vectores opuestos, creando un rango $1$ matriz.

Si nuestros dos vectores tienen un ángulo agudo entre ellos, esto reducirá las normas de las transformaciones que los envían a vectores similares y aumentará las normas de las transformaciones que los envían a vectores diferentes. La norma óptima será enviarlos al mismo vector.

Del mismo modo, si nuestros dos vectores tienen un ángulo obtuso entre ellos, esto aumentará las normas de las transformaciones que los envían a vectores similares y disminuirá las normas de las transformaciones que los envían a vectores disímiles. La norma óptima será enviarlos al vector opuesto.

Para grandes $K$ podría ser útil considerar el problema relacionado $\max_{x\in \mathcal X} \sum_{k \in (1,\dots, K)} || X Y_k||^2$ . Es fácil comprobar que, para este problema, un rango $1$ es siempre óptima, de hecho, para cualquier matriz $M$ y proyección $P$ o bien $PM$ es al menos tan bueno como $M$ o $(1-P)M$ es al menos tan bueno como $M$ . Por lo tanto, lo único que nos obliga a utilizar un rango superior en general es garantizar que la norma se distribuya uniformemente.

No tengo ninguna intuición $\sqrt{K}$ es la asintótica correcta.