Compressed sensing is a new signal acquisition method that acquires signal in a compressed form and then recovers the signal by the use of computational tools and techniques.This means fewer measurements of signal are needed and thus it will save huge amount of time and storage space.We,in this paper,consider the compressed sensing of sparse integer-valued signal(referred as “q-states signal” throughout the paper).In order to accelerate the speed of reconstruction,we adopt the sparse rather than dense measurement matrices.Using methods and tools developed in statistical physics,we locate the reconstruction limit for L 0-reconstruction method and propose a belief propagationbased algorithm that can deal with instance with large size and its typical reconstruction performance are also analyzed. Compressed sensing is a new signal acquisition method that acquires signal in a compressed form and then recovers the signal by the use of computational tools and techniques. This means fewer measurements of signal are needed and thus it will save huge amount of time and storage space. We, in this paper, consider the compressed sensing of sparse integer-valued signal (referred as “q-states signal ” throughout the paper). In order to accelerate the speed of reconstruction, we adopt the sparse rather than dense measurement matrices .Using methods and tools developed in statistical physics, we locate the reconstruction limit for L 0-reconstruction method and propose a belief propagation based algorithm that can deal with instance with large size and its typical reconstruction performance are also analyzed.