Alternating projections on nontangential manifolds

DOI10.1007/S00365-013-9213-3zbMATH Open1283.41026arXiv1107.4055OpenAlexW2074065373MaRDI QIDQ387545FDOQ387545

Authors: Fredrik Andersson, Marcus Carlsson 

Publication date: 23 December 2013

Published in: Constructive Approximation (Search for Journal in Brave)

Abstract: We consider sequences $(B_k{)}_{k=0}^{i}nfty$ of points obtained by projecting back and forth between two manifolds $M_1$ and $M_2$, and give conditions guaranteeing that the sequence converge to a limit $B_{i}nftyin{M}_{1}cap{M}_2$. Our motivation is the study of algorithms based on finding the limit of such sequences, which have proven useful in a number of areas. The intersection is typically a set with desirable properties, but for which there is no efficient method of finding the closest point $B_{opt}$ in $M_{1}cap{M}_2$. We prove not only that the sequence of alternating projections converges, but that the limit point is fairly close to $B_{opt}$, in a manner relative to the distance $|B_0-B_{opt}|$, thereby significantly improving earlier results in the field. A concrete example with applications to frequency estimation of signals is also presented.

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

Recommendations

• Alternating Projections on Manifolds
• Relaxed Alternating Projection Methods
• Transversality and alternating projections for nonconvex sets
• Local linear convergence of alternating projections in metric spaces with bounded curvature
• Local linear convergence for alternating and averaged nonconvex projections

zbMATH Keywords

algorithmsalternating projectionsrate of convergencelow-rank approximationmetric projectionreal algebraic varietysmooth manifold

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Abstract approximation theory (approximation in normed linear spaces and other abstract spaces) (41A65) Contraction-type mappings, nonexpansive mappings, (A)-proper mappings, etc. (47H09) Applications of operator theory in optimization, convex analysis, mathematical programming, economics (47N10) Semialgebraic sets and related spaces (14P10)

Cites Work

• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Computing the nearest correlation matrix--a problem from finance
• Solving semidefinite-quadratic-linear programs using SDPT3
• Error bounds for the method of alternating projections
• Distributed optimization and statistical learning via the alternating direction method of multipliers
• The rate of convergence for the method of alternating projections. II
• Variational Analysis
• On Projection Algorithms for Solving Convex Feasibility Problems
• Title not available (Why is that?)
• Efficient rank reduction of correlation matrices
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
• Elliptic partial differential equations of second order
• On the convergence of von Neumann's alternating projection algorithm for two sets
• The analysis of linear partial differential operators. III: Pseudo-differential operators
• Distance to \(C^k\) hypersurfaces
• On the implementation and usage of SDPT3 -- a Matlab software package for semidefinite-quadratic-linear programming, version 4.0
• Title not available (Why is that?)
• The method of alternating projections and the method of subspace corrections in Hilbert space
• Title not available (Why is that?)
• Title not available (Why is that?)
• The method of projections for finding the common point of convex sets
• Functional Operators (AM-22), Volume 2
• The measure of the critical values of differentiable maps
• Algorithms in real algebraic geometry
• Best approximation in inner product spaces
• A generalization of the Friedrichs angle and the method of alternating projections
• An Algorithm for Restricted Least Squares Regression
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear algebra and its applications
• Structured low-rank approximation and its applications
• Signal enhancement-a composite property mapping algorithm
• Alternating Projections on Manifolds
• Local linear convergence for alternating and averaged nonconvex projections
• Method of successive projections for finding a common point of sets in metric spaces
• Dykstra's alternating projection algorithm for two sets
• Convergence Conditions for Nonlinear Programming Algorithms
• Elementary structure of real algebraic varieties
• LECTURES ON REAL STRATIFICATION THEORY
• Title not available (Why is that?)
• Curves and surfaces. Transl. from the Spanish by Sebastián Montiel. Transl. edited by Donald Babbitt
• Least-Squares Covariance Matrix Adjustment

Cited In (16)

• Frame completion with prescribed norms via alternating projection method
• Optimal rank-1 Hankel approximation of matrices: Frobenius norm and spectral norm and Cadzow's algorithm
• Alternating Projections on Manifolds
• A convex relaxation to compute the nearest structured rank deficient matrix
• Convergences of alternating projections in \(\mathrm{CAT}(\kappa)\) spaces
• Nonnegative low rank matrix approximation for nonnegative matrices
• Randomized low rank approximation for nonnegative pure quaternion matrices
• Operator-Lipschitz estimates for the singular value functional calculus
• Geometry of the phase retrieval problem
• Low-rank nonnegative tensor approximation via alternating projections and sketching
• Transversality and alternating projections for nonconvex sets
• Spokes, mirrors and alternating projections
• Stochastic algorithms for solving structured low-rank matrix approximation problems
• The punctured plane: alternating projections and $L^2$-angles
• Finding a low-rank basis in a matrix subspace
• Low rank pure quaternion approximation for pure quaternion matrices

Uses Software

• SDPT3

This page was built for publication: Alternating projections on nontangential manifolds

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