How to find a subset of a matrix that has minimum condition number?

Suppose matrix A is consist of M column vectors, how can we find a subset B, consisting of N column of A (N<M), that has minimum condition number (the ratio of maximum singular value by minimum singular value)? If we try all possible combination of columns in A, the amount is tremendous， for example if M = 100, N = 50, there is 10^29 combinations. So is there a faster algorithm?

Answer 1

[Torsten]

Maybe of interest for you:

http://mathoverflow.net/questions/104803/optimizing-the-condition-number

http://www.cs.rpi.edu/~magdon/ps/journal/MaxVolTCS.pdf

Best wishes

Torsten.

[Qiu]

Thank you so much, but these papers are difficult for me to comprehend, as I am not major in algebra or mathematics. I encounter this question on the works of Spectrum Estimation of Camera. So it will be appreciate if there exists prepared toolbox.

[Torsten]

I think one should consult the papers first to find out whether a faster algorithm than the obvious one you suggested exists. If this question is answered positive, one can search for MATLAB implementations.

Best wishes

Torsten.