Sub-Nyquist sampling for spectrum sensing has the advantages of reducing the sampling and computational complexity burdens. However, determining the sparsity of the underlying spectrum is still a challenging issue for this approach. Along this line, this paper proposes an algorithm for narrowband spectrum sensing based on tracking the convergence patterns in sparse coding of compressed received signals. First, a compressed version of a received signal at the location of interest is obtained according to the principle of compressive sensing. Then, the signal is reconstructed via sparse recovery over a learned dictionary. While performing sparse recovery, we calculate the sparse coding convergence rate in terms of the decay rate of the energy of residual vectors. Such a decay rate is conveniently quantified in terms of the gradient operator. This means that while compressive sensing allows for sub-Nyquist sampling thereby reducing the analog-to-digital conversion overhead, the sparse recovery process could be effectively exploited to reveal spectrum occupancy. Furthermore, as an extension to this approach, we consider feeding the energy decay gradient vectors as features for a machine learning-based classification process. This classification further enhances the performance of the proposed algorithm. The proposed algorithm is shown to have excellent performances in terms of the probability-of-detection and false-alarm-rate measures. This result is validated through numerical experiments conducted over synthetic data as well as real-life measurements of received signals. Moreover, we show that the proposed algorithm has a tractable computational complexity, allowing for real-time operation.