Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg m.$ I want to choose a subset $\{v_1, \dots, v_m\}$ of $S$ in such a way that the condition number of the matrix with columns $v_1, \dotsc, v_m$ is as small as possible  notice that this is trivial if $S$ does not span $W,$ since the condition number is always $\infty,$ so we can assume that $S$ does span. The question is: is there a better algorithm than the obvious $O(N^{m+c})$ algorithm (where we look at all the $m$element subsets of $S?$). and how much better? One might guess that there is an algorithm polynomial in the input size, but none jumps to mind.

Update: This recent paper on this topic may also be of interest; it's quite short and claims to have a fully constructive approach. I think the closest to answering your question is the following paper. "Column subset selection, matrix factorization, and eigenvalue optimization", by J. A. Tropp. In Proc. 2009 ACMSIAM Symp. Discrete Algorithms (SODA), pp. 978986, New York, NY, Jan. 2009. SODA .pdf or a longer arXiv version. From the abstract:



I have been working recently on a problem that appears to be related, namely, maximizing the absolute value of the determinant of a chosen $m\times m$ submatrix $S$ of a $m\times N$ submatrix $V$ (think to the columns of $V$ as your vectors). I can tell you the following.


