0
$\begingroup$

Consider $x$ an n-dimensional vector with $x_i$ is integer in the range $[0 \dots k], k\in N$.

Given $A_{n\times n}$ is the covariance matrix of $x$.

$u$ is a given n-dimensional vector of real values with $0.0 \leq u_i \leq k.0$

Given a set of $x$, I need to find the minimum value of $f(x)$ defined as follow:

$f(x) = \sum_{i=1}^n\sum_{j\neq i}(x_i-u_i)(x_j-u_j)A_{ij}$

I've tried to simply calculate all the values of $f(x)$ and find the minimum of them. In matlab, it could take me more than 30 minutes if $n=1000$ and $k \leq 5$.

Does any one here know of any efficient algorithm for this problem? If possible, could you give me some suggestion or direct me to the literature where I can search for the solution?

Thanks,

Improve this question
$\endgroup$
11
  • $\begingroup$ What is the $X$ that appears only at the end of the second sentence? $\endgroup$
    – Gerry Myerson
    Nov 27, 2011 at 11:20
  • $\begingroup$ Also it is not clear to me what the range of indices in the double sum is. I guess what was meant is just $i,j:1\le i,j\le n, i\ne j$ but that's certainly not what is written. $\endgroup$
    – fedja
    Nov 27, 2011 at 14:49
  • $\begingroup$ @Gerry: by $X$ I means the vectors $x$. @fedja: Yes, I actually means $1 \leq i,j \leq n, i \neq j$ $\endgroup$
    – chepukha
    Nov 28, 2011 at 4:25
  • 3
    $\begingroup$ I suggest rephrasing this as locating the minimizer of $x^T A x - bx +c$, and then using the fact that $A$ is symmetric, and positive semi-definite, to use a Krylov method to solve the associate linear problem. $\endgroup$
    – Nilima Nigam
    Nov 28, 2011 at 5:53
  • 2
    $\begingroup$ @Federico Poloni, this terminology is often associated with estimation problems. I think the OP meant to say that $x$ is a vector of random variables with an associated covariance matrix $A$. Usually $A$ is updated recursively, this in this instance, $A$ would be a constant covariance matrix and is used as a weighting matrix in the estimation problem. @Barry Cipra, you have hit the nail on the head. It is a quadratic integer programming problem. $\endgroup$
    – Gilead
    Nov 28, 2011 at 16:58

1 Answer 1

Reset to default
1
$\begingroup$

You are given a set of vectors, and you must find the best choice in this set. It is unlikely that an analytical method will give you the answer. Instead, I suggest you find a way to quickly discard vectors that are bad candidates.

Here is what might be the basis for a practical algorithm.

Typically, covariance matrices can be approximated using a low-rank matrix. That is, $A$ is diagonalizable and most of its eigenvalues are near zero relative to the highest eigenvalues.

For simplicity, let me assume that we can approximate $A$ using a one-dimensional projection. That is, we have that $A \approx \lambda y y^{\top}$. Then we can estimate $(x-u)^T A (x-u)$ as $((x-u) \cdot y)^2$. This last expression can be computed much faster. Naturally, you can extend this analysis with more eigenvalues for more accuracy. Let me write $P(x)$ this estimate of $(x-u)^T A (x-u)$. The important thing is that $P(x)$ can be computed much faster than $(x-u)^T A (x-u)$ and is somewhat accurate. Quickly find $\kappa$ such that $| (x-u)^T A (x-u)- ((x-u) \cdot y)^2 |\leq \kappa$. You might be able to compute $\kappa$ from the eigenvalues of $A$.

This fast estimation be used to quickly prune out $x$'s that cannot possibly be the best choice. That is, if $\max_x P(x) = M$ then any $x$ such that $ P(x) < M-\kappa$ can be rejected.

This leaves you with a smaller sets of vectors $x$ over which you can do the full computation: $\arg \max (x-u)^T A (x-u)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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