2
$\begingroup$

Let's say we have the following optimization problem. (All the $\Sigma_{ii}$'s are positive definite.)

$\max u^\top \Sigma_{12} v\quad$ $\text{subject to}\quad u^\top \Sigma_{11} u = 1\quad and\quad v^\top \Sigma_{11} v = 1$.

From SVD, we have if $\Sigma_{12}$ is a rank-1 matrix, then $u^*$ and $v^*$ is the solution to the above optimization problem if and only if $\Sigma_{12} = \lambda \Sigma_{11} u^* v^{*\top}\Sigma_{22}$.

We can also formulate the above optimization problem into a generalized eigenvalue problem as follows

$\begin{bmatrix}0 & \Sigma_{12} \\ \Sigma_{21} & 0\end{bmatrix}\begin{bmatrix}u \\ v\end{bmatrix} = \lambda \begin{bmatrix}\Sigma_{11} & 0 \\ 0 & \Sigma_{22} \end{bmatrix}\begin{bmatrix}u \\ v\end{bmatrix}$ $\quad \text{subject to}\quad u^\top \Sigma_{11} u = 1\quad and\quad v^\top \Sigma_{11} v = 1$. We can see that $u^*$ and $v^*$ is also the generalized eigenvector to this problem corresponding to the largest eigenvalue. Thus similar to the above argument, we can say if $\Sigma_{12}$ is a rank-1 matrix, then $u^*$ and $v^*$ is the solution to the above generalized eigenvalue problem corresponding to the largest eigenvalue if and only if $\Sigma_{12} = \lambda \Sigma_{11} u^* v^{*\top}\Sigma_{22}$.

My question is how we can generalize this to higher dimensions (by higher dimension, I mean the number of blocks increases in the generalized eigenvalue problem).

$\frac{1}{M-1}\begin{bmatrix}0 & \Sigma_{12} & \ldots & \Sigma_{1M} \\ \Sigma_{21} & 0 & \ldots & \Sigma_{2M} \\ \ldots & \ldots & \ldots & \ldots \\ \Sigma_{M1} & \Sigma_{M2} & \ldots & 0\end{bmatrix} \begin{bmatrix}u_1 \\ u_2 \\ \ldots \\ u_M \end{bmatrix} = \lambda \begin{bmatrix}\Sigma_{11} & 0 & \ldots & 0 \\ 0 & \Sigma_{22} & \ldots & 0 \\ \ldots & \ldots & \ldots & \ldots \\ 0 & \ldots & \ldots & \Sigma_{MM}\end{bmatrix} \begin{bmatrix}u_1 \\ u_2 \\ \ldots \\ u_M \end{bmatrix}$

$\quad \text{subject to}\quad u_{i}^\top \Sigma_{ii} u_i = 1 \quad \forall i$.

Thanks for your help!

$\endgroup$
  • $\begingroup$ If $\Sigma_{11}$ is symmetric, then the solution to the first problem is $\| \Sigma_{11}^{-{1 \over 2}} \Sigma_{12} \Sigma_{11}^{-{1 \over 2}}\|$. $\endgroup$ – copper.hat Apr 18 '16 at 18:09
  • $\begingroup$ yes, but what you said is the optimal value rather than the optimal solution. I wonder is there any characterization for the optimal solution. $\endgroup$ – Wuchen Apr 18 '16 at 18:27
  • $\begingroup$ The right & left singular vectors corresponding to the norm in my last comment. $\endgroup$ – copper.hat Apr 18 '16 at 18:33
  • $\begingroup$ Yes, you are absolutely right. How about the higher dimension one? What's the form of $\Sigma_{ij}$ such that the solution is $u_1$ to $u_M$? $\endgroup$ – Wuchen Apr 18 '16 at 18:35
  • $\begingroup$ It is not clear that there is an easy shortcut for the generalised eigenvalue problem... $\endgroup$ – copper.hat Apr 18 '16 at 18:38

Your Answer

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

Browse other questions tagged or ask your own question.