Several waveforms have been recently proposed in the literature as alternatives to orthogonal frequency division multiplexing (OFDM) for frequency selective channels. However, in order to achieve a superior performance, it is necessary to employ iterative equalization. In this paper, we consider the sparse Walsh-Hadamard (SWH) waveform with maximum a-Posterior (MAP) equalization. We show that the inherent structure of the SWH matrix allows a significant reduction in the number of multiplications required for the MAP equalizer implementation. The proposed solutions is compared with the zero padding single carrier (ZP-SC) with MAP equalization. We show that SWH with MAP equalization achieves a good trade-off performance vs complexity compared with ZP-SC. In particular, for 16-QAM under the Proakis C channel, ZP-SC is not even feasible while SWH with MAP equalization has manageable complexity.