0
$\begingroup$

I have a set of N real sequences and need to pick K sequences (with no replacement) such that their sum has the minimum variance.

E.g. I have N=3 real sequences of length 5:

x(1)=[-0.9   0.7    2.0    2.5    1.5]
x(2)=[-1.8  -0.2    0.5   -1.3   -0.7]
x(3)=[-1.5  -0.9    0.3    1.5    0.4]

If I need to select K=2 sequences, the variance of the sums is:

var(x(1)+x(2))=3.7
var(x(1)+x(3))=6.1
var(x(2)+x(3))=2.5

So I'd want to select sequences 2 & 3.

This is easy to brute force for small N, but my real application has much larger N. For example, for N=20 and K=10, there are 184756 combinations. Since my sequence lengths are long and computational time is critical, this is not feasible.

Is there an efficient algorithm to do the selection? Or even to give an approximate solution? Or reduce the problem space to likely candidates?

$\endgroup$
5
  • $\begingroup$ I don't have a clear path in mind right now, but it does very much sound like an application for PCA $\endgroup$ Sep 28 at 11:57
  • $\begingroup$ @MarcusMüller Can you expand on that? Would the variance of the sum of the principal components be related to the variance of the sum of the original sequences? Could you then do the optimization on a reduced set of principal components to speed up the calculation? $\endgroup$
    – tkw954
    Sep 29 at 15:52
  • $\begingroup$ Idea is this: PCA to find the direction in which your dataset has the highest variance. In that direction, combine the most antipodal elements with the same amplitude along that direction, to "cancel" as much of that variance (they are correlated – but with a negative factor). You might want to try a few until you find one combination that has minimum variance. Iterate! $\endgroup$ Sep 29 at 15:56
  • $\begingroup$ @MarcusMüller I'll try it. $\endgroup$
    – tkw954
    Sep 29 at 16:21
  • 1
    $\begingroup$ @MarcusMüller It seems that a set of sequences with a low variance will tend to cancel in the principal component domain, as you suggest. However, there are also a number of sequences that cancel in the principal component domain that do not produce low variance. So your suggestion may reduce the search space but does not indicate the solution. I'll have to do further simulation to see if this is worth while. $\endgroup$
    – tkw954
    Sep 30 at 3:28
2
$\begingroup$

If your sequences are uncorrelated, then for the sum of the sequences, the variance becomes $$ \mathrm{Var}\left(\sum_i^N X_i\right) = \sum_i^N \mathrm{Var}(X_i) $$ and it is easy to solve the minimum problme.

If they are unfortunately correlated, the variance is $$ \mathrm{Var}\left(\sum_i^N X_i\right) = \sum_i^N \mathrm{Var}(X_i) + \sum_{i\neq j}\mathrm{Cov}(X_i,X_j) $$ You can use cov in MATLAB to calculate the covariance matrix of all the N sequences. The second term in the above equation is the sum of the off-diagonal elements of the covariance matrix.

Global minimum is relatively hard to find. An idea is starting from the K sequences with the smallest variance and search upwards, or from the K sequences with the smallest covariance.

$\endgroup$
1
  • $\begingroup$ Good idea. Unfortunately, for my application the covariance is significant: between 10% and 80% of the variance. $\endgroup$
    – tkw954
    Sep 29 at 15:29

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.