Various methods and devices are provided to address the need for reduced compression complexity in the area of compressive sensing. In one method, a vector x is compressed to obtain a vector y according to y=ΦRDx, where ΦRD=UΦRM·ΦRM is a compressive sensing matrix constructed using a second-order Reed-Muller code or a subcode of a second-order Reed-Muller code and U is a unitary matrix from the real or complex Clifford group G. In another method, vector y is decompressed to obtain vector x also according to y=ΦRDx. In some embodiments, decompression may involve computing y′=U−1y and then determining the vector x using the computed y′.