Random multipliers numerically stabilize Gaussian and block Gaussian elimination: Proofs and an extension to low-rank approximation ☆
Random multipliers numerically stabilize Gaussian and block Gaussian elimination: Proofs and an extension to low-rank approximation ☆
复制标题
随机乘法器在数值上稳定高斯和块高斯消除：证明和低阶近似的扩展☆
DOI：
10.1016/j.laa.2015.04.021
复制
发表时间：
2014
影响因子：
1.1
通讯作者：
Xiaodong Yan
中科院分区：
文献类型：
--
作者：
V. Pan;G. Qian;Xiaodong Yan
我们研究了标准高斯随机乘子的两个应用。首先，我们证明了在概率接近1的情况下，这样的乘子有望在数值上稳定不旋转的高斯消元以及块高斯消元。然后，通过扩展我们的分析，我们证明了这样的乘子也有望支持矩阵的低阶逼近，而不需要惯常的过采样。我们的测试结果与这项正式研究很好地一致。当我们用随机循环或Toeplitz乘子代替高斯乘子时，结果仍然是相似的，它们涉及的随机参数更少，可以实现更快的乘法。我们形式上支持随机结构乘子应用于逼近的观察到的效率，但我们仍然在消除的情况下继续我们的研究。我们指定了一类狭义的么正输入，对于它，没有枢轴的高斯消元是数值不稳定的，然后证明了，在概率接近1的情况下，高斯随机循环乘子不能解决这类输入的数值稳定性问题。我们还证明了如果也包括随机置换，则随机循环预处理的能力增加。
We study two applications of standard Gaussian random multipliers. At first we prove that with a probability close to 1 such a multiplier is expected to numerically stabilize Gaussian elimination with no pivoting as well as block Gaussian elimination. Then, by extending our analysis, we prove that such a multiplier is also expected to support low-rank approximation of a matrix without customary oversampling. Our test results are in good accordance with this formal study. The results remain similar when we replace Gaussian multipliers with random circulant or Toeplitz multipliers, which involve fewer random parameters and enable faster multiplication. We formally support the observed efficiency of random structured multipliers applied to approximation, but we still continue our research in the case of elimination. We specify a narrow class of unitary inputs for which Gaussian elimination with no pivoting is numerically unstable and then prove that, with a probability close to 1, a Gaussian random circulant multiplier does not fix numerical stability problems for such inputs. We also prove that the power of the random circulant preprocessing increases if we also include random permutations.