Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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}

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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