An electronic device has a transmit circuit and a processing circuit. The processing circuit outputs a first portion of compressive sensing (CS) samples corresponding to a signal segment to another electronic device via the transmit circuit, and selectively outputs a second portion of the CS samples corresponding to the signal segment to another electronic device via the transmit circuit according to a response of another electronic device. In this way, a balance between the compression ratio and the reconstruction quality/speed can be achieved. Moreover, the signal reconstruction performed at the processing circuit may employ a multi-resolution/multi-scale reconstruction scheme to achieve a balance between the dictionary size and the reconstruction quality/speed, and/or may employ a multi-stage reconstruction scheme to achieve a balance between the reconstruction algorithm control setting and the reconstruction quality/speed. In addition, dictionary weighting, online dictionary update, and/or point constraints may be used to improve the reconstruction quality.