Compressed Sensing (CS) is a novel signal compression technique in which signal is compressed while sensing. The compressed signal is recovered with only few number of observations compared to conventional Shannon-Nyquist sampling and thus reducing the storage requirements. This research paper is focused on application of Compressed Sensing (CS) for musical signal processing. In this paper, we have proposed the structured class of sensing matrices like random Toeplitz matrix and random Circulant matrix for CS based musical signal processing. Along with this we have proposed the random partial Hadamard matrix, random Block-Diagonal Hadamard and random projection sensing matrix for CS based musical signal processing. Then, we evaluated the performance for the best basis selection for musical signal processing using DCT and DST. The result shows that DCT outperforms DST in terms of signal reconstruction time, signal reconstruction error and signal to noise ratio (SNR). Finally, we have performed the comparative analysis between all proposed sensing matrices for the best random sensing matrix selection for CS based musical signal processing using performance metrics such as number of measurements (m), compression ratios (CR), signal reconstruction time (in seconds), root mean square error (RMSE) and SNR etc. The result shows that the random partial Hadamard sensing matrix shows better performance compared to other sensing matrices.