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
    Commented 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
    Commented 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
    Commented 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
    Commented 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
    Commented 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .