Optimal convergence rates for generalized alternating projections
(2017) 56th IEEE Annual Conference on Decision and Control, CDC 2017 p.22682274 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:
http://lup.lub.lu.se/record/edbb4c52621f4acea8b961e0d5a0660f
 author
 Fält, Mattias ^{LU} and Giselsson, Pontus ^{LU}
 organization
 publishing date
 20171212
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 OPTIMIZATION, First order optimization algorithms
 host publication
 Proceedings of the IEEE Conference on Decision and Control, 2017
 pages
 7 pages
 publisher
 IEEEInstitute of Electrical and Electronics Engineers Inc.
 conference name
 56th IEEE Annual Conference on Decision and Control, CDC 2017
 conference location
 Melbourne, Australia
 conference dates
 20171212  20171215
 external identifiers

 scopus:85046282732
 ISBN
 9781509028740
 9781509028733
 DOI
 10.1109/CDC.2017.8263980
 language
 English
 LU publication?
 yes
 id
 edbb4c52621f4acea8b961e0d5a0660f
 alternative location
 https://arxiv.org/abs/1703.10547
 date added to LUP
 20180201 09:31:54
 date last changed
 20190106 13:42:59
@inproceedings{edbb4c52621f4acea8b961e0d5a0660f, 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}, isbn = {9781509028740}, keyword = {OPTIMIZATION,First order optimization algorithms}, language = {eng}, location = {Melbourne, Australia}, month = {12}, pages = {22682274}, publisher = {IEEEInstitute 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}, }