Algorithms Seminar

Sparse Approximate Hulls

Speaker:Ben Raichel
Date: Thursday, February 23, 2017
Time: 12:00pm - 1:00pm
Location: D344 LSRC, Duke


Given a set P of n points in the unit ball in R^d, consider the problem of finding a small subset S of P whose convex hull \eps-approximates the convex hull of P (under Hausdorff distance). If k is the size of the smallest epsilon-approximation, then we produce a k' sized \eps'-approximation. Here k' and \eps' are functions of k and \eps, and we present several trade-offs between them. Most notable is an efficient greedy procedure, which surprisingly yields a k' and \eps' independent of $n$ and $d$. We then extend this result to approximating conic hulls by giving a reduction from the conic case to the convex case. Moreover, we prove both variants are d-sum hard, justifying the need for approximation. When cast as a matrix factorization problem, the conic version seeks a factorization P ~ BC, where the columns of B are a subset of those from P and the entries in C are all non-negative. Thus our problem combines two of the most common factorizations, namely non-negative factorization, and CU decomposition. One reason for the widespread popularity of non-negative factorization in areas such as machine learning is that in practice it often gives sparse solutions. Thus as a final result we prove an approximate conic Caratheodory theorem, arguing any conic approximation can be sparsified, thus giving some theoretical justification to this practical observation.


Dr. Raichel is an assistant professor at the University of Texas at Dallas. His research focus is algorithmic design, and more specifically the combination of computational geometry with other areas such as randomized and approximation algorithms. Recently Dr. Raichel has worked on algorithms for sparse dimension-independent geometric approximation, in particular on finding coresets for approximating hulls in high dimensions. He has published papers in the ACM Symposium on the Theory of Computing, the IEEE Foundations of Computer Science, and ACM-SIAM Symposium on Discrete Algorithms, the top theoretical computer science conferences. He has also published numerous papers in the Symposium on Computational Geometry, the leading conference in computational geometry. Dr. Raichel obtained his PhD from the University of Illinois at Urbana-Champaign.