Advanced

Optimal convergence rates for generalized alternating projections

Fält, Mattias LU and Giselsson, Pontus LU (2017) 56th IEEE Annual Conference on Decision and Control, CDC 2017 In Proceedings of the IEEE Conference on Decision and Control, 2017 p.2268-2274
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
OPTIMIZATION, First order optimization algorithms
in
Proceedings of the IEEE Conference on Decision and Control, 2017
pages
7 pages
publisher
IEEE--Institute of Electrical and Electronics Engineers Inc.
conference name
56th IEEE Annual Conference on Decision and Control, CDC 2017
external identifiers
  • scopus:85046282732
ISBN
978-1-5090-2874-0
978-1-5090-2873-3
DOI
10.1109/CDC.2017.8263980
language
English
LU publication?
yes
id
edbb4c52-621f-4ace-a8b9-61e0d5a0660f
alternative location
https://arxiv.org/abs/1703.10547
date added to LUP
2018-02-01 09:31:54
date last changed
2018-05-20 04:40:27
@inproceedings{edbb4c52-621f-4ace-a8b9-61e0d5a0660f,
  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.},
  author       = {Fält, Mattias and Giselsson, Pontus},
  booktitle    = {Proceedings of the IEEE Conference on Decision and Control, 2017},
  isbn         = {978-1-5090-2874-0},
  keyword      = {OPTIMIZATION,First order optimization algorithms},
  language     = {eng},
  month        = {12},
  pages        = {2268--2274},
  publisher    = {IEEE--Institute of Electrical and Electronics Engineers Inc.},
  title        = {Optimal convergence rates for generalized alternating projections},
  url          = {http://dx.doi.org/10.1109/CDC.2017.8263980},
  year         = {2017},
}