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?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ 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. $\endgroup$– jqx1991Commented Jan 8, 2016 at 13:39
-
$\begingroup$ In my answer to the duplicate question, I have a link to a Matlab toolbox (written by me) that solves a similar problem, namely, it finds a $m\times m$ submatrix $B$ of a $m\times n$ matrix $A$ such that $B^{-1}A$ has all entries bounded by 1. In my application at least, this property is sufficient to get good numerical properties. It should also possible to bound explicitly $\kappa(B)/\kappa(A)$. $\endgroup$– Federico PoloniCommented Jan 8, 2016 at 13:47
Add a comment
|