The growing deployment of deep learning models in real-world applications necessitates not only high predictive accuracy, but also mechanism to identify unreliable predictions, especially in high-stakes scenarios where decision risk must be minimized. Existing methods estimate uncertainty by leveraging predictive confidence (e.g., Softmax Response), structural characteristics of representation space (e.g., Mahalanobis distance), or stochastic variation in model outputs (e.g., Bayesian inference techniques such as Monte Carlo Dropout). In this work, we propose a novel uncertainty estimation (UE) framework based on sparse dictionary learning by identifying dictionary atoms associated with misclassified samples. We leverage pointwise mutual information (PMI) to quantify the association between sparse features and predictive failure. Our method -- Sparsity-based Uncertainty Estimation (SUE) -- is computationally efficient, is interpretable via atom-level analysis of the dictionary, has no assumption about the class distribution (like Mahalanobis distance), has a regularization effect which helps identifying the most fundamental blocks within the representation. We evaluated SUE on several NLU (GLUE tasks) and sentiment analysis (Twitter, ParaDetox, and Jigsaw) benchmarks. It performed better or achieved comparable performance to other methods. On average, SUE demonstrated the most consistent results across all benchmarks, achieving a 26% improvement over the second-best performing method (Softmax Response).