We give a polynomial time algorithm for the lossy population recovery problem. In this problem, the goal is to approximately learn an unknown distribution on binary strings of length n from lossy samples: for some parameter μ each coordinate of the sample is preserved with probability μ and otherwise is replaced by a '?'. The running time and number of samples needed for our algorithm is polynomial in n and 1/ε for each fixed μ > 0. This improves on the algorithm of Wigderson and Yehudayoff  that runs in quasi-polynomial time for any fixed μ > 0 and the polynomial time algorithm of Dvir et al  which was shown to work for μ > 0.30 by Batman et al . In fact, our algorithm also works in the more general framework of Batman et al.  in which there is no a priori bound on the size of the support of the distribution. The algorithm we analyze is implicit in previous work , ; our main contribution is to analyze the algorithm by showing (via linear programming duality and connections to complex analysis) that a certain matrix associated with the problem has a robust local inverse even though its condition number is exponentially small. A corollary of our result is the first polynomial time algorithm for learning DNFs in the restriction access model of Dvir et al .