The problem of inverse halftoning is approached on the basis of compressed sensing, which enables us to make significantly efficient inference through the sparse representation of data to be inferred. For this purpose, we have adopted a DCT dictionary as a basis to represent image patches. In the Bayesian formulation of the problem taking the sparse representation into account, the MAP estimate is found to lead to an inverse halftoning algorithm which can be interpreted as a linear programming problem. Numerical simulations have successfully confirmed the effectiveness of the algorithm, which allows us to conclude that the compressed sensing approach is efficient to the problem of inverse halftoning.