  We study the problem of inverting a deep generative model with ReLU
activations. Inversion corresponds to finding a latent code vector that
explains observed measurements as much as possible. In most prior works this is
performed by attempting to solve a non-convex optimization problem involving
the generator. In this paper we obtain several novel theoretical results for
the inversion problem.
  We show that for the realizable case, single layer inversion can be performed
exactly in polynomial time, by solving a linear program. Further, we show that
for multiple layers, inversion is NP-hard and the pre-image set can be
non-convex.
  For generative models of arbitrary depth, we show that exact recovery is
possible in polynomial time with high probability, if the layers are expanding
and the weights are randomly selected. Very recent work analyzed the same
problem for gradient descent inversion. Their analysis requires significantly
higher expansion (logarithmic in the latent dimension) while our proposed
algorithm can provably reconstruct even with constant factor expansion. We also
provide provable error bounds for different norms for reconstructing noisy
observations. Our empirical validation demonstrates that we obtain better
reconstructions when the latent dimension is large.
