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 similar problem, 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). At first sight, it may seem that the two problems are not related, but one can prove that if $S$ has this property then $S^{1}V$ has all entries bounded in modulus by 1. This is enough to ensure some form of stability, at least in the applications that we were investigating, and I suspect that yours case might be similar. Other useful references are this paper and this one. I can tell you the following.


