The bound that arises out of sparse recovery analysis in compressed sensing involves input signal sparsity and some property of the sensing matrix. An effort has therefore been made in the literature to optimize sensing matrices for optimal recovery using this property. We discover, in the specific case of optimizing codes for the CACTI camera, that the popular method of mutual coherence minimization does not produce optimal results: codes designed to optimize effective dictionary coherence often perform worse than random codes in terms of mean squared reconstruction error. This surprising phenomenon leads us to investigate the reliability of the coherence bound for matrix optimization, in terms of its looseness. We examine, on simulated data, the looseness of the bound as it propagates across various steps of the inequalities in a derivation leading to the final bound. We then similarly examine an alternate bound derived by Tang, G. et al, based on the $\ell_1/\ell_{\infty}$ notion of sparsity, which is a compromise between coherence and the restricted isometry constant (RIC). Moreover, we also perform a bound looseness analysis for the RIC as derived by Cai, T. et al. The conclusion of these efforts is that coherence optimization is problematic not only because of the coherence bound on the RIC, but also the RIC bound itself. These negative results imply that despite the success of previous work in designing sensing matrices based on optimization of a matrix quality factor, one needs to exercise caution in using them for practical sensing matrix design. We then introduce a paradigm for optimizing sensing matrices that overcomes the looseness of compressed sensing upper bounds using an average case error approach. We show a proof-of-concept design using this paradigm that performs convincingly better than coherence-based design in the CACTI case, and no worse for general matrices.