16
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$ Aug 16, 2012 at 1:13
  • $\begingroup$ @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...$)? $\endgroup$
    – Suvrit
    Aug 16, 2012 at 6:45
  • $\begingroup$ @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. $\endgroup$ Aug 16, 2012 at 7:39
  • $\begingroup$ sorry, I meant "inverse of the condition number", not "reverse". $\endgroup$ Aug 16, 2012 at 9:06
  • $\begingroup$ @Federico and @Suvrit: of course you are right, I want SMALL condition numbers. Will fix. $\endgroup$
    – Igor Rivin
    Aug 16, 2012 at 13:12

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is VERY close to what I am looking for, thanks! $\endgroup$
    – Igor Rivin
    Aug 16, 2012 at 16:35
5
$\begingroup$

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.
$\endgroup$
1
  • $\begingroup$ 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...] $\endgroup$
    – Igor Rivin
    Aug 16, 2012 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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