Music onset detection is significant and essential for obtaining the high-level music features such as rhythm, beat, music paragraph and structure. The traditional methods for onset detection which employ Short Time Fourier Transform (STFT)-based or Wavelet Transform (WT)-based features to characterize music signal generally lack adaptiveness for representing the stationary and non-stationary part of the music signal. This will lead to the degraded performance for music note onset detection. To solve this problem, a new algorithm for note onset detection based on sparse decomposition is proposed. Firstly, the musical signals are sparsely decomposed with Matching Pursuit (MP), and then the hybrid detection algorithm which combines namely the Degree of Explanation (DE) and the Change of Partials (CP) is applied to the sparse representation of the music signal. Finally, a modified peak-picking algorithm is employed to generate onset vectors. The experiments on the dataset with 2050 onsets show that our results are superior to those of MIREX 2013. For the polyphonic music which is the most widely used form in our real life, the proposed algorithm has better performance than the other algorithms.