Sparse Approximate Hulls
||Thursday, February 23, 2017
||12:00pm - 1:00pm
||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.