We address efficient preconditioning techniques for the inexact second-order methods applied to solve various sparse approximation problems arising in signal/image reconstruction. The preconditioners exploit two features of such problems: (i) sparsity of the solution, and (ii) near-orthogonality of the matrices involved. The latter originates from the restricted isometry properties frequently assumed in such applications. Spectral analysis of the preconditioners and their practical efficiency when solving linear systems in the Newton Conjugate Gradient method will be presented. If time permits then a few comments on the some other problems originating from the "Big Data" buzz will also be given.