Sparse quadratic optimisation over the stiefel manifold with application to permutation synchronisation
(2021) 35th Conference on Neural Information Processing Systems, NeurIPS 2021 In Advances in Neural Information Processing Systems 34. p.25256-25266- Abstract
- We address the non-convex optimisation problem of finding a sparse matrix on the Stiefel manifold (matrices with mutually orthogonal columns of unit length) that maximises (or minimises) a quadratic objective function. Optimisation problems on the Stiefel manifold occur for example in spectral relaxations of various combinatorial problems, such as graph matching, clustering, or permutation synchronisation. Although sparsity is a desirable property in such settings, it is mostly neglected in spectral formulations since existing solvers, e.g. based on eigenvalue decomposition, are unable to account for sparsity while at the same time maintaining global optimality guarantees. We fill this gap and propose a simple yet effective... (More)
- We address the non-convex optimisation problem of finding a sparse matrix on the Stiefel manifold (matrices with mutually orthogonal columns of unit length) that maximises (or minimises) a quadratic objective function. Optimisation problems on the Stiefel manifold occur for example in spectral relaxations of various combinatorial problems, such as graph matching, clustering, or permutation synchronisation. Although sparsity is a desirable property in such settings, it is mostly neglected in spectral formulations since existing solvers, e.g. based on eigenvalue decomposition, are unable to account for sparsity while at the same time maintaining global optimality guarantees. We fill this gap and propose a simple yet effective sparsity-promoting modification of the Orthogonal Iteration algorithm for finding the dominant eigenspace of a matrix. By doing so, we can guarantee that our method finds a Stiefel matrix that is globally optimal with respect to the quadratic objective function, while in addition being sparse. As a motivating application we consider the task of permutation synchronisation, which can be understood as a constrained clustering problem that has particular relevance for matching multiple images or 3D shapes in computer vision, computer graphics, and beyond. We demonstrate that the proposed approach outperforms previous methods in this domain. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/4b9ceea6-7320-4b45-8650-b6ea9e5cc41d
- author
- Bernard, Florian ; Cremers, Daniel and Thunberg, Johan LU
- publishing date
- 2021
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 35th conference on neural information processing systems (NeurIPS 2021) : Online, 6-14 December 2021
- series title
- Advances in Neural Information Processing Systems
- volume
- 34
- pages
- 11 pages
- publisher
- Curran Associates, Inc
- conference name
- 35th Conference on Neural Information Processing Systems, NeurIPS 2021
- conference location
- Virtual, Online
- conference dates
- 2021-12-06 - 2021-12-14
- external identifiers
-
- scopus:85131858878
- ISSN
- 1049-5258
- ISBN
- 9781713845393
- language
- Unknown
- LU publication?
- no
- id
- 4b9ceea6-7320-4b45-8650-b6ea9e5cc41d
- date added to LUP
- 2024-09-05 14:43:18
- date last changed
- 2024-09-12 09:58:42
@inproceedings{4b9ceea6-7320-4b45-8650-b6ea9e5cc41d,
abstract = {{We address the non-convex optimisation problem of finding a sparse matrix on the Stiefel manifold (matrices with mutually orthogonal columns of unit length) that maximises (or minimises) a quadratic objective function. Optimisation problems on the Stiefel manifold occur for example in spectral relaxations of various combinatorial problems, such as graph matching, clustering, or permutation synchronisation. Although sparsity is a desirable property in such settings, it is mostly neglected in spectral formulations since existing solvers, e.g. based on eigenvalue decomposition, are unable to account for sparsity while at the same time maintaining global optimality guarantees. We fill this gap and propose a simple yet effective sparsity-promoting modification of the Orthogonal Iteration algorithm for finding the dominant eigenspace of a matrix. By doing so, we can guarantee that our method finds a Stiefel matrix that is globally optimal with respect to the quadratic objective function, while in addition being sparse. As a motivating application we consider the task of permutation synchronisation, which can be understood as a constrained clustering problem that has particular relevance for matching multiple images or 3D shapes in computer vision, computer graphics, and beyond. We demonstrate that the proposed approach outperforms previous methods in this domain.}},
author = {{Bernard, Florian and Cremers, Daniel and Thunberg, Johan}},
booktitle = {{35th conference on neural information processing systems (NeurIPS 2021) : Online, 6-14 December 2021}},
isbn = {{9781713845393}},
issn = {{1049-5258}},
language = {{und}},
pages = {{25256--25266}},
publisher = {{Curran Associates, Inc}},
series = {{Advances in Neural Information Processing Systems}},
title = {{Sparse quadratic optimisation over the stiefel manifold with application to permutation synchronisation}},
volume = {{34}},
year = {{2021}},
}