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

\begin{equation} \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} \end{equation} 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}.$

Thanks in advance!


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.