Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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 2

up vote 7 down vote accepted

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.

share|improve this answer
    
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 problem that appears to be related, 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). 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. The interesting feature is that in this way the matrix $S^{-1}V$ has a submatrix equal to the identity matrix (obvious) and all other entries bounded in modulus by 1. This is enough to ensure good conditioning, at least in the applications that we were investigating. One can prove that the rows of the matrix $V$ are a well-conditioned basis for its row space, for instance. Another reference is this paper.
  • 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 within $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.
share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.