Extension of an error analysis of the randomized Kaczmarz method for inconsistent linear systems

• Morijiri Yushi

  Graduate School of Information Science and Technology, The University of Tokyo

• Aishima Kensuke

  Graduate School of Information Science and Technology, The University of Tokyo

• Matsuo Takayasu

  Graduate School of Information Science and Technology, The University of Tokyo

抄録

In 2015, Gower and Richtárik presented a unifying framework for a variety of randomized iterative algorithms for consistent linear systems. The framework includes the randomized Kaczmarz method that exponentially converges in the mean square whenever the system is consistent. For noisy linear systems corresponding to inconsistent systems, the randomized Kaczmarz method computes an approximate solution within a fixed distance depending on the norm of the noise vector. We extend this error analysis to a general framework in inconsistent systems in a similar manner to Gower and Richtárik, and verify this theoretical analysis in numerical experiments.

収録刊行物

• JSIAM Letters

  JSIAM Letters 10 (0), 17-20, 2018

  一般社団法人 日本応用数理学会

キーワード

• inconsistent linear systems
• iterative methods
• randomized algorithms
• randomized Kaczmarz
• randomized coordinate descent

詳細情報

• CRID: 1390564238017320192
• NII論文ID: 130007404199
• DOI: 10.14495/jsiaml.10.17
• ISSN: 18830617
• ISSN: 18830609
• Web Site: https://www.jstage.jst.go.jp/article/jsiaml/10/0/10_17/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可