A Caltech Library Service

Fitting Tractable Convex Sets to Support Function Evaluations

Soh, Yong Sheng and Chandrasekaran, Venkat (2021) Fitting Tractable Convex Sets to Support Function Evaluations. Discrete and Computational Geometry, 66 (2). pp. 510-551. ISSN 0179-5376. doi:10.1007/s00454-020-00258-0.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The geometric problem of estimating an unknown compact convex set from evaluations of its support function arises in a range of scientific and engineering applications. Traditional approaches typically rely on estimators that minimize the error over all possible compact convex sets; in particular, these methods allow for limited incorporation of prior structural information about the underlying set and the resulting estimates become increasingly more complicated to describe as the number of measurements available grows. We address both of these shortcomings by describing a framework for estimating tractably specified convex sets from support function evaluations. Building on the literature in convex optimization, our approach is based on estimators that minimize the error over structured families of convex sets that are specified as linear images of concisely described sets—such as the simplex or the spectraplex—in a higher-dimensional space that is not much larger than the ambient space. Convex sets parametrized in this manner are significant from a computational perspective as one can optimize linear functionals over such sets efficiently; they serve a different purpose in the inferential context of the present paper, namely, that of incorporating regularization in the reconstruction while still offering considerable expressive power. We provide a geometric characterization of the asymptotic behavior of our estimators, and our analysis relies on the property that certain sets which admit semialgebraic descriptions are Vapnik–Chervonenkis classes. Our numerical experiments highlight the utility of our framework over previous approaches in settings in which the measurements available are noisy or small in number as well as those in which the underlying set to be reconstructed is non-polyhedral.

Item Type:Article
Related URLs:
URLURL TypeDescription ReadCube access Paper
Soh, Yong Sheng0000-0003-3367-1401
Additional Information:© 2021 Springer Science+Business Media, LLC, part of Springer Nature. Received 09 May 2019; Revised 23 October 2019; Accepted 14 October 2020; Published 03 January 2021. The authors were supported in part by NSF grants CCF-1350590 and CCF-1637598, by Air Force Office of Scientific Research Grant FA9550-16-1-0210, by a Sloan research fellowship, and an A*STAR (Agency for Science, Technology and Research, Singapore) fellowship. Editor in Charge: Kenneth Clarkson.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0210
Alfred P. Sloan FoundationUNSPECIFIED
Agency for Science, Technology and Research (A*STAR)UNSPECIFIED
Subject Keywords:Constrained shape regression; Convex regression; Entropy of semialgebraic sets; K-means clustering; Simplicial polytopes; Stochastic equicontinuity
Issue or Number:2
Record Number:CaltechAUTHORS:20190626-093718719
Persistent URL:
Official Citation:Soh, Y.S., Chandrasekaran, V. Fitting Tractable Convex Sets to Support Function Evaluations. Discrete Comput Geom 66, 510–551 (2021).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:96717
Deposited By: Tony Diaz
Deposited On:26 Jun 2019 16:48
Last Modified:04 Aug 2021 22:24

Repository Staff Only: item control page