Quantile-based Random Kaczmarz for corrupted linear systems of equations
Quantile-based Random Kaczmarz for corrupted linear systems of equations
复制标题
用于损坏线性方程组的基于分位数的随机 Kaczmarz
DOI：
10.1093/imaiai/iaab029
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Steinerberger, Stefan
中科院分区：
文献类型：
--
作者：
Steinerberger, Stefan
我们考虑线性系统，其中包括规范化的行，，和其中多达项已损坏（可能是任意大的数字）。Haddock，Needell，Rebrova & Swartworth提出了一种基于分位数的Random Kaczmarz方法，并证明了对于某些随机矩阵，它以高似然收敛到真实解。我们证明了一个确定性的版本，构造，任何矩阵，一个numbersuch有收敛的所有扰动。假设一个随机矩阵启发式，这证明了高高斯矩阵的收敛性，最多可达腐败（一个数字，可能会得到改善）。
We consider linear systemswhereconsists of normalized rows,, and where up toentries ofhave been corrupted (possibly by arbitrarily large numbers). Haddock, Needell, Rebrova & Swartworth propose a quantile-based Random Kaczmarz method and show that for certain random matricesit converges with high likelihood to the true solution. We prove a deterministic version by constructing, for any matrix, a numbersuch that there is convergence for all perturbations with. Assuming a random matrix heuristic, this proves convergence for tall Gaussian matrices with up tocorruption (a number that can likely be improved).