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.

(Old-Question) Given a $n\times n$ symmetric matrix $X$, I would like to factor it using a vector $c$ of size $n \times 1$ such that: $\sum_{i,j} [X_{ij} \cdot c_i\cdot c_j]$ is minimum. How can I find the optimal vector $c^*$?

Constraint: The entries in the vector $c$ should sum to $1$.

Also, feel free to make notes about any optimality conditions/ assumptions that might go around this problem.

(New-Edited Question)

w.r.t the above question, this is an updated problem: If for any 3 distinct indices i,j,k if the motive is to preserve the ordering between $X_{ij}$, $X_{jk}$ , $X_{ki}$ after the approximation with the vector c, defined in the old question above, what would be a suitable loss function containing X and c?

ex: If $X_{12}$ > $X_{23}$ < $X_{31}$ for a chosen i=1,j=2,k=3 then I would like to have $c_1.c_2$ > $c_2.c_3$ < $c_3.c_1$ after the approximation. What is a suitable loss function?

share|improve this question
    
If you want to use TeX, write your TeX code within dollar signs. Please define your variables, what is $\sigma$? If this question is the same as your last question, please edit that question instead of starting a new question. –  Calle Jan 25 '12 at 15:10
    
@ Calle I have not used a $\sigma$. This is a different question than the previous. –  user23600 Jan 25 '12 at 15:17
    
So you want the $c$ such that $c^T X c$ is minimized, subject to $e^Tc=1$ (where $e$ is a vector of all 1s)? Consider the method of Lagrange multipliers. Alternatively the solution is $c^* = (X^{-1}e) / (e^TX^{-1}e)$ assuming $X$ is invertible. –  Chris Taylor Jan 25 '12 at 15:27
    
@ChrisTaylor Yes, that is the right formulation. –  user23600 Jan 25 '12 at 15:29
    
@ I have an updated question, that takes it from here. Do have a look. –  user23600 Jan 25 '12 at 15:51
show 2 more comments

1 Answer

up vote 0 down vote accepted

If you want to know how to solve this, consider looking at the method of Lagrange multipliers.

The solution (assuming $X$ is invertible) is given by

$$c^* = (X^{-1}e) / (e^TX^{-1}e)$$

Note that this will only be a minimum if $X$ is positive definite. If $X$ is negative definite then this is a maximum, and if $X$ is mixed then this will be a saddle.

I may expand this answer later - leave me a comment if that would be helpful.

share|improve this answer
add comment

Your Answer

 
discard

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