Alternating projections on nontangential manifolds

DOI10.1007/S00365-013-9213-3MaRDI QIDQ387545zbMATH OpenOpenAlexFDO

Authors Fredrik Andersson, Marcus Carlsson

Publication date 23 December 2013

Published in Constructive Approximation (Search for Journal in Brave)

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

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)

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.

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

Cites work

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

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
• Stochastic algorithms for solving structured low-rank matrix approximation problems
• Spokes, mirrors and alternating projections
• Finding a low-rank basis in a matrix subspace
• The punctured plane: alternating projections and $L^2$-angles
• Low rank pure quaternion approximation for pure quaternion matrices

Describes a project that uses

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)