A Caltech Library Service

Fitting Convex Sets to Data: Algorithms and Applications


Soh, Yong Sheng (2019) Fitting Convex Sets to Data: Algorithms and Applications. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/jkmq-b430.


This thesis concerns the geometric problem of finding a convex set that best fits a given dataset. Our question serves as an abstraction for data-analytical tasks arising in a range of scientific and engineering applications. We focus on two specific instances:

1. A key challenge that arises in solving inverse problems is ill-posedness due to a lack of measurements. A prominent family of methods for addressing such issues is based on augmenting optimization-based approaches with a convex penalty function so as to induce a desired structure in the solution. These functions are typically chosen using prior knowledge about the data. In Chapter 2, we study the problem of learning convex penalty functions directly from data for settings in which we lack the domain expertise to choose a penalty function. Our solution relies on suitably transforming the problem of learning a penalty function into a fitting task.

2. In Chapter 3, we study the problem of fitting tractably-described convex sets given the optimal value of linear functionals evaluated in different directions.

Our computational procedures for fitting convex sets are based on a broader framework in which we search among families of sets that are parameterized as linear projections of a fixed structured convex set. The utility of such a framework is that our procedures reduce to the computation of simple primitives at each iteration, and these primitives can be further performed in parallel. In addition, by choosing structured sets that are non-polyhedral, our framework provides a principled way to search over expressive collections of non-polyhedral descriptions; in particular, convex sets that can be described via semidefinite programming provide a rich source of non-polyhedral sets, and such sets feature prominently in this thesis.

We provide performance guarantees for our procedures. Our analyses rely on understanding geometrical aspects of determinantal varieties, building on ideas from empirical processes as well as random matrix theory. We demonstrate the utility of our framework with numerical experiments on synthetic data as well as applications in image denoising and computational geometry.

As secondary contributions, we consider the following:

1. In Chapter 4, we consider the problem of optimally approximating a convex set as a spectrahedron of a given size. Spectrahedra are sets that can be expressed as feasible regions of a semidefinite program.

2. In Chapter 5, we consider change-point estimation in a sequence of high-dimensional signals given noisy observations. Our method integrates classical approaches with a convex optimization-based step that is useful for exploiting structure in high-dimensional data.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Convex Optimization, Semidefinite Programming, Atomic Norm, Shape Regression, Representation Learning
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Awards:The W.P. Carey and Co., Inc., Prize in Applied Mathematics, 2019. Ben P.C. Chou Doctoral Prize in IST, 2019.
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Chandrasekaran, Venkat
Thesis Committee:
  • Tropp, Joel A. (chair)
  • Chandrasekaran, Venkat
  • Desbrun, Mathieu
  • Hassibi, Babak
  • Stuart, Andrew M.
Defense Date:29 August 2018
Non-Caltech Author Email:sohyongsheng87 (AT)
Funding AgencyGrant Number
Agency for Science, Technology and Research (Singapore)UNSPECIFIED
National Science Foundation (NSF)CCF-1350590
Air Force Office of Scientific Research (AFOSR)FA9550-14-1-0098
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0210
Record Number:CaltechTHESIS:09282018-091842941
Persistent URL:
Related URLs:
URLURL TypeDescription adapted for Ch. 5 adapted for Ch. 5 adapted for Ch. 2
Soh, Yong Sheng0000-0003-3367-1401
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11208
Deposited By: Yong Sheng Soh
Deposited On:09 Oct 2018 18:56
Last Modified:18 Dec 2020 18:36

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page