迭代求解线性系统的细粒度分析与更快算法
原文中文,约400字,阅读约需1分钟。发表于: 。通过调研迭代方法在解决大型线性方程组时受到问题特定条件数量的显著影响,文中提出了一种称为谱尾条件数的复杂性概念,并通过 Sketch-and-Project with Nesterov's acceleration 算法保证了在给定矩阵和向量的情况下,在准确性为 ε 时的时间复杂度为 O ((kappa_l*n^2*log (1/ε)),其中 kappa_l...
本文介绍了一种解决大型线性方程组的新方法,利用谱尾条件数和Sketch-and-Project with Nesterov's acceleration算法,时间复杂度为O((kappa_l*n^2*log(1/ε))。同时,还研究了随机投影矩阵的特性。