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.



Optimizing the condition number
*Update*: [This recent paper](http://arxiv.org/abs/1509.00748) 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 ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 978-986, New York, NY, Jan. 2009.* [SODA .pdf](http://users.cms.caltech.edu/%7Ejtropp/conf/Tro09-Column-Subset-SODA.pdf) or a [longer arXiv version](https://arxiv.org/abs/0806.4404).


From the abstract:



> 
> Most research from the algorithms and numerical linear algebra communities focuses on a variant called rank-revealing QR, which seeks a well-conditioned collection of columns that spans the (numerical) range of the matrix.
> 
> 
> ....
> 
> 
> a celebrated result of Bourgain and Tzafriri demonstrates that each matrix with normalized columns contains a large column submatrix that is exceptionally well conditioned. Unfortunately, standard proofs of this result cannot be regarded as algorithmic. This paper presents a randomized, polynomial-time algorithm that produces the submatrix promised by Bourgain and Tzafriri.
> 
> 
> 


