Dykstras algorithm with bregman projections: A convergence proof
From MaRDI portal
Dykstra's algorithm and the method of cyclic Bregman projections are often employed to solve best approximation and convex feasibility problems, which are fundamental in mathematics and the physical sciences. [\textit{Y. Censor} and \textit{S. Reich}, Commun. Appl. Anal. 2, 407-419 (1998; Zbl 0897.90155)] very recently suggested a synthesis of these methods, Dykstra's algorithm with Bregman projections, to tackle a nonorthogonal best approximation problem. They obtained convergence when each constraint is a halfspace. It is shown here that this new algorithm works for general closed convex constraints; this complements Censor and Reich's result and relates to a framework by [\textit{P. Tseng}, Math. Program. 59 A, 231-247 (1993; Zbl 0782.90073)]. The proof rests on original work [\textit{J. P. Boyle} and \textit{R. L. Dykstra}, Advances in Order Restricted Statistical Inference, Lect. Notes Stat. 37, 28-47 (1986; Zbl 0603.49024)] and on strong properties of Bregman distances corresponding to Legendre functions. Special cases and observations simplifying the implementation of the algorithm are also discussed.
Recommendations
- scientific article; zbMATH DE number 1393068
- The rate of convergence of dykstra's cyclic projections algorithm: The polyhedral case
- On Dykstra's algorithm: finite convergence, stalling, and the method of alternating projections
- Two generalizations of Dykstra's cyclic projections algorithm
- scientific article; zbMATH DE number 1174325
Cites work
- A cyclic projection algorithm via duality
- A multiprojection algorithm using Bregman projections in a product space
- A relaxed version of Bregman's method for convex programming
- A successive projection method
- An Algorithm for Restricted Least Squares Regression
- An Alternating Projection Algorithm for Computing the Nearest Euclidean Distance Matrix
- An alternating projections method for certain linear problems in a Hilbert space
- An iterative row-action method for interval convex programming
- Approximate iterations in Bregman-function-based proximal algorithms
- Block-iterative surrogate projection methods for convex feasibility problems
- Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions
- Convergence of Bregman projection methods for solving consistent convex feasibility problems in reflexive Banach spaces
- Dual coordinate ascent methods for non-strictly convex minimization
- Dykstra's Algorithm for a Constrained Least-squares Matrix Problem
- Dykstra's alternating projection algorithm for two sets
- Entropic Proximal Mappings with Applications to Nonlinear Programming
- Free-Steering Relaxation Methods for Problems with Strictly Convex Costs and Linear Constraints
- Generalized Bregman projections in convex feasibility problems
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- Iterations of paracontractions and firmaly nonexpansive operators with applications to feasibility and optimization
- Iterative averaging of entropic projections for solving stochastic convex feasibility problems
- Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming
- On a proximal point method for convex optimization in banach spaces
- On Projection Algorithms for Solving Convex Feasibility Problems
- On the convergence of Han's method for convex programming with quadratic objective
- Proximal Minimization Methods with Generalized Bregman Functions
- The rate of convergence of dykstra's cyclic projections algorithm: The polyhedral case
Cited in
(42)- A multiprojection algorithm using Bregman projections in a product space
- Finding the projection of a point onto the intersection of convex sets via projections onto half-spaces.
- A multi-objective interpretation of optimal transport
- Generalized incompressible flows, multi-marginal transport and Sinkhorn algorithm
- Convergence of sequential parafirmly nonexpansive mappings in reflexive Banach spaces
- Monotonically convergent algorithms for symmetric tensor approximation
- On Dykstra's algorithm: finite convergence, stalling, and the method of alternating projections
- Bivariate rational approximations of the general temperature integral
- Bregman proximal mappings and Bregman-Moreau envelopes under relative prox-regularity
- Bregman distances, totally convex functions, and a method for solving operator equations in Banach spaces
- Computational acceleration of projection algorithms for the linear best approximation problem
- An efficient implementable inexact entropic proximal point algorithm for a class of linear programming problems
- Low complexity regularization of linear inverse problems
- Scaling algorithms for unbalanced optimal transport problems
- Entropic approximation of Wasserstein gradient flows
- scientific article; zbMATH DE number 1208852 (Why is no real title available?)
- scientific article; zbMATH DE number 1174325 (Why is no real title available?)
- Construction of best Bregman approximations in reflexive Banach spaces
- Regularized optimal transport and the rot mover's distance
- Regularizing with Bregman-Moreau envelopes
- Generalized Sinkhorn iterations for regularizing inverse problems using optimal mass transport
- scientific article; zbMATH DE number 1393068 (Why is no real title available?)
- Multimarginal Optimal Transport with a Tree-Structured Cost and the Schrödinger Bridge Problem
- scientific article; zbMATH DE number 7523740 (Why is no real title available?)
- The extension of the linear inequality method for generalized rational Chebyshev approximation to approximation by general quasilinear functions
- Multivariate approximation by polynomial and generalized rational functions
- Prediction in Riemannian metrics derived from divergence functions
- Quantum entropic regularization of matrix-valued optimal transport
- Iterative Bregman projections for regularized transportation problems
- Convergence of entropic schemes for optimal transport and gradient flows
- An algorithmic proof of Brégman–Minc theorem
- Bregman-Golden ratio algorithms for variational inequalities
- Provable Phase Retrieval with Mirror Descent
- Convergence Rate Analysis of a Dykstra-Type Projection Algorithm
- Approximation of fixed points of weak Bregman relatively nonexpansive mappings in Banach spaces
- Proof mining for the dual of a Banach space with extensions for uniformly Fréchet differentiable functions
- An iterated projection approach to variational problems under generalized convexity constraints
- Computation of Cournot-Nash equilibria by entropic regularization
- The football model, stochastic ordering and martingale transport
- Remap for ALE Hydrodynamics via Direct Interpolation and Constraint Optimization
- Minimization of Tikhonov functionals in Banach spaces
- Klee sets and Chebyshev centers for the right Bregman distance
This page was built for publication: Dykstras algorithm with bregman projections: A convergence proof
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2709445)
