In the last few years, we have witnessed an explosion in applications of sparse representation, the majority of which share the need for finding sparse solutions of underdetermined systems of linear equations (USLE's). Based on recently proposed smoothed lscr⁰-norm (SL0), we develop a noise-tolerant algorithm for sparse representation, namely Robust-SL0, enjoying the same computational advantages of SL0, while demonstrating remarkable robustness against noise. The proposed algorithm is developed by adopting the corresponding optimization problem for noisy settings, followed by theoretically-justified approximation to reduce the complexity. Stability properties of robust-SL0 are rigorously analyzed, both analytically and experimentally, revealing a remarkable improvement in performance over SL0 and other competing algorithms, in the presence of noise.