# Spectral/Eigen-value solution?

Is there a spectral or eigen-value solution to finding $d$ vectors $x_1...x_n$ such that

$\sum_{i,j=1}^{d} C_{i,j} \cdot x_i^\top M x_j$ is minimized, with $C_{i,j}$ being a constant real-scalar and $M$ being a p.s.d real-matrix under othogonality or weighted orthogonality constraints over $x$'s?

If not under any other constraints-what would be the solution - to find the $x$'s?

-

I am not sure if this helps, but it will be good if your $C$ have some nice properties. Define the matrix $X=[x_1,x_2,...,x_n]$ with the vectors under question as columns. Then you can rewrite your problem as \begin{align} \min_{X}~trace(CX^{T}MX) \end{align} Define $M=F^{T}F$ ($M$ being a psd matrix, you will be able to find such a $F$). Define $Y=FX$. You get the above problem as \begin{align} \min_{Y}~trace(CY^{T}Y) \end{align} Now $trace(CY^{T}Y)=trace(YCY^{T})$, (circularity of trace). At this point, to progress any further, we need to have some properties on $C$. For instance, if $C$ is symmetric, you can decompose as you did with $M$ and come up with a even simpler condition.

EDIT---

Starting from the last point, define $Z=Y^{T}Y$. Then you can rewrite the problem as
\begin{align} \min_{Z}~trace(CZ) \\ subject ~to~Z\geq0 \end{align}
where $Z\geq 0$ means it should be psd. This is a convex optimization problem with a linear objective and a semi-definite constraint. It is referred to as semi-definite programming. If you do not have any nice properties on $C$, I think this is what you can do.

-

If define the matrix $\left[C\right]_{ij}=C_{ij}$ then I get that $C^\top$ is the factor. Other than that un-stated detail @dineshdileep looks exactly correct to me (though admittedly I have not done much with convex optimization). Here are my steps to bring you (close) to the first statement of his, using the same $X$ with $x$'s as columns: \begin{align} \sum_{i=1}^{d}\sum_{j=1}^{d}C_{i,j}x_i^\top Mx_j= & \sum_{i=1}^{d}\sum_{j=1}^{d}x_i^\top Mx_j C_{i,j} \tag{$C_{ij}$ is a scalar}\\ = & \sum_{i=1}^{d}x_i^\top M\left(\sum_{j=1}^{d} x_j C_{i,j}\right) \tag{sum of $j$}\\ = & \sum_{i=1}^{d}x_i^\top M \left[XC^\top \right]_{\star i} \tag{col-mix of $X$}\\ = & \operatorname{trace}(X^\top MXC^\top) \end{align}

-
What do you mean by factor? You mean- it is supposed to be $C^T$ instead of $C$ in the trace formulation? – qlinck Nov 8 '12 at 20:07
@DineshDileep If $Y^{*}$ is the optimal solution for $Y$, then would $F^{-1}Y$ be the optimal solution for $X$? – qlinck Nov 8 '12 at 21:11
@qlinck it depends, $M$ is a psd matrix, so $F$ may not be unique. I will have to use the pseudo inverse. – dineshdileep Nov 9 '12 at 3:06
@adam Please tell what is wrong with this formulation. Define the matrix $[D]_{i,j}=x_i ^{T}Mx_j$. This implies $D=X^{T}MX$. Also $\sum_{i,j}C_{i,j}D_{i,j}=trace(CD)$. Hence $trace(CD)=trace(CX^{T}MX)$. I can't find anything wrong with it and I can't anything wrong with your argument also!!! – dineshdileep Nov 9 '12 at 3:11
Not sure about $\sum_{ij}C_{ij}D_{ij}$. I would do $\operatorname{trace}(CD) = \sum_i C_{i\star} D_{\star i}$, is that the same? I believe it is not but only because the transpose difference. Multiplication takes rows in one with columns in the other. – adam W Nov 9 '12 at 15:59