Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility

DOI10.1109/TSP.2014.2339801MaRDI QIDQ4579457zbMATH OpenFDO

Authors Robert Hesse, D. Russell Luke, Patrick Neumann

Publication date 22 August 2018

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Iterative procedures involving nonlinear operators (47J25) Set-valued and variational analysis (49J53) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The problem of finding a vector with the fewest nonzero elements that satisfies an underdetermined system of linear equations is an NP-complete problem that is typically solved numerically via convex heuristics or nicely-behaved nonconvex relaxations. In this work we consider elementary methods based on projections for solving a sparse feasibility problem without employing convex heuristics. In a recent paper Bauschke, Luke, Phan and Wang (2014) showed that, locally, the fundamental method of alternating projections must converge linearly to a solution to the sparse feasibility problem with an affine constraint. In this paper we apply different analytical tools that allow us to show global linear convergence of alternating projections under familiar constraint qualifications. These analytical tools can also be applied to other algorithms. This is demonstrated with the prominent Douglas-Rachford algorithm where we establish local linear convergence of this method applied to the sparse affine feasibility problem.

Recommendations

• A note on alternating projections for ill-posed semidefinite feasibility problems
• A projection method for solving the sparsity split feasibility problem
• Alternating Projection-Proximal Methods for Convex Programming and Variational Inequalities
• Douglas-Rachford feasibility methods for matrix completion problems
• Proximal Decomposition Via Alternating Linearization
• scientific article; zbMATH DE number 1424235
• On the application of alternating projection under the constraint of linear matrix inequalities
• Projection algorithms for nonconvex minimization with application to sparse principal component analysis
• Proximal point algorithm, Douglas-Rachford algorithm and alternating projections: a case study
• Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces

Cited in

(46)

• Circumcentering the Douglas-Rachford method
• Tight global linear convergence rate bounds for Douglas-Rachford splitting
• A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem
• General splitting methods with linearization for the split feasibility problem
• Alternating conditional gradient method for convex feasibility problems
• \( \alpha \)-firmly nonexpansive operators on metric spaces
• Method of alternating projections for the general absolute value equation
• Douglas-Rachford splitting and ADMM for nonconvex optimization: accelerated and Newton-type linesearch algorithms
• The Douglas-Rachford algorithm for convex and nonconvex feasibility problems
• The block-wise circumcentered-reflection method
• A parameterized Douglas-Rachford splitting algorithm for nonconvex optimization
• The rate of linear convergence of the Douglas-Rachford algorithm for subspaces is the cosine of the Friedrichs angle
• Douglas-Rachford splitting for the sum of a Lipschitz continuous and a strongly monotone operator
• On the Douglas-Rachford algorithm
• Local convergence properties of Douglas-Rachford and alternating direction method of multipliers
• On the linear convergence of the circumcentered-reflection method
• Union averaged operators with applications to proximal algorithms for MIN-convex functions
• A sparse proximal implementation of the LP dual active set algorithm
• Linear convergence of the Douglas-Rachford method for two closed sets
• On the order of the operators in the Douglas-Rachford algorithm
• The Douglas-Rachford algorithm for two (not necessarily intersecting) affine subspaces
• Global behavior of the Douglas-Rachford method for a nonconvex feasibility problem
• Convergence rate analysis for averaged fixed point iterations in common fixed point problems
• Optimal rates of linear convergence of relaxed alternating projections and generalized Douglas-Rachford methods for two subspaces
• Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems
• Local linear convergence of the ADMM/Douglas-Rachford algorithms without strong convexity and application to statistical imaging
• Activity identification and local linear convergence of Douglas-Rachford/ADMM under partial smoothness
• Regularity properties of non-negative sparsity sets
• Projection methods for quantum channel construction
• SURVEY: SIXTY YEARS OF DOUGLAS–RACHFORD
• Phase retrieval with sparse phase constraint
• A splitting method for finding the resolvent of the sum of two maximal monotone operators
• A weakly convergent fully inexact Douglas-Rachford method with relative error tolerance
• Douglas--Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• Proximal heterogeneous block implicit-explicit method and application to blind ptychographic diffraction imaging
• On the finite convergence of the Douglas-Rachford algorithm for solving (not necessarily convex) feasibility problems in Euclidean spaces
• Dynamic string‐averaging CQ‐methods for the split feasibility problem with percentage violation constraints arising in radiation therapy treatment planning
• Approximate Douglas-Rachford algorithm for two-sets convex feasibility problems
• Cardinality minimization, constraints, and regularization: a survey
• Non-separable multidimensional multiresolution wavelets: a Douglas-Rachford approach
• Global convergence and acceleration of projection methods for feasibility problems involving union convex sets
• Convergence in distribution of randomized algorithms: the case of partially separable optimization
• A convergent relaxation of the Douglas-Rachford algorithm
• Douglas–Rachford is the best projection method in its family
• Linear convergence of resolvent splitting with minimal lifting and its application to a primal–dual algorithm

This page was built for publication: Alternating Projections and Douglas-Rachford for Sparse Affine Feasibility

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