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?


  • $\begingroup$ What is the $X$ that appears only at the end of the second sentence? $\endgroup$ – Gerry Myerson Nov 27 '11 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 '11 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 '11 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 '11 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 '11 at 16:58

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)$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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