Open Collections

Bundle-type methods for dual atomic pursuit

University of British Columbia

We discuss a type of structured optimization problem called atomic pursuit, where the aim is to assemble a solution, using a given set of (possibly uncountably infinite) atoms, to fit a model to data, popularized in compressed sensing and machine learning. The solutions to atomic pursuit problems can be formed as the sum of a few atoms, which means they lie on low-dimensional facets of the convex hull of the atomic set and the gauges induced by the convex hull of the atomic sets have been shown to promote atomic sparsity. Examples include well-studied cases such as one norm promoting general sparsity and nuclear norm promoting low rankness. In this thesis, we examine the gauge dual of atomic pursuit and show that the support of the primal solution can be recovered from the dual solution. In particular, a two-stage algorithm based on gauge duality and bundle-type methods is proposed. The first stage discovers the optimal atomic support for the primal problem by solving a sequence of approximations of the dual problem using a bundle-type method, which geometrically can be seen as producing a sequence of inscribing subsets of the atomic set. The second stage recovers the approximate primal solution using the atoms discovered in the first stage. We show that these methods lead to efficient and scalable semidefinite optimization methods with low-rank solutions, producing a fast, scalable, SDP solver for phase retrieval and graph problems.

Text

2019-08-20

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/71339

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-nd/4.0/