0
$\begingroup$

(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?

  • 0
    @ Chris- I agree. Would you suggest that it be dealt with in a new posting?2012-01-26

1 Answers 1

0

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.