Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ 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.

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.

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ 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 large as possible -- notice that this is trivial if $S$ does not span $W,$ since the condition number is always $0,$ 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.

Suppose I have a set $S$ of $N$ vectors in $W=\mathbb{R}^m,$ with $N \gg n.$ 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.