1. A data compression device that compresses data used for performing a search, recognition or prediction, the data compression device comprising: a processor; and memory having stored therein program instructions which cause the processor to extract features of the data in the form of an n dimensional feature quantity vector x; perform dimensional compression on the feature quantity vector x by multiplying the feature quantity vector x by a check matrix H of a random code, which consists of binary elements 0 or 1, to generate a compressed m dimensional feature quantity vector y, where n>m; and reduce a quantization size of each element y k of the compressed feature quantity vector y, wherein said dimensional compression adds values, in said feature quantity vector x corresponding to 1 elements of said check matrix on a row by row basis, to generate the compressed feature quantity vector y.