Several recent works have shown the advantages of using phase-change memory (PCM) in developing brain-inspired computing approaches. In particular, PCM cells have been applied to the direct computation of matrix-vector multiplications in the analog domain. However, the intrinsic nonlinearity of these cells with respect to the applied voltage is detrimental. In this paper we consider a PCM array as the encoder in a Compressed Sensing (CS) acquisition system, and investigate the effect of the non-linearity of the cells. We introduce a CS decoding strategy that is able to compensate for PCM nonlinearities by means of an iterative approach. At each step, the current signal estimate is used to approximate the average behaviour of the PCM cells used in the encoder. Monte Carlo simulations relying on a PCM model extracted from an STMicrolectronics 90 nm BCD chip validate the performance of the algorithm with various degrees of nonlinearities, showing up to 35 dB increase in median performance as compared to standard decoding procedures.