Optimization Kronecker

Question

Now I have to solve a optimization problem \begin{equation} u=\sum_{p=1}^{P}h_{1,p}\otimes h_{2,p}.\\ \min_{h_{1,p},h_{2,p}}u^TRu, \end{equation} with a iterative algorithm, where R is a correlation matrix.

Answer 1

First, minimization of the Rayleigh quotient $$\min_{u} \left(\frac{u^TRu}{u^Tu}\right)$$ is a well-known problem whose solution is the eigenvector associated with $\lambda_{min}$ of the $R$ matrix.

Second, any matrix can be expanded as a sum of Kronecker products $$X = \sum_{k=1}^{r} A_k\otimes B_k$$ if the dimensions of $(X,A_k,B_k)$ are compatible (which is guaranteed by the posted question).

The number of terms in the expansion is determined by the value of $r$ which the rank of the matrix $X$ after it has been reshaped and its elements permuted. For further details, look for papers by vanLoan & Pitsianis. Better yet, search for Pitsianis' 1997 thesis, which contains Matlab code for the decomposition.

The vector $u$ which minimizes the Rayleigh quotient, can therefore be expanded as $$u = \sum_{k=1}^{r} a_k\otimes b_k$$ Identifying $(a_k,b_k)\to(h_{1,k},h_{2,k})\,$ recovers the form of the current question.

Therefore, if $\,P\ge r,\,$ use the full Pitsianis decomposition, otherwise truncating the sum at the $P^{th}$ term will yield the "nearest Kronecker approximation" (which is another thing to google).