Compressed Sensing (CS) offers a method to solve the channel estimation problems for an underwater acoustic system, based on the existence of a sparse representation of the treated signal and an overcomplete dictionary with a set of non-orthogonal bases. In this paper, we proposed a new approach to optimize dictionaries by decreasing the average measure of the mutual coherence of the effective dictionary. A fixed link between the average mutual coherence and the CS performance is indicated by designing three factors: operating bandwidth, the number of pilot subcarriers, and coherence bandwidth. Both the Orthogonal Matching Pursuit (OMP) and the Basis Pursuit De-Noising (BPDN) are compared to the Dantzig Selector (DS) for different Signal Noise Ratio (SNR) and shown to benefit from the newly designed dictionary. Numerical simulations and experimental data of an OFDM receiver are used to evaluate the proposed method in comparison with the conventional Least-Square (LS) estimator. The results show that the dictionary with a better condition considerably improves the performance of the channel estimation.