# Row subset selection of matrix to optimize condition number

Given a matrix $\mathbf{A} \in \mathbb{C}^{N\times M}$ with $N \gg M$. This matrix results from a linear equation system and has a certain structure (however, I do not think that details provide any advantages).

This matrix should be solved via LS using $L \gt M \ll N$ rows. Choosing a consecutive set of rows results in a terribly defined matrix (huge condition nr.) but selecting the rows at random seems to give good results. Is there a way to figure out the best possible rows for minimum condition nr without $\mathcal{O}(N^M)$?

I found the same question regarding columns and the reference to Tropp's paper here: Optimizing the condition number. Is there something similar for the case of rows? Does the same apply if I just transpose $\mathbf{A}$ or is this misleading?

-
I would like to add here that I tried solving the problem by the fact that a more stable matrix should have its column vectors more linearly independent. So I could iterate over all possible sets of rows and select the subset whose column vectors have the smallest normalized dot-product (=column vectors are as close to 90 degree as possible). Since I know the structure of the matrix $a_{ij} = f(i,j)$ I would be able to determine the best row-subset. However, I am not sure if I am on the right track with that. Can anyone comment on this? Thanks! – divB Feb 17 '14 at 2:02