Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons

DOI10.1137/18M1193025zbMATH Open1499.90175arXiv1810.02893WikidataQ127388661 ScholiaQ127388661MaRDI QIDQ5025784FDOQ5025784

Authors: D. Russell Luke, Shoham Sabach, Marc Teboulle 

Publication date: 3 February 2022

Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)

Abstract: We present a unified treatment of the abstract problem of finding the best approximation between a cone and spheres in the image of affine transformations. Prominent instances of this problem are phase retrieval and source localization. The common geometry binding these problems permits a generic application of algorithmic ideas and abstract convergence results for nonconvex optimization. We organize variational models for this problem into three different classes and derive the main algorithmic approaches within these classes (13 in all). We identify the central ideas underlying these methods and provide thorough numerical benchmarks comparing their performance on synthetic and laboratory data. The software and data of our experiments are all publicly accessible. We also introduce one new algorithm, a cyclic relaxed Douglas-Rachford algorithm, which outperforms all other algorithms by every measure: speed, stability and accuracy. The analysis of this algorithm remains open.

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

Recommendations

• Optimization on the Euclidean unit sphere
• Concepts and techniques of optimization on the sphere
• scientific article; zbMATH DE number 7626752
• From the simplex to the sphere: faster constrained optimization using the Hadamard parametrization
• Approximation algorithms for nonnegative polynomial optimization problems over unit spheres
• A derivative-free algorithm for spherically constrained optimization
• Geodesic regression on spheres from a numerical optimization viewpoint
• The cubic spherical optimization problems
• Stochastic proximal gradient method FOR \(\ell_1\) regularized optimization over a sphere

zbMATH Keywords

nonconvex optimizationnonsmooth optimizationfixed pointsfeasibilityproximal algorithmsphase retrievalsource localization

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Nonconvex programming, global optimization (90C26) Numerical methods in optimal control (49M99)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• iPiano: inertial proximal algorithm for nonconvex optimization
• Phase retrieval via Wirtinger flow: theory and algorithms
• Numerical Optimization
• On the Numerical Solution of Heat Conduction Problems in Two and Three Space Variables
• Title not available (Why is that?)
• Variational Analysis
• Title not available (Why is that?)
• Proximal alternating linearized minimization for nonconvex and nonsmooth problems
• Representations of quasi-Newton matrices and their use in limited memory methods
• Title not available (Why is that?)
• Local differentiability of distance functions
• Proximité et dualité dans un espace hilbertien
• Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods
• Nonsmooth optimization via quasi-Newton methods
• Restricted normal cones and sparsity optimization with affine constraints
• A cyclic Douglas-Rachford iteration scheme
• Linear and strong convergence of algorithms involving averaged nonexpansive operators
• Proximal heterogeneous block implicit-explicit method and application to blind ptychographic diffraction imaging
• The cyclic Douglas-Rachford method for inconsistent feasibility problems
• Least Squares Algorithms for Time-of-Arrival-Based Mobile Location
• Nonconvex notions of regularity and convergence of fundamental algorithms for feasibility problems
• Local linear convergence for alternating and averaged nonconvex projections
• Finding Best Approximation Pairs Relative to a Convex and Prox-Regular Set in a Hilbert Space
• Optical Wavefront Reconstruction: Theory and Numerical Methods
• Finding best approximation pairs relative to two closed convex sets in Hilbert spaces
• Rate of Convergence Analysis of Decomposition Methods Based on the Proximal Method of Multipliers for Convex Minimization
• Projection methods: an annotated bibliography of books and reviews
• Relaxed averaged alternating reflections for diffraction imaging
• Local linear convergence of approximate projections onto regularized sets
• Global convergence of splitting methods for nonconvex composite optimization
• A convergent relaxation of the Douglas-Rachford algorithm
• On the solution of the GPS localization and circle fitting problems
• Inertial proximal alternating linearized minimization (iPALM) for nonconvex and nonsmooth problems
• First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems
• A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem
• Iterative Minimization Schemes for Solving the Single Source Localization Problem
• Algorithms and convergence results of projection methods for inconsistent feasibility problems: a review
• Nonconvex Lagrangian-based optimization: monitoring schemes and global convergence
• A flexible convex relaxation for phase retrieval
• Quantitative Convergence Analysis of Iterated Expansive, Set-Valued Mappings
• On Fienup Methods for Sparse Phase Retrieval
• Phase retrieval for Fresnel measurements using a shearlet sparsity constraint
• Phase retrieval via sensor network localization
• Variational phase retrieval with globally convergent preconditioned proximal algorithm

Cited In (10)

• On the relationship between the Kurdyka-Łojasiewicz property and error bounds on Hadamard manifolds
• Convergence Analysis of the Relaxed Douglas--Rachford Algorithm
• Concepts and techniques of optimization on the sphere
• Non-dissipative and structure-preserving emulators via spherical optimization
• Convex combination of alternating projection and Douglas-Rachford operators for phase retrieval
• Projection methods for high numerical aperture phase retrieval
• The cubic spherical optimization problems
• From the simplex to the sphere: faster constrained optimization using the Hadamard parametrization
• \( \alpha \)-firmly nonexpansive operators on metric spaces
• A dynamic alternating direction of multipliers for nonconvex minimization with nonlinear functional equality constraints

Uses Software

• iPiano
• PhasePack
• PhaseMax
• Wirtinger Flow
• Superflip
• ProxToolbox

This page was built for publication: Optimization on Spheres: Models and Proximal Algorithms with Computational Performance Comparisons

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