DeepHull: Fast Convex Hull Approximation in High Dimensions
Authors:
- 23 May 2022
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 3888-3892
Abstract
Computing or approximating the convex hull of a dataset plays a role in a wide range of applications, including economics, statistics, and physics, to name just a few. However, convex hull computation and approximation is exponentially complex, in terms of both memory and computation, as the ambient space dimension increases. In this paper, we propose DeepHull, a new convex hull approximation algorithm based on convex deep networks (DNs) with continuous piecewise-affine nonlinearities and nonnegative weights. The idea is that binary classification between true data samples and adversarially generated samples with such a DN naturally induces a polytope decision boundary that approximates the true data convex hull. A range of exploratory experiments demonstrates that DeepHull efficiently produces a meaningful convex hull approximation, even in a high-dimensional ambient space.Keywords
This publication has 16 references indexed in Scilit:
- gHullACM Transactions on Mathematical Software, 2013
- CHull: A generic convex-hull-based model selection methodBehavior Research Methods, 2012
- CudaHull: Fast parallel 3D convex hull on the GPUComputers & Graphics, 2012
- A convex hull approach for the reliability-based design optimization of nonlinear transient dynamic problemsComputer Methods in Applied Mechanics and Engineering, 2007
- Minimizing within Convex Bodies Using a Convex Hull MethodSIAM Journal on Optimization, 2005
- Neural networks for convex hull computationIEEE Transactions on Neural Networks, 1997
- The quickhull algorithm for convex hullsACM Transactions on Mathematical Software, 1996
- The Ultimate Planar Convex Hull Algorithm?SIAM Journal on Computing, 1986
- Approximation algorithms for convex hullsCommunications of the ACM, 1982
- A New Convex Hull Algorithm for Planar SetsACM Transactions on Mathematical Software, 1977