MADMM: A Generic Algorithm for Non-smooth Optimization on Manifolds
Numerous problems in computer vision, pattern recognition, and machine learning are formulated as optimization with manifold constraints. In this paper, we propose the Manifold Alternating Directions Method of Multipliers (MADMM), an extension of the clas
- PDF / 2,518,414 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 6 Downloads / 258 Views
bstract. Numerous problems in computer vision, pattern recognition, and machine learning are formulated as optimization with manifold constraints. In this paper, we propose the Manifold Alternating Directions Method of Multipliers (MADMM), an extension of the classical ADMM scheme for manifold-constrained non-smooth optimization problems. To our knowledge, MADMM is the first generic non-smooth manifold optimization method. We showcase our method on several challenging problems in dimensionality reduction, non-rigid correspondence, multi-modal clustering, and multidimensional scaling.
1
Introduction
A wide range of problems in machine learning, pattern recognition, computer vision, and signal processing is formulated as optimization problems where the variables are constrained to lie on some Riemannian manifold. For example, optimization on the Grassman manifold comes up in multi-view clustering [1] and matrix completion [2]. Optimization on the Stiefel manifold arises in eigenvalue-, assignment-, and Procrustes problems, and in 1-bit compressed sensing [3]. Problems involving products of Stiefel manifolds include coupled diagonalization with applications to shape correspondence [4] and manifold learning [5], and eigenvector synchronization with applications to sensor localization [6], structural biology [7] and structure from motion recovery [8]. Optimization on the sphere is used in principle geodesic analysis [9], a generalization of the classical PCA to nonEuclidean domains. Optimization over the manifold of fixed-rank matrices arises in maxcut problems [10], sparse principal component analysis [10], regression [11], matrix completion [12,13], and image classification [14]. Oblique manifolds are encountered in problems such as independent component analysis [15], blind source separation [16], and prediction of stock returns [17]. Though some instances of manifold optimization such as eigenvalues problems have been treated extensively in the distant past, the first general purpose algorithms appeared only in the 1990s [18]. With the emergence of numerous applications during the last decade, especially in the machine learning community, there has been an increased interest in general-purpose optimization on different manifolds [19], leading to several manifold optimization algorithms c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part V, LNCS 9909, pp. 680–696, 2016. DOI: 10.1007/978-3-319-46454-1 41
MADMM: A Generic Algorithm for Non-smooth Optimization on Manifolds
681
such as conjugate gradients [20], trust regions [21], and Newton [18,22]. Boumal et al. [23] released the MATLAB package Manopt, as of today the most complete generic toolbox for smooth optimization on various manifolds. In this paper, we are interested in manifold-constrained minimization of non-smooth functions, such as nuclear, L1 , or L2,1 matrix norms. Recent examples of such problems include robust PCA [24], compressed eigenmodes [25,26], robust multidimensional scaling [27], synchronization of rotation mat
Data Loading...
