I have an $n \times m$ matrix of data $\mathbf{D}$ as well as a $k$-partition $P$ of $n$ indices each representing a row in a dataset. Assuming an arbitrary clustering algorithm $A$, I would like to find a subset $F$ of $\{1,\ldots, m\}$, representing indices of the columns of $D$, such that applying $A$ to only the columns indexed by $F$, an $n \times |F|$ matrix, minimizes the average variation of information (VI) between $P$ and the output of $A$. Another way of saying this is that I would like to be able to find the subspace on which $\mathbf{D}$ is most informative about $P$.
(That the metric is VI or that the statistic taken over multiple runs is an average is not necessarily important. I'm looking for a general solution, but if a solution that specifies either the metric or the clustering algorithm exists, I'd be interested.)
Attempting to build the distribution of (normalized) variation of information values by brute force is not practical since the number of possible subsets of $\{1,\ldots, m\}$ is the Stirling number (of the second kind) $S(m, 2)$, which obviously gets monstrous as $m$ gets to any interesting size.
