Selecting subset of sequences so their sum has minimum variance?

Question

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?

Answer 1

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.