Nested Barycentric Coordinate System as an Explicit Feature Map

We introduce a new embedding technique based on a barycentric coordinate system. We show that our embedding can be used to transform the problem of polytope approximation into one of finding a linear classifier in a higher dimensional (but nevertheless quite sparse) representation. In effect, this embedding maps a piecewise linear function into an everywhere-linear function, and allows us to invoke well-known algorithms for the latter problem to solve the former. We demonstrate that our embedding has applications to the problems of approximating separating polytopes - in fact, it can approximate any convex body and unions of convex bodies - as well as to classification by separating polytopes and piecewise linear regression.