Cyclostationary feature detection is one of the most powerful spectrum sensing techniques used for cognitive radio (CR) systems. This is because of its robustness against noise uncertainties. However, this technique needs high sampling rates, which is limited by the state-of the-art analog to digital converters (ADCs), especially in wideband regime. Comressive sensing (CS) was used by many researchers for solving this problem via sub-Nyquist sampling rates. However CS solves the high sampling rate problem, but it does not reduce complexity considerably. This is because spectrum sensing is performed in three steps: sensing compressed measurements, then reconstructing the Nyquist rate signal, and finally performing cyclostationary detection (CD) on the reconstructed signal. In this paper we suggest performing CD directly on the compressed measurements skipping the reconstruction step which is the most complex step in CS. This can be realized by designing the sensing matrix with constraints different from those used in the conventional CS. Results show that performance is improved relative to applying CD on the Nyquist rate signal. This is in addition to reduction in receiver complexity resulting from reducing sampling rates. A detection probability of 78.7% can be achieved with only 7% of samples used by the conventional cyclostationary detection technique that achieves a detection probability of 32.7%.