Underlay cognitive networks should follow strict interference thresholds to operate in parallel with primary networks. This constraint limits their transmission power and eventually the coverage area. Therefore, in this paper, we first design a new approach for asynchronous narrow-band interference (NBI) estimation and mitigation in orthogonal frequency-division multiplexing cognitive radio networks that does not require prior knowledge of the NBI characteristics. Our proposed approach allows the primary user to exploit the sparsity of the secondary users' interference signal to recover it and cancel it based on sparse signal recovery theory. We also propose two subcarrier selection schemes that allow the primary user to further reduce the effect of the secondary users' interference based on sparse signal recovery algorithms. We show that although the primary and secondary transmissions are performed at the same time, the performance of our proposed techniques approach the interference-free limit over practical ranges of NBI power levels.