☆ 4.7 Article

Regularized randomized iterative algorithms for factorized linear systems

APPLIED MATHEMATICS AND COMPUTATION (2024)

Related references

Note: Only part of the references are listed.

Article Mathematics

A randomised iterative method for solving factorised linear systems

Jing Zhao et al.

Summary: A new interlaced randomised iterative method is proposed in this paper for solving linear systems with large-scale coefficient matrices stored in factorised forms. The new method takes advantage of the factored form and avoids matrix multiplications. The convergence property is studied and theoretical analysis shows that it is linearly convergent. Numerical results are provided to confirm the effectiveness of the proposed method.

LINEAR & MULTILINEAR ALGEBRA (2023)

Add to Collection

Article Mathematics, Applied

Sparse sampling Kaczmarz-Motzkin method with linear convergence

Ziyang Yuan et al.

Summary: In this work, a greedy variant of the randomized sparse Kaczmarz method is introduced by employing the sampling Kaczmarz-Motzkin method, and its linear convergence in expectation with respect to the Bregman distance in noiseless and noisy cases is proved. This greedy variant can be seen as a unification of the sampling Kaczmarz-Motzkin method and the randomized sparse Kaczmarz method, inheriting the merits of both methods. Experimental results are presented to demonstrate its superiority.

MATHEMATICAL METHODS IN THE APPLIED SCIENCES (2022)

Add to Collection

Article Mathematics, Applied

Greedy Motzkin-Kaczmarz methods for solving linear systems

Yanjun Zhang et al.

Summary: The paper introduces the greedy randomized Motzkin-Kaczmarz (GRMK) method for solving linear systems using the greedy selection rule on maximum residual, along with a block version. Extensive numerical experiments show that the GRMK method performs similarly to the GRK method for dense matrices, but has better computing time for some sparse matrices and practical problems.

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS (2022)

Add to Collection

Article Mathematics, Applied

On two-subspace randomized extended Kaczmarz method for solving large linear least-squares problems

Wen-Ting Wu

Summary: The proposed two-subspace randomized extended Kaczmarz method is more efficient than the randomized extended Kaczmarz method and randomized coordinate descent method. The generalized two-subspace randomized Kaczmarz method provides a better upper bound for convergence rate than the two-subspace randomized Kaczmarz method, improving overall efficiency.

NUMERICAL ALGORITHMS (2022)

Add to Collection

Article Mathematics, Applied

Randomized block Kaczmarz methods with k-means clustering for solving large linear systems

Xiang-Long Jiang et al.

Summary: In this study, a randomized block Kaczmarz method based on k-means clustering is proposed, which selects the working block submatrix using a practical probability criterion. It is proven to converge when the linear system is consistent, and a practical variant is provided. Numerical examples are used to verify the effectiveness of the methods proposed.

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS (2022)

Add to Collection

Article Mathematics, Applied

Adaptively sketched Bregman projection methods for linear systems

Zi-Yang Yuan et al.

Summary: The sketch-and-project algorithm, a general method for solving linear systems, unifies various randomized iterative methods. However, it cannot include randomized sparse Kaczmarz algorithm since its goal is to find the least-norm solution. This leads to the proposal of a more general framework called sketched Bregman projection (SBP) method, which can find solutions with specific structures from linear systems. We provide detailed global convergence results for the SBP method with different adaptive sampling rules and demonstrate through numerical simulations that the Kaczmarz-Motzkin sampling rule has the lowest computational cost for achieving a given error bound compared to other sampling rules.

INVERSE PROBLEMS (2022)

Add to Collection

Article Mathematics, Applied

Faster randomized block sparse Kaczmarz by averaging

Lionel Tondji et al.

Summary: This study introduces a parallel (mini batch) version of the sparse Kaczmarz method, which computes solutions by averaging Kaczmarz steps. It is proven to have faster convergence compared to the standard method when parallel computations are utilized. Additionally, it can be viewed as a variant of other algorithms and has advantages such as estimating inconsistent systems and limiting convergence errors.

NUMERICAL ALGORITHMS (2022)

Add to Collection

Article Mathematics, Applied

Extended randomized Kaczmarz method for sparse least squares and impulsive noise problems

Frank Schoepfer et al.

Summary: This article introduces the combination of the Extended Randomized Kaczmarz method and the Sparse Randomized Kaczmarz method, proposing the Extended Sparse Randomized Kaczmarz method. The effectiveness of the method in handling noise problems is verified through numerical experiments.

LINEAR ALGEBRA AND ITS APPLICATIONS (2022)

Add to Collection

Article Computer Science, Artificial Intelligence

Regularized Kaczmarz Algorithms for Tensor Recovery

Xuemei Chen et al.

Summary: This paper proposes a novel algorithmic framework for tensor recovery based on the Kaczmarz algorithm, with thorough convergence analysis and demonstrations of potential in various tensor recovery applications.

SIAM JOURNAL ON IMAGING SCIENCES (2021)

Add to Collection

Article Mathematics, Applied

RANDOMIZED EXTENDED AVERAGE BLOCK KACZMARZ FOR SOLVING LEAST SQUARES

Kui Du et al.

SIAM JOURNAL ON SCIENTIFIC COMPUTING (2020)

Add to Collection

Article Computer Science, Software Engineering

Linear convergence of the randomized sparse Kaczmarz method

Frank Schoepfer et al.

MATHEMATICAL PROGRAMMING (2019)

Add to Collection

Article Mathematics, Applied

Tight upper bounds for the convergence of the randomized extended Kaczmarz and Gauss-Seidel algorithms

Kui Du

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS (2019)

Add to Collection

Article Mathematics, Applied

On greedy randomized coordinate descent methods for solving large linear least-squares problems

Zhong-Zhi Bai et al.

NUMERICAL LINEAR ALGEBRA WITH APPLICATIONS (2019)

Add to Collection

Article Mathematics, Applied

FASTER RANDOMIZED BLOCK KACZMARZ ALGORITHMS

Ion Necoara

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS (2019)

Add to Collection

Article Mathematics, Applied

ITERATIVE METHODS FOR SOLVING FACTORIZED LINEAR SYSTEMS

Anna Ma et al.

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS (2018)

Add to Collection

Article Mathematics, Applied

ON GREEDY RANDOMIZED KACZMARZ METHOD FOR SOLVING LARGE SPARSE LINEAR SYSTEMS

Zhong-Zhi Bai et al.

SIAM JOURNAL ON SCIENTIFIC COMPUTING (2018)

Add to Collection

Article Mathematics, Applied

LINEAR CONVERGENCE OF DESCENT METHODS FOR THE UNCONSTRAINED MINIMIZATION OF RESTRICTED STRONGLY CONVEX FUNCTIONS

Frank Schoepfer

SIAM JOURNAL ON OPTIMIZATION (2016)

Add to Collection

Article Mathematics, Applied

Paved with good intentions: Analysis of a randomized block Kaczmarz method

Deanna Needell et al.

LINEAR ALGEBRA AND ITS APPLICATIONS (2014)

Add to Collection

Article Computer Science, Artificial Intelligence

Augmented l(1) and Nuclear-Norm Models with a Globally Linearly Convergent Algorithm

Ming-Jun Lai et al.

SIAM JOURNAL ON IMAGING SCIENCES (2013)

Add to Collection

Article Mathematics, Applied

RANDOMIZED EXTENDED KACZMARZ FOR SOLVING LEAST SQUARES

Anastasios Zouzias et al.

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS (2013)

Add to Collection

Article Mathematics, Applied

EFFICIENCY OF COORDINATE DESCENT METHODS ON HUGE-SCALE OPTIMIZATION PROBLEMS

Yu Nesterov

SIAM JOURNAL ON OPTIMIZATION (2012)

Add to Collection

Article Operations Research & Management Science

Randomized Methods for Linear Constraints: Convergence Rates and Conditioning

D. Leventhal et al.

MATHEMATICS OF OPERATIONS RESEARCH (2010)

Add to Collection

Article Mathematics, Applied

A Randomized Kaczmarz Algorithm with Exponential Convergence

Thomas Strohmer et al.

JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS (2009)

Add to Collection

© Peeref 2019-2024. All rights reserved.