Page 1 of 1

Projecting a Polytope

Posted: Fri Apr 13, 2018 10:20 pm UTC
by cyanyoshi
I'm having some trouble finding a good way to project a convex polytope into lower dimensions. Specifically, I am given a matrix "G" and column vector "h" which define a set of x in RN such that Gx≤h, and a linear mapping y=Cx. The goal is to find a "P" and "q" to represent Cx as the set of all y such that Py≤q. It's easy to show that P=GC-1 and q=h solve the problem if C is invertible, but this doesn't work if y has a lower number of dimensions than x. I could just project each vertex individually if I knew the set of vertices beforehand, but I'm worried that the curse of dimensionality might make it difficult to enumerate the vertices for N on the order of hundreds or even thousands.

Note: For two vectors "a" and "b" in RN, a≤b is equivalent to a(i)≤b(i) for all i=1,...,N.

Re: Projecting a Polytope

Posted: Mon Apr 16, 2018 4:24 pm UTC
by Qaanol
Here’s something to try:

Form a continuous family of transformations T(t) such that T(0) = C, and T is invertible when t≠0. For example, I think T(t) = t·I + (1−t)·C should work. Find the general solution in terms of T when t≠0, then take the limit as t→0.

Re: Projecting a Polytope

Posted: Mon Apr 16, 2018 9:21 pm UTC
by cyanyoshi
Thanks for the suggestion! I'm not sure how to get around the fact that x and y are in vector spaces of different dimension, though. I know that invertible transformations do exist, but I couldn't even begin to figure out how to construct T(t) which is invertible for t>0, but approaches something linear at t=0.

Re: Projecting a Polytope

Posted: Mon Apr 16, 2018 9:51 pm UTC
by DavidSh
I don't expect this to be easy. After all, if y is of dimension 1 you basically have Linear Programming (finding a maximum or minimum of a linear function over a region defined by linear inequalities), which took quite some time for somebody to find a polynomial-time algorithm for.

Re: Projecting a Polytope

Posted: Mon Apr 16, 2018 10:18 pm UTC
by Qaanol
cyanyoshi wrote:Thanks for the suggestion! I'm not sure how to get around the fact that x and y are in vector spaces of different dimension, though. I know that invertible transformations do exist, but I couldn't even begin to figure out how to construct T(t) which is invertible for t>0, but approaches something linear at t=0.

I already gave you an example of T. Just write the matrix down using “t” as a variable, calculate its inverse, and solve your original problem. If that solution has a limit as t→0, then you are basically done.

The dimensionality difference is the entire point of using a continuous family of transforms. The lower-dimensional space embeds within the higher-dimensional space, as a subspace orthogonal to the direction of the projection. The projection squashes space flat, but nearby transformations still have full rank. So we can perturb the flattening projection very slightly and see what happens when it is “nearly flat”.

The specific example of T that I posted, namely T(t) = t·I + (1−t)·C, is the natural “flattening” action that you would see in an animation of how C affects space. As you squash space flatter and flatter, everything moves directly toward the flat destination subspace. As long as you haven’t gotten all the way to complete flatness, all the dimensions are still present and you can solve the problem as you described.

And since you are doing the squashing in a continuous manner, you can take the limit as you approach full flatness. Does that make sense?

• • •

This may not work, if it makes everything blow up to infinity. I haven’t actually tried it, it just seemed like perturbation might be tractable.

Re: Projecting a Polytope

Posted: Thu Apr 19, 2018 7:05 pm UTC
by cyanyoshi
I may have found more or less what I've been looking for in "Equality Set Projection: A new algorithm for the projection
of polytopes in halfspace representation" by Jones, Kerrigan, and Maciejowski (2004): http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.137.3998&rep=rep1&type=pdf. It might take a while to digest what's going on here, but it seems to have polynomial worst-case complexity in both the number of outputs and the number of dimensions.