Optimal convergence rates for generalized alternating projections

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

Generalized alternating projections is an algorithm that alternates relaxed projections onto a finite number of sets to find a point in their intersection. We consider the special case of two linear subspaces, for which the algorithm reduces to matrix multiplications. For convergent powers of the matrix, the asymptotic rate is linear and decided by the magnitude of the subdominant eigenvalue. In this paper, we show how to select the three algorithm parameters to optimize this magnitude, and hence the asymptotic convergence rate. The obtained rate depends on the Friedrichs angle between the subspaces and is considerably better than known rates for other methods such as alternating projections and DouglasRachford splitting. We also present an adaptive scheme that, online, estimates the Friedrichs angle and updates the algorithm parameters based on this estimate. A numerical example is provided that supports our theoretical claims and shows very good performance for the adaptive method.

Details

Authors
Organisations
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Control Engineering

Keywords

  • OPTIMIZATION, First order optimization algorithms
Original languageEnglish
Title of host publicationProceedings of the IEEE Conference on Decision and Control, 2017
PublisherIEEE--Institute of Electrical and Electronics Engineers Inc.
Pages2268-2274
Number of pages7
ISBN (Electronic)978-1-5090-2873-3
ISBN (Print)978-1-5090-2874-0
Publication statusPublished - 2017 Dec 12
Publication categoryResearch
Peer-reviewedYes
Event56th IEEE Annual Conference on Decision and Control, CDC 2017 - Melbourne, Australia
Duration: 2017 Dec 122017 Dec 15
Conference number: 56
http://cdc2017.ieeecss.org/

Conference

Conference56th IEEE Annual Conference on Decision and Control, CDC 2017
Abbreviated titleCDC 2017
CountryAustralia
CityMelbourne
Period2017/12/122017/12/15
Internet address

Related projects

Mattias Fält & Pontus Giselsson

Swedish Foundation for Strategic Research, SSF, Swedish Research Council

Project: Research

View all (1)