In this paper, we present a general framework for robust nonlinear regression that leverages concepts from the field of compressive sensing to simultaneously detect outliers and determine optimally sparse representations of noisy data from arbitrary sets of basis functions. Our framework employs a two-component noise model and compressive sensing recovery techniques to exploit the inherent sparsity of outliers while (optionally) performing model order reduction over all predictive variables and basis functions. As such, our algorithm can de-emphasize the effect of predictive variables that become uncorrelated with the measurement data. This desirable property has various applications like real-time detection of faulty sensors and sensor jamming in wireless sensor networks. After developing our framework and making the connection to compressive sensing theory, we present simulations that demonstrate the superior performance of our framework with respect to classic robust regression techniques like least absolute value and iteratively reweighted least-squares.