In this work, we consider the problem of data decoding in media-based modulation systems. The underlying problem is sparse because only a subset of the available transmit antennas is activated in each symbol; additionally, only one of the different mirror patterns is activated depending on the unknown data bits. Thus, the data recovery problem involves recovery of a block-sparse vector, with the additional structure that only one entry is active within each block. We term this structure as inclusion-exclusion sparsity, as the inclusion of an index in the active set precludes several other indices from being active. Devising efficient algorithms for recovering such sparse signals from noisy underdetermined linear measurements is an open problem. To this end, we propose a general, non-convex cost function that, when optimized, yields a sparse vector with additional structure, including, but not limited to, the inclusion-exclusion sparsity. Further, we propose a convex concave procedure (CCP) based algorithm for optimizing the cost function. The algorithm has low computational complexity and is globally convergent to a local optimum. Finally, we demonstrate the efficacy of our algorithm and its superior performance over existing data recovery schemes via Monte Carlo simulations.