# Maximization under Kronecker product vectors

I need some hints to solve the optimization problem on $\mathbf{x}$ and $\mathbf{y}$

$$\begin{array}{c} \text{max} \hspace{4mm} (\mathbf{x}\otimes \mathbf{y})^TA(\mathbf{x}\otimes \mathbf{y})\\ s.t \hspace{10mm}\|\mathbf{x}\|_2 = 1 \\ \hspace{17mm}\|\mathbf{y}\|_2 = 1, \end{array}$$ where $\mathbf{x} \in \mathbb{R}^{m}$ and $\mathbf{y} \in \mathbb{R}^{n}.$ The matrix $A$ is a rank-one symmetric matrix given by $A = \mathbf{v} \mathbf{v}^{T},$ where $\mathbf{v} \in \mathbb{R}^{mn}.$

First, note that for any two equal-size vectors $v,w$, $w^T(vv^T)w=(w^Tv)^2$. Subdivide $v$ into $n\times 1$ blocks $v^{(i)}$, $i=1,2,\dots, m$. Then $$(x\otimes y)^Tv = \sum_{i=1}^m x_iy^Tv^{(i)} = y^T \sum_{i=1}^m x_i v^{(i)} = y^TVx$$ where $V\in\mathbb{R}^{n\times m}$ collects the vectors $v^{(i)}$ into columns. The problem becomes $$\max_{\|x\|_2=1,\|y\|_2=1} (x\otimes y)^TA(x\otimes y) = \max_{\|x\|_2=1,\|y\|_2=1} \left( y^T Vx \right)^2 \qquad (*)$$ But $\max_{\|y\|_2=1} y^Tw = \|w\|_2$ and $\max_{\|y\|_2=1} (y^Tw)^2 = \|w\|_2^2$, so $$\max_{\|x\|_2=1,\|y\|_2=1} (x\otimes y)^TA(x\otimes y) = \max_{\|x\|_2=1} \left\| Vx \right\|_2^2 = \sigma_1(V)^2$$ where $\sigma_1(V)$ is the largest singular value of $V$. The maximizing $x$ is any right-singular vector associated with $\sigma_1(V)$, and the corresponding maximizing $y$ is $y=\pm (\sigma_1(V))^{-1} Vx$, which is a corresponding left singular vector of $V$. In hindsight, I could have jumped right to the answer after (*).

• +1 Thank you very much, Michael! Just a typo: I think a square is missing in $(y^Tw)^{\color{red}2} = \|w\|^2_2$. – Alex Silva Jan 12 '15 at 15:22
• Corrected! Thanks for catching it – Michael Grant Jan 12 '15 at 15:23
• I just realized you were asking for hints! Oops :-) – Michael Grant Jan 12 '15 at 17:16
• Yeah! But when you suggested the transformation on $V$, I got it. :) – Alex Silva Jan 12 '15 at 17:18