An official website of the United States government
Hit-and-Run is a coordinate-free Gibbs sampler, yet the quantitative advantages of its coordinate-free property remain largely unexplored beyond empirical studies. In this paper, we prove sharp estimates for the Wasserstein contraction of Hit-and-Run in Gaussian target measures via coupling methods and conclude mixing time bounds. Our results uncover accelerated convergence rates in certain settings. Furthermore, we extend these insights to a coordinate-free variant of the randomized Kaczmarz algorithm, an iterative method for linear systems, and demonstrate analogous convergence rates. These findings offer new insights into the advantages and limitations of coordinate-free methods for both sampling and optimization.
more »
« less
Selectable Set Randomized Kaczmarz
Abstract The Randomized Kaczmarz method (RK) is a stochastic iterative method for solving linear systems that has recently grown in popularity due to its speed and low memory requirement. Selectable Set Randomized Kaczmarz is a variant of RK that leverages existing information about the Kaczmarz iterate to identify an adaptive “selectable set” and thus yields an improved convergence guarantee. In this article, we propose a general perspective for selectable set approaches and prove a convergence result for that framework. In addition, we define two specific selectable set sampling strategies that have competitive convergence guarantees to those of other variants of RK. One selectable set sampling strategy leverages information about the previous iterate, while the other leverages the orthogonality structure of the problem via the Gramian matrix. We complement our theoretical results with numerical experiments that compare our proposed rules with those existing in the literature.
more »
« less
- PAR ID:
- 10443812
- Publisher / Repository:
- Wiley Blackwell (John Wiley & Sons)
- Date Published:
- Journal Name:
- Numerical Linear Algebra with Applications
- Volume:
- 30
- Issue:
- 1
- ISSN:
- 1070-5325
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The randomized Kaczmarz methods are a popular and effective family of iterative methods for solving large-scale linear systems of equations, which have also been applied to linear feasibility problems. In this work, we propose a new block variant of the randomized Kaczmarz method, B-MRK, for solving linear feasibility problems defined by matrices. We show that B-MRK converges linearly in expectation to the feasible region. Furthermore, we extend the method to solve tensor linear feasibility problems defined under the tensor t-product. A tensor randomized Kaczmarz (TRK) method, TRK-L, is proposed for solving linear feasibility problems that involve mixed equality and inequality constraints. Additionally, we introduce another TRK method, TRK-LB, specifically tailored for cases where the feasible region is defined by linear equality constraints coupled with bound constraints on the variables. We show that both of the TRK methods converge linearly in expectation to the feasible region. Moreover, the effectiveness of our methods is demonstrated through numerical experiments on various Gaussian random data and applications in image deblurring.more » « less
-
The Kaczmarz algorithm is an iterative method for solving systems of linear equations. We introduce a randomized Kaczmarz algorithm for solving systems of linear equations in a distributed environment, i.e., the equations within the system are distributed over multiple nodes within a network. The modification we introduce is designed for a network with a tree structure that allows for passage of solution estimates between the nodes in the network. We demonstrate that the algorithm converges to the solution, or the solution of minimal norm, when the system is consistent. We also prove convergence rates of the randomized algorithm that depend on the spectral data of the coefficient matrix and the random control probability distribution. In addition, we demonstrate that the randomized algorithm can be used to identify anomalies in the system of equations when the measurements are perturbed by large, sparse noise.more » « less
-
The Wilson–Cowan model has been widely applied for the simulation of electroencephalography (EEG) waves associated with neural activities in the brain. The Runge–Kutta (RK) method is commonly used to numerically solve the Wilson–Cowan equations. In this paper, we focus on enhancing the accuracy of the numerical method by proposing a strategy to construct a class of fourth-order RK methods using a generalized iterated Crank–Nicolson procedure, where the RK coefficients depend on a free parameter c2. When c2 is set to 0.5, our method becomes a special case of the classical fourth-order RK method. We apply the proposed methods to solve the Wilson–Cowan equations with two and three neuron populations, modeling EEG epileptic dynamics. Our simulations demonstrate that when c2 is set to 0.4, the proposed RK4-04 method yields smaller errors compared to those obtained using the classical fourth-order RK method. This is particularly visible when the spectral radius of the connection matrix or the excitation-inhibition coupling coefficient is relatively large.more » « less
-
Abstract Fourier analysis is gaining popularity in image synthesis as a tool for the analysis of error in Monte Carlo (MC) integration. Still, existing tools are only able to analyse convergence under simplifying assumptions (such as randomized shifts) which are not applied in practice during rendering. We reformulate the expressions for bias and variance of sampling‐based integrators to unify non‐uniform sample distributions [importance sampling (IS)] as well as correlations between samples while respecting finite sampling domains. Our unified formulation hints at fundamental limitations of Fourier‐based tools in performing variance analysis for MC integration. At the same time, it reveals that, when combined with correlated sampling, IS can impact convergence rate by introducing or inhibiting discontinuities in the integrand. We demonstrate that the convergence of multiple importance sampling (MIS) is determined by the strategy which converges slowest and propose several simple approaches to overcome this limitation. We show that smoothing light boundaries (as commonly done in production to reduce variance) can improve (M)IS convergence (at a cost of introducing a small amount of bias) since it removesC0discontinuities within the integration domain. We also propose practical integrand‐ and sample‐mirroring approaches which cancel the impact of boundary discontinuities on the convergence rate of estimators.more » « less
