Algorithms Seminar
Sparse Approximate Hulls
Speaker:  Ben Raichel

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


Abstract
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 \epsapproximates
the convex hull of P (under Hausdorff distance). If k is the size of the smallest epsilonapproximation, then we produce a k' sized \eps'approximation. Here k' and \eps' are functions of k and \eps, and we present several tradeoffs 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 dsum 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 nonnegative. Thus our problem
combines two of the most common factorizations, namely nonnegative
factorization, and CU decomposition. One reason for the widespread
popularity of nonnegative 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.
Biography
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 dimensionindependent 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
ACMSIAM 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 UrbanaChampaign.