Recovering a signal $x^\ast \in \mathbb{R}^n$ from a sequence of linear measurements is an important problem in areas such as computerized tomography and compressed sensing. In this work, we consider an online setting in which measurements are sampled one-by-one from some source distribution. We propose solving this problem with a variant of the Kaczmarz method with an additional heavy ball momentum term. A popular technique for solving systems of linear equations, recent work has shown that the Kaczmarz method also enjoys linear convergence when applied to random measurement models, however convergence may be slowed when successive measurements are highly coherent. We demonstrate that the addition of heavy ball momentum may accelerate the convergence of the Kaczmarz method when data is coherent, and provide a theoretical analysis of the method culminating in a linear convergence guarantee for a wide class of source distributions.
翻译:从一系列线性测量中恢复一个信号$x ⁇ ast\ in\mathbb{R ⁇ n$,这是计算机断层摄影和压缩感测等领域的一个重要问题。在这项工作中,我们考虑建立一个在线环境,从某些来源分布中逐个抽样测量。我们建议用卡茨马兹法的变体来解决这个问题,并增加一个重球动力术语。一种解决线性方程式系统的流行技术,最近的工作表明,卡茨马兹法在应用随机测量模型时也享有线性趋同,但相继测量高度一致时,趋同速度可能会放慢。我们证明,在数据一致时,重球动力的增加可能会加速卡茨马兹方法的趋同速度,并对方法进行理论分析,最终为广泛的源分布提供线性趋同保证。