The present invention relates to a compressed sensing apparatus for compressed sensing of a set function consisting of a plurality of input sets containing a group of data. The apparatus includes: a plurality of sensing units acquiring a group of sampling data representing a plurality of sampling sets selected out of the plurality of input sets; a compression and computation unit enabling a compression to the group of data based on the group of sampling data in accordance with a Fourier basis set generated on the basis of the plurality of input sets and sampling sets, and a computation to compute a Fourier coefficient set based on a sparse regression technique which is in relation with the Fourier basis set; and a reconstruction unit predicting the group of data based on the Fourier coefficient set.