# Least correlated subset of random variables from a correlation matrix

I have a correlation matrix $A$, which I obtained using the Pearson's linear correlation coefficient through Matlab's corrcoef(). The correlation matrix of dimension 100x100, i.e. I computed the correlation matrix on 100 random variables.

Among these 100 random variables, I would like to find the 10 random variables whose correlation matrix contains as "little correlation" as possible (see Quantifying how much "more correlation" a correlation matrix A contains compared to a correlation matrix B regarding metrics to measure the overall correlation in a correlation matrix). I only care about pairwise correlation.

Are there good methods to find those 10 random variables in a reasonable amount of time (e.g. I don't want to try $\binom{100}{10}$ combinations)? Approximation algorithms are OK.

• metrics to measure the overall correlation. You are thinking specifically about the determinant? – ttnphns Aug 3 '14 at 6:37
• A very similar question stats.stackexchange.com/q/73125/3277. – ttnphns Aug 3 '14 at 6:55
• The log-determinant is a submodular function (see page 18 here). It's not increasing, unfortunately, which means the classic $1-1/e$ greedy approximation result doesn't apply, but it still feels like that might be helpful somehow.... – Dougal Aug 4 '14 at 6:43
• If you instead want to use the mean value of the correlation, this becomes a maximum edge weight clique problem, which is of course NP-hard but has seen some work on approximation algorithms. – Dougal Aug 4 '14 at 7:01
• What about that simple idea with cluster analysis. Take $|r|$ as the distance (dissimilarity) and do clustering by a selected method (I'd probably choose Ward or average linkage hierarchical). Select the most tight cluster consisting of 10 items. – ttnphns Aug 4 '14 at 11:43

Let us consider the sum of absolute pairwise correlations as our measure of choice. We thus seek a vector $v\in\{0,1\}^N$ with $l_1(v)=n$ which will minimize $v'Qv$ where $Q_{ij}=|A_{ij}|$.

Assume Q is also positive definite as A, the problem is reduced to solving the constrained quadratic optimization problem:

$$v^*=\min\ v'Qv\ s.t.\ l_1(v)=n,\ v_i\in\{0,1\}$$

This suggest the folloing relaxation:

$$v^*=\min\ v'Qv\ s.t.\ l_1(v)=n,\ v_i\in[0,1]$$

which can be easily solved using off-the-shelf solvers; then the result is given by the largest $n$ components in $v^*$.

Sample matlab code:

N=100;
n=10;
% Generate random data
A=rand(N,1000);
C=corrcoef(A');
Q=abs((C+C')/2); % make sure it is symmetric
x = cplexqp(Q,zeros(1,N),[],[], ones(1, N),n, zeros(N,1), ones(N,1));
% If you don't use CPLEX, use matlab's default
% x = quadprog(Q,zeros(1,N),[],[], ones(1, N),n, zeros(N,1), ones(N,1));
assert(abs(sum(x)-n)<1e-10);
% Find the n largest values
I=sort(x);
v=zeros(size(x)); v(x>I(N-n))=1;
assert(abs(sum(v)-n)<1e-10);
% Make sure we do better than 10K random trials
for i=1:10000
vc=zeros(size(x)); vc(randperm(N,n))=1;
assert(sum(vc)==n, 'Wrong l0 norm');
assert(vc'*Q*vc>v'*Q*v, 'Improves result');
end
% Show results
J=find(v==1);
fprintf('The optimal solution total off-diagonal correlations are %1.3f\n', v'*Q*v-n);
fprintf('The matrix:\n');
C(J,J)


This may be worse than @ttnphns's hierarchical clustering idea. But: I just happened across a paper that uses $$\log \det(I + A)$$ as an increasing submodular objective function:

Vanchinathan, Marfurt, Robelin, Kossman, and Krause. Discovering Valuable Items from Massive Data. KDD 2015. (doi, arXiv)

If you think that's a reasonable measure of "least correlated", you can get within a $$1-1/e$$ factor of the optimal set by simply iteratively choosing the point that maximizes that. This can be done efficiently with the block LU decomposition, where $$v$$ is the vector of correlations to entries already in the matrix:

\begin{align*} \det \begin{bmatrix} I+A & v \\ v^T & 2 \end{bmatrix} &= \det \left( \begin{bmatrix} I & 0 \\ v^T (I+A)^{-1} & 1 \end{bmatrix} \begin{bmatrix} I+A & 0 \\ 0 & 2 - v^T (I+A)^{-1} v \end{bmatrix} \begin{bmatrix} I & (I+A)^{-1} v \\ 0 & 1 \end{bmatrix} \right) \\&= \det \begin{bmatrix} I & 0 \\ v^T (I+A)^{-1} & 1 \end{bmatrix} \det \begin{bmatrix} I+A & 0 \\ 0 & 2 - v^T (I+A)^{-1} v \end{bmatrix} \det \begin{bmatrix} I & (I+A)^{-1} v \\ 0 & 1 \end{bmatrix} \\&= (2 - v^T (I+A)^{-1} v) \det (I+A) \end{align*}

and of course you should compute $$v^T (I+A)^{-1} v = \lVert L^{-1} v \rVert^2$$, where $$L$$ is the Cholesky factorization of $$I + A$$ and using a triangular solver which is $$O(n^2)$$. So this whole process should take $$O( \sum_{k=1}^n N k^2 + k^3) = O( N n^3 )$$ time to pick $$n$$ out of $$N$$ elements, assuming the correlation matrix is already computed.

• It looks like the link to the paper is dead. Do you have a citation handy? – Sycorax Sep 23 '18 at 23:13
• @Sycorax It's available on the Wayback Machine, but I couldn't find a current copy on the web. It looks like that workshop paper was turned into a conference paper, which I'm adding to the answer. – Dougal Sep 24 '18 at 11:50

I'm not sure to fully understand what you mean by "I only care about pairwise correlation", but here's something that may help: use the invert of your correlation matrix. The $$A^{-1}_{ii}$$ term is equal to $$det(A_{0_i}) / det(A)$$, where $$A_{0_i}$$ is the $$(n-1)$$x$$(n-1)$$ matrix built from $$A$$ where the $$i$$-th column and line have been removed.

Getting the index of the minimum diagonal coefficient in $$A^{-1}$$ thus tells you what point has the lowest correlation to the remainder of the set.

Depending on what you actually want to do, you could either take the 10 lowest values on the diagonal of the invert, or get the first one, then compute the invert with the point deleted, and so on.

If this is not what you need, I feel like this trick might still be helpful, but I'm not sure how, though.

Find $k$ of $n$ items with the least pairwise correlation: Since a correlation of say $0.6$ explains $0.36$ of the relation between two series it makes more sense to minimize the sum of the squares of correlations for your target $k$ items. Here is my simple solution.

Rewrite your $n \times n$ matrix of correlations to a matrix of squares of correlations. Sum the squares of each column. Eliminate the column and corresponding row with the greatest sum. You now have a $(n−1)\times (n−1)$ matrix. Repeat until you have a $k\times k$ matrix. You could also just keep the columns and corresponding rows with the $k$ smallest sums. Comparing the methods, I found in a matrix with $n=43$ and $k=20$ that only two items with close sums were differently kept and eliminated.

• This might work, but it sounds ad hoc (it reads like a greedy algorithm) and you haven't offered any mathematical reasons that suggest it should work. Do you have any assurance it will work, or any bounds on how close it will get to the best solution? – whuber Feb 27 '18 at 23:58