Find the matrix maximizing a summation of bilinear forms

Question

Given $d, n \in \mathbb{N}$ and $x_k, y_k \in \mathbb{R}^d$, for $1 \leq k \leq n$, we want to find $\arg \max_{A: ||A||_2 = 1} \sum_k \langle x_k, A y_k \rangle$, where $||\cdot||_2$ denotes spectral norm. I can see that this is a linear combination of $A_{ij}$'s, where the coefficient of $A_{ij}$ is $\sum_k (x_k)_i (y_k)_j$. But I cannot proceed further.

Answer 1

Let $X$ be the matrix whose $j$-th column for each $j$ is $x_j$ and define $Y$ analogously. Let $U\Sigma V^T$ be a singular value decomposition of $XY^T$ and let $B=U^TAV$. Then $\|A\|_2=\|B\|_2$. Also, when $\|B\|_2=1$, the norm of every column of $B$ must be $\le1$. In particular, we have $|b_{kk}|\le 1$ for each $k$. Therefore $$ \begin{align} \max_{\|A\|_2=1}\sum_k\langle x_k,Ay_k\rangle &=\max_{\|A\|_2=1}\langle XY^T,A\rangle_F\\ &=\max_{\|A\|_2=1}\langle U\Sigma V^T,A\rangle_F\\ &=\max_{\|B\|_2=1}\langle \Sigma,B\rangle_F\tag{1}\\ &=\max_{\|B\|_2=1}\sum_k\sigma_kb_{kk}\\ &\le\max_{\|B\|_2=1}\sum_k\sigma_k\quad(\because |b_{kk}|\le1)\tag{2}\\ &=\|\Sigma\|_{\mathrm{tr}}\\ &=\|XY^T\|_{\mathrm{tr}} \end{align} $$ where $\|\cdot\|_\mathrm{tr}$ denotes the trace norm (a.k.a. nuclear norm or Schatten $1$-norm) of a matrix. Clearly, equality holds in $(2)$ above when $b_{11}=\cdots=b_{dd}=1$. Therefore $B=I$ is an optimal solution to the transformed problem $(1)$ (and such it is the only solution if $XY^T$ is nonsingular), $A=UV^T$ is an optimal solution to the original optimisation problem, and the maximum objective function value is $\|XY^T\|_{\mathrm{tr}}$.