Noisy and missing data are prevalent in many real-world statistical estimation problems. Popular techniques for handling nonidealities in data are often difficult to analyze theoretically and may terminate in substantially different local optima of a nonconvex objective function -- these problems are only exacerbated in high dimensions. We present new methods for constructing high-dimensional...