Abstract: Under the influence of additive white Gaussian noise, the classical dectionary learning algorithms, such as K-means Singular Value Decomposition (K-SVD), Recursive Least Squares Dictionary Learning Algorithm (RLS-DLA) and K-means Singular Value Decomposition Denoising (K-SVDD), can not effectively remove the noise of Cubic Phase Signal (CPS). A novel dictionary learning algorithm for denoising CPS is proposed. Firstly,the dictionary is learned by using the RLS-DLA algorithm. Secondly,the update stage of the RLS-DLA algorithm is modified by using Non-Linear Least Squares (NLLS) in the algorithm. Finally, the signal is reconstructed via sparse representations over learned dictionary.Signal to Noise Ratio (SNR) obtained by using the novel dictionary learning algorithm is obviously higher than other algorithms,and the Mean Squares Error (MSE) obtained by using the novel dictionary learning algorithm is obviously lower than other algorithms. Therefore there is obviously denoising performance for using the dictionary learned by the algorithm to sparsely represent CPS. The experimental results show that the average SNR obtained by using the algorithm is9.55 dB, 13.94 dB and9.76 dB higher than K-SVD, RLS-DLS and K-SVDD.