Recently it has been shown that sparse channel estimation, implemented with orthogonal matching pursuit (OMP) and basis pursuit (BP) algorithms, has impressive performance gains over alternatives that do not take advantage of the channel sparsity, for underwater acoustic (UWA) communications. We in this paper compare the performance and complexity of three popular BP algorithms, namely l1_ls, SpaRSA, and YALL1, using both simulation and experimental data for underwater orthogonal frequency division multiplexing (OFDM) systems with both single and multiple transmitters. We find that all BP solvers achieve similar block-error-rate performance, considerably outperforming OMP. In terms of complexity, both SpaRSA and YALL1 reduce the runtime by about one order of magnitude relative to l1 ls, catching up with OMP. The efficient BP solvers such as SpaRSA and YALL1 are thus appealing to be implemented in real-time underwater OFDM modems.