We apply deep generative models to the task of generating protein structures, toward application in protein design. We encode protein structures in terms of pairwise distances between alpha-carbons on the protein backbone, which by construction eliminates the need for the generative model to learn translational and rotational symmetries. We then introduce a convex formulation of corruption-robust 3-D structure recovery to fold protein structures from generated pairwise distance matrices, and solve this optimization problem using the Alternating Direction Method of Multipliers. Finally, we demonstrate the effectiveness of our models by predicting completions of corrupted protein structures and show that in many cases the models infer biochemically viable solutions.