论文标题
线性系统以通用速率的近似解决方案
Approximate Solutions of Linear Systems at a Universal Rate
论文作者
论文摘要
令$ a \ in \ mathbb {r}^{n \ times n} $是可逆的，$ x \ in \ mathbb {r}^n $ unknown和$ b = ax $给定。我们对近似解决方案感兴趣：vectors $ y \ in \ mathbb {r}^n $，这样$ \ | ay -b \ | $很小。我们证明，对于所有$ 0 <\ varepsilon <1 $，$ k $正交的投影在由$ a $ a $的行产生的$ n $超平面上，其中$$ k \ leq 2 \ log \ log \ left（\ frac {\ frac {1}} \ varepsilon^{2}} $$将原点映射到\ mathbb {r}^n $满足$ \ |的vector $ y \ y \ y -ax \ | \ leq \ varepsilon \ cdot \ | a \ | \ cdot \ | x \ | $。我们注意到，$ k $的上限与矩阵$ a $无关。从某种意义上说，此过程是稳定的。 \ leq 2 \ | x \ | $。存在证明是基于对随机kaczmarz方法的概率精制分析，该分析在求解$ a x = b $的较高可能性时似乎可以达到此速率。
Let $A \in \mathbb{R}^{n \times n}$ be invertible, $x \in \mathbb{R}^n$ unknown and $b =Ax $ given. We are interested in approximate solutions: vectors $y \in \mathbb{R}^n$ such that $\|Ay - b\|$ is small. We prove that for all $0< \varepsilon <1 $ there is a composition of $k$ orthogonal projections onto the $n$ hyperplanes generated by the rows of $A$, where $$k \leq 2 \log\left(\frac{1}{\varepsilon} \right) \frac{ n}{ \varepsilon^{2}}$$ which maps the origin to a vector $y\in \mathbb{R}^n$ satisfying $\| A y - Ax\| \leq \varepsilon \cdot \|A\| \cdot \| x\|$. We note that this upper bound on $k$ is independent of the matrix $A$. This procedure is stable in the sense that $\|y\| \leq 2\|x\|$. The existence proof is based on a probabilistically refined analysis of the Random Kaczmarz method which seems to achieve this rate when solving for $A x = b$ with high likelihood.
