Boolean Network (BN) and its extension Probabilistic Boolean Network (PBN) are popular mathematical models for studying genetic regulatory networks. Apart from applications in genetic networks, BNs and PBNs also find many other applications in modeling financial risk, manufacturing systems and healthcare service systems. In this paper, we propose a novel Greedy Entry Removal (GER) algorithm for constructing sparse PBNs from rational transition probability matrices. We present theoretical upper bounds for both existing algorithms and the GER algorithm. Furthermore, we are the first to study and provide the lower bound of the captured problem under some simple condition. Our numerical experiments based on both synthetic and practical data demonstrate that GER gives the best performance among state-of-the-art sparse PBN construction algorithms.