Finding most informative feature subsets given dataset, clustering algorithm and gold standard partition

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.

-
 I have the feeling that this question might also be appropriate for stats.stackexchange.com – Thomas Klimpel Sep 28 '12 at 9:07

This problem is called subset selection and is nowadays usually solved by appropriate nonsmooth convex optimization techniques.

Two recent papers describing subset selection methods are
http://users.cms.caltech.edu/~jtropp/reports/Tro04-Just-Relax-TR.pdf
http://automatica.dei.unipd.it/public/Schenato/PSC/2010_2011/gruppo4-Building_termo_identification/Bibliografia%20Casuale/Sensor%20Selection%20via%20Convex%20Optimization.pdf
but this is just the tip of an iceberg.

-