supplementary material for paper: Constant-Expansion Suffices for Compressed Sensing with Generative Priors

In this section we prove Theorem 3.2. The two arguments are essentially identical, and we will focus on the former. See [20] for a reference on the first bound. The second bound is by concentration of chisquared with k degrees of freedom. We check that f and g satisfy the three conditions of Theorem 4.4 with appropriate parameters. Finally, since Pr[W Θ] 1/2, it follows that conditioning on Θ at most doubles the failure probability.