Exact convergence rates of alternating projections for nontransversal intersections

DOI10.1007/S13160-023-00584-9MaRDI QIDQ6179912zbMATH OpenOpenAlexFDO

Authors Hiroyuki Ochiai, Yoshiyuki Sekiguchi, Hayato Waki

Publication date 18 January 2024

Published in Japan Journal of Industrial and Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.06026

zbMATH Keywords

alternating projection methodbasic semialgebraic convex setexact convergence ratemultiplicitynontransversal intersectionŁojasiewicz exponent

Mathematics Subject Classification ID

Rate of convergence, degree of approximation (41A25) Numerical optimization and variational techniques (65K10) Convex programming (90C25)

Abstract: We consider the convergence rate of the alternating projection method for the nontransversal intersection of a semialgebraic set and a linear subspace. For such an intersection, the convergence rate is known as sublinear in the worst case. We study the exact convergence rate for a given semialgebraic set and an initial point, and investigate when the convergence rate is linear or sublinear. As a consequence, we show that the exact rates are expressed by multiplicities of the defining polynomials of the semialgebraic set, or related power series in the case that the linear subspace is a line, and we also decide the convergence rate for given data by using elimination theory. Our methods are also applied to give upper bounds for the case that the linear subspace has the dimension more than one. The upper bounds are shown to be tight by obtaining exact convergence rates for a specific semialgebraic set, which depend on the initial points.

Recommendations

• Transversality and alternating projections for nonconvex sets
• Alternating Projections on Manifolds
• Local linear convergence for inexact alternating projections on nonconvex sets
• A note on the finite convergence of alternating projections
• Local linear convergence for alternating and averaged nonconvex projections

Cites work

• A factorization method for completely positive matrices
• A note on alternating projections for ill-posed semidefinite feasibility problems
• Alternating Projections on Manifolds
• Analysis of the convergence rate for the cyclic projection algorithm applied to basic semialgebraic convex sets
• Computation of the Łojasiewicz exponent of nonnegative and nondegenerate analytic functions
• Ideals, Varieties, and Algorithms
• Low-order control design for LMI problems using alternating projection methods
• On Projection Algorithms for Solving Convex Feasibility Problems
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• Separation of real algebraic sets and the Łojasiewicz exponent
• Set regularities and feasibility problems
• Some applications of the Łojasiewicz gradient inequality
• The method of projections for finding the common point of convex sets
• Variational Analysis

Cited in

(3)

• Analytic formulas for alternating projection sequences for the positive semidefinite cone and an application to convergence analysis
• Convergence rate of alternating projection method for the intersection of an affine subspace and the second-order cone
• Expansions of the characteristic polynomial of a perturbed PSD matrix and convergence analysis of alternating projections for the PSD cone and a line

This page was built for publication: Exact convergence rates of alternating projections for nontransversal intersections

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6179912)