# Optimizing the condition number

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.

-
I don't know of anything theoretically better. Something that should work in practice is to do Gram Schmidt orthogonalization: when you choose the largest m/2 vectors and orthogonalize the rest, it makes sense to choose the longer of the remaining processed vectors to reach your goal. That should prune a lot of the search space. (I am assuming condition number is related to determinant.) Gerhard "Ask Me About System Design" Paseman, 2012.08.15 – Gerhard Paseman Aug 16 '12 at 1:13
@Igor: The condition number of any matrix is always $\ge 1$, using a consistent norm, so am I misreading your question (because you say "...condition number is always 0...$)? – Suvrit Aug 16 '12 at 6:45 @Igor: given Suvrit's remark, maybe you were thinking about the reverse condition number when writing? Typically people want to get small condition numbers, not large ones. – Federico Poloni Aug 16 '12 at 7:39 sorry, I meant "inverse of the condition number", not "reverse". – Federico Poloni Aug 16 '12 at 9:06 @Federico and @Suvrit: of course you are right, I want SMALL condition numbers. Will fix. – Igor Rivin Aug 16 '12 at 13:12 ## 2 Answers 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 ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 978-986, New York, NY, Jan. 2009. SODA .pdf or a longer arXiv version. 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. - This is VERY close to what I am looking for, thanks! – Igor Rivin Aug 16 '12 at 16:35 You are welcome! – Suvrit Aug 16 '12 at 16:36 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. • Finding the maximum volume submatrix is an NP-hard problem, so I guess that your problem may suffer the same fate • a useful relaxation, however, is finding a submatrix that has locally maximum volume, i.e., larger than all those that can be obtained by changing one vector only. There is a paper by Knuth (yes, that Knuth) that studies the problem. • a second relaxation is finding a submatrix$S$such that$S^{-1}V$has all entries bounded by some real$\tau>1$. This problem can be solved explicitly in$O(Nm^2\frac{\log m}{\log\tau})$. The good conditioning properties carry over to this relaxation, up to a factor$\tau$. Putting everything together, I think that one can prove using the techniques in our paper that the matrix chosen by the algorithm has conditioning which differs by at most a factor$O(\sqrt{Nm}\tau)$from the conditioning of the rectangular matrix$V$(defined as largest over smallest singular value), which is a theoretical maximum for the conditioning of$S\$ (I think).
• if you have a practical computation and you want to check how things work with this solution, I have some Matlab code in a packaged and usable state that you might wish to try out. Feel free to ask for explanation if the documentation is too poor.
-
Thanks much! I will certainly check out the references and the code -- it does sound very relevant [not exactly clear what the precise connection is, but...] – Igor Rivin Aug 16 '12 at 14:27