In multi-user wireless communication systems, adaptive modulation and scheduling are promising techniques for increasing system throughput. However, for multi-carrier systems, they will lead to overwhelming user feedback overhead for Channel Quality Indication (CQI) in every subcarrier. In our work, novel CQI feedback schemes are proposed based on the recently proposed theory of Compressive Sensing (CS). First, the standard CS method is introduced to reduce CQI feedback overhead for multi-carrier Multiple-Input Multiple-Output transmission. In addition, via further research on the design of measurement matrix with standard CS, a novel CQI feedback scheme based on subspace CS is proposed by exploiting the subspace information of the underlying signal and the feedback rate is greatly decreased. Simulation results show that, with the same feedback rate, the throughputs with subspace CS outperform the Discrete Cosine Transform (DCT )-based method which is usually employed, and the throughputs with standard CS outperform DCT when the feedback rate is larger than 0.13 bits/subcarrier.