Biconvex Relaxation for Semidefinite Programming in Computer Vision
Semidefinite programming (SDP) is an indispensable tool in computer vision, but general-purpose solvers for SDPs are often too slow and memory intensive for large-scale problems. Our framework, referred to as biconvex relaxation (BCR), transforms an SDP c
- PDF / 2,601,638 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 81 Downloads / 223 Views
University of Maryland, College Park, MD, USA [email protected], {jaiabhay,djacobs,tomg}@cs.umd.edu, [email protected] 2 Cornell University, Ithaca, NY, USA [email protected] Abstract. Semidefinite programming (SDP) is an indispensable tool in computer vision, but general-purpose solvers for SDPs are often too slow and memory intensive for large-scale problems. Our framework, referred to as biconvex relaxation (BCR), transforms an SDP consisting of PSD constraint matrices into a specific biconvex optimization problem, which can then be approximately solved in the original, low-dimensional variable space at low complexity. The resulting problem is solved using an efficient alternating minimization (AM) procedure. Since AM has the potential to get stuck in local minima, we propose a general initialization scheme that enables BCR to start close to a global optimum—this is key for BCR to quickly converge to optimal or near-optimal solutions. We showcase the efficacy of our approach on three applications in computer vision, namely segmentation, co-segmentation, and manifold metric learning. BCR achieves solution quality comparable to state-ofthe-art SDP methods with speedups between 4× and 35×.
1
Introduction
Optimization problems involving either integer-valued vectors or low-rank matrices are ubiquitous in computer vision. Graph-cut methods for image segmentation, for example, involve optimization problems where integer-valued variables represent region labels [1–4]. Problems in multi-camera structure from motion [5], manifold embedding [6], and matrix completion [7] all rely on optimization problems involving matrices with low rank constraints. Since these constraints are non-convex, the design of efficient algorithms that find globally optimal solutions is a difficult task. For a wide range of applications [6,8–12], non-convex constraints can be handled by semidefinite relaxation (SDR) [8]. In this approach, a non-convex optimization problem involving a vector of unknowns is “lifted” to a higher dimensional convex problem that involves a positive semidefinite (PSD) matrix, which then enables one to solve a SDP [13]. While SDR delivers state-of-the-art S. Shah and A.K. Yadav—The first two authors contributed equally to this work. c Springer International Publishing AG 2016 B. Leibe et al. (Eds.): ECCV 2016, Part VI, LNCS 9910, pp. 717–735, 2016. DOI: 10.1007/978-3-319-46466-4 43
718
S. Shah et al.
performance in a wide range of applications [3,4,6–8,14], the approach significantly increases the dimensionality of the original optimization problem (i.e., replacing a vector with a matrix), which typically results in exorbitant computational costs and memory requirements. Nevertheless, SDR leads to SDPs whose global optimal solution can be found using robust numerical methods. A growing number of computer-vision applications involve high-resolution images (or videos) that require SDPs with a large number of variables. Generalpurpose (interior point) solvers for SDPs do not scale well to such problem sizes; the worst-case
Data Loading...
