Semi-optimal bases for linear dependencies
Semi-optimal bases for linear dependencies
复制标题
线性依赖的半最优基
DOI：
--
复制
发表时间：
1985
期刊：
影响因子：
--
通讯作者：
D. E. Knuth
中科院分区：
文献类型：
--
作者：
D. E. Knuth
令A为真实或复数的M×N矩阵，让μ为给定常数≥1。如果A具有秩M，则可以选择A的M列，如果B为M×M由这些M列形成的基质，B -1 A的所有条目在绝对值中都小于或等于μ，如果μ> 1，则可以在M中找到M的多项式中的多项列。和n，与logμ成反比。
Let A be an m × n matrix of real or complex numbers, and let μ. be a given constant ≥ 1. If A has rank m, it is possible to choose m columns of A such that, if B is the m × m matrix formed by these m columns, all entries of B −1 A are less than or equal to μ in absolute value. Moreover, if μ > 1, it is possible to find m such columns in a number of steps that is polynomial in m and n and inversely proportional to log μ.