Bundle-type methods for dual atomic pursuit
department or school: Science, Faculty of
department or school: Computer Science, Department of
data provider: DSpace
degree campus: UBCV
creator: Fan, Zhenan
issued: 2019-08-20T15:36:05Z
issued: 2019
related degree: Master of Science - MSc
degree grantor: University of British Columbia
description: 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.
aggregated CHO: https://circle.library.ubc.ca/rest/handle/2429/71339
note: Bundle-type methods for dual atomicpursuitbyZhenan FanB.Sc., University of Toronto, 2017A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Computer Science)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2019c© Zhenan Fan 2019The following individuals certify that they have read, and recommend to the Faculty ofGraduate and Postdoctoral Studies for acceptance, the thesis entitled:Bundle-type methods for dual atomic pursuitsubmitted by Zhenan Fan in partial fulfillment of the requirements for the degree ofMaster of Science in Computer Science.Examining Committee:Michael P. Friedlander, Computer ScienceSupervisorBruce Shepherd, Computer ScienceSecond ReaderiiAbstractWe discuss a type of structured optimization problem called atomic pursuit, where the aimis to assemble a solution, using a given set of (possibly uncountably infinite) atoms, to fit amodel to data, popularized in compressed sensing and machine learning. The solutions toatomic pursuit problems can be formed as the sum of a few atoms, which means they lie onlow-dimensional facets of the convex hull of the atomic set and the gauges induced by theconvex hull of the atomic sets have been shown to promote atomic sparsity. Examples includewell-studied cases such as one norm promoting general sparsity and nuclear norm promotinglow rankness. In this thesis, we examine the gauge dual of atomic pursuit and show thatthe support of the primal solution can be recovered from the dual solution. In particular, atwo-stage algorithm based on gauge duality and bundle-type methods is proposed. The firststage discovers the optimal atomic support for the primal problem by solving a sequence ofapproximations of the dual problem using a bundle-type method, which geometrically canbe seen as producing a sequence of inscribing subsets of the atomic set. The second stagerecovers the approximate primal solution using the atoms discovered …
has type: Thesis/Dissertation
date issued: 2019-09
is shown at: 10.14288/1.0380495
language: eng
degree discipline: Computer Science
provider: Vancouver : University of British Columbia Library
publisher: University of British Columbia
rights: Attribution-NonCommercial-NoDerivatives 4.0 International
rights URI: http://creativecommons.org/licenses/by-nc-nd/4.0/
scholar level: Graduate
type: Text
identifier URI: http://hdl.handle.net/2429/71339