Computational models for numerically simulating physical systems are increasingly being used to support decision-making processes in engineering. Processes such as design decisions, policy level analyses, and experimental design settings are often guided by information gained from computational modeling capabilities. To ensure effective application of results obtained through numerical simulation of computational models, uncertainty in model inputs must be propagated to uncertainty in model outputs. For expensive computational models, the many thousands of model evaluations required for traditional Monte Carlo based techniques for uncertainty propagation can be prohibitive. This paper presents a novel methodology for constructing surrogate representations of computational models via compressed sensing. Our approach exploits the approximate additivity inherent in many engineering computational modeling capabilities. We demonstrate our methodology on an analytical function and a cooled gas turbine blade application. The results of these applications reveal substantial computational savings over traditional Monte Carlo simulation with negligible loss of accuracy.