Intuition on a certain class of quadratic optimization problems

Question

Let $\mathcal{X} = \{\mathbf{X}\in\mathbb{C}^{d\times d}:\|\mathbf{X}\|\leq 1\}$, where $\|\cdot\|$ is the Frobenius norm. Let $\mathbf{y}\in\mathbb{C}^{d\times 1}$. We are familiar with the following maximization: \begin{align} \max_{\mathbf{X}\in\mathcal{X}}\|\mathbf{X}\mathbf{y}\| \end{align} We have $\|\mathbf{X}\mathbf{y}\|\leq\|\mathbf{X}\|\|\mathbf{y}\| \leq \|\mathbf{y}\|$ with equality if, for example, $\mathbf{X} = \frac{\mathbf{y}\mathbf{y}^{\dagger}}{\|\mathbf{y}\|^2}$. Hence, we say that there is a rank-$1$ optimal solution. This is Cauchy-Scharwz in disguise and the result is quite intuitive. The way I see it is by taking the spectral decomposition $\mathbf{X}^{\dagger}\mathbf{X} = \sum_i \lambda_i \mathbf{v}_i\mathbf{v}_i^{\dagger}$. Then, $\|\mathbf{X}\mathbf{y}\|^2 = \sum_i \lambda_i |\langle \mathbf{y},\mathbf{v}_i\rangle|^2$. I have an orthonormal set of eigenvectors that I can optimize, with their respective "powers" (eigenvalues) that should sum up to at most $1$. The best way is to choose one of the $\mathbf{v}_i$ "in the direction of" $\mathbf{y}$ with the maximum power of $1$.

My question is concerned with the following generalization. Let $\mathbf{y}_1,\ldots,\mathbf{y}_K\in\mathbb{C}^{d\times 1}$ and consider \begin{align} \max_{\mathbf{X}\in\mathcal{X}}\min_{k\in\{1,\ldots,K\}}\|\mathbf{X}\mathbf{y}_k\| \end{align} The optimization problem discussed before is a particular case where $K=1$. Now, for any $K>1$, "intuitively," since we now have many vectors in many directions, we should always spend power in several different directions. Interestingly enough, when $K\in\{2,3\}$, there exists -again- a rank-$1$ optimal solution (see e.g. http://www1.se.cuhk.edu.hk/~zhang/Reports/seem2005-02.pdf). In general, there exists a roughly rank-$\sqrt{K}$ optimal solution, but the exact value appears to be open.

Similar to the case of $K=1$, I tried a lot to gain some geometric intuition on why rank-$1$ solutions would be optimal for $K=2$ or $K=3$, and why would the scaling be as at most $\sqrt{K}$ for large $K$, but failed to come up with a reasonable explanation. I was wondering if anyone has any ideas in this context.

Answer 1

For $K=2$, because unitaries preserve Frobenius norm, we can assume our two vectors lie in the plane $\mathbb R^2$, and their image under $M$ also lies in the plane $\mathbb R^2$. So hopes for geometric intuition seem bright.

We have two vectors in the plane, and we would like a linear transformation that makes them both large, without making a pair of orthogonal vectors too large.

If our two vectors are orthogonal, then any transformation that sends them to two vectors of the same length will be optimal. We might as well send them to the same vector or to opposite vectors, creating a rank $1$ matrix.

If our two vectors have an acute angle between them, this will lower the norms of transformations that send them to similar vectors and raise the norms of transformations that send them to dissimilar vectors. The optimal norm will be to send them to the same vector.

Similarly, if our two vectors have an obtuse angle between them, this will raise the norms of transformatiosn that send them to similar vectors and lower the norms of transformations that send them to dissimilar vectors. The optimal norm will be to send them to the opposite vector.

For larger $K$, it might help to consider the related problem $\max_{x\in \mathcal X} \sum_{k \in (1,\dots, K)} || X Y_k||^2$. It is easy to check that, for this problem, a rank $1$ matrix is always optimal, in fact, for any matrix $M$ and projection $P$, either $PM$ is at least as good as $M$ or $(1-P)M$ is at least as good as $M$. So the only thing that requires us to use a higher rank in general is ensuring that the norm is evenly distributed.

I do not have any intuition $\sqrt{K}$ is the correct asymptotic, though.