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.
 A: 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)

A: 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.
A: 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.
A: 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.
