Graduate Programs
Graduate Home
Ph D Programs
Masters Degree
Ph D Program Requirements
Course Descriptions
Current Courses
Admissions
Current Graduate Students
Graduate Student Seminar
SIAM Chapter Seminar
Recent Graduates
Incoming Students

Graduate Seminar
Kerrek Stinson Carnegie Mellon University Title: A randomized algorithm for enumerating zonotope vertices Abstract: We propose a randomized algorithm for enumerating the vertices of a zonotope, which is a lowdimensional linear projection of a hypercube. The algorithm produces a pair of the zonotope's vertices by sampling a random linear combination of the zonotope generators, where the combination's weights are the signs of the product between the zonotope's generator matrix and random vectors with normally distributed entries. We study the probability of recovering particular vertices and relate it to the vertices' normal cones. This study shows that if we terminate the randomized algorithm before all vertices are recovered, then the convex hull of the resulting vertex set approximates the zonotope. In high dimensions, we expect the enumeration algorithm to be most appropriate as an approximation algorithmparticularly for cases when existing methods are not practical. Date: Tuesday, September 26, 2017 Time: 5:30 pm Location: Wean Hall 8220 Submitted by: Yangxi Ou Note: Video on YouTube: https://youtu.be/zu9aZND13yE 