  Orthogonal Matching Pursuit and Basis Pursuit are popular reconstruction
algorithms for recovery of sparse signals. The exact recovery property of both
the methods has a relation with the coherence of the underlying redundant
dictionary, i.e. a frame. A frame with low coherence provides better guarantees
for exact recovery. An equivalent formulation of the associated linear system
is obtained via premultiplication by a non-singular matrix. In view of bounds
that guarantee sparse recovery, it is very useful to generate the
preconditioner in such way that the preconditioned frame has low coherence as
compared to the original. In this paper, we discuss the impact of
preconditioning on sparse recovery. Further, we formulate a convex optimization
problem for designing the preconditioner that yields a frame with improved
coherence. In addition to reducing coherence, we focus on designing well
conditioned frames and numerically study the relationship between the condition
number of the preconditioner and the coherence of the new frame. Alongside
theoretical justifications, we demonstrate through simulations the efficacy of
the preconditioner in reducing coherence as well as recovering sparse signals.
