In Compressed Sensing (CS), Orthogonal Matching Pursuit (OMP) is a popular solver for recovering the sparse solution of an underdetermined system. The performance guarantees of OMP involving coherence-based arguments are known to be pessimistic. The present work aims at improving the performance guarantees via preconditioning. Since the systems Ax = y and GAx = Gy have the same set of solutions, both analytically and numerically, for an invertible and well-conditioned matrix G, while singling out the conditions, we determine G via a convex optimization problem in such a way that the performance guarantees of OMP get improved. Alongside the proof of concept, we demonstrate the implications of proposed improved bound towards dimensionality reduction by considering the reconstruction of a signal from a small set of its linearly projected samples. © 2021, The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.