A method for image reconstruction includes defining a dictionary including a set of atoms selected such that patches of natural images can be represented as linear combinations of the atoms. A binary input image, including a single bit of input image data per input pixel, is captured using an image sensor. A maximum-likelihood (ML) estimator is applied, subject to a sparse synthesis prior derived from the dictionary, to the input image data so as to reconstruct an output image comprising multiple bits per output pixel of output image data.