Parsimony, manifested as variously structured sparse and low rank representations of data, has been shown as a tremendously successful model in numerous domains of science, including signal and image processing, computer vision, and machine learning problems. Despite this success, parsimonious representation pursuit approaches practiced today face serious limitations stemming from their reliance on iterative optimization. In this project, we propose to develop a novel approach to parsimonious modeling that puts the pursuit process itself at the center, surfacing crucial aspects that are currently lost deep inside the optimization machinery. First, we will study the theoretical performance limitations of pursuit processes constrained by a fixed computational complexity budget, devising bounds on the tradeoff between performance and complexity (in the spirit of the rate-distortion tradeoff). Second, we will develop a principled way to construct families of pursuit processes that approach optimal performance at fixed complexity given a specific input data distribution, and devise tools for learning such processes on real data. Abandoning iterative representation pursuit in favour of a learned fixed-complexity function can lead to a dramatic improvement in performance, enabling previously impossible applications. It will also allow including parsimonious models into higher-level optimization problems, leading to novel modeling capabilities. In lieu of the existing generative parsimonious models, we will develop novel discriminative counterparts for uni- and multi-modal data, and show their utility in large-scale similarity learning. We will also construct efficient parsimonious modeling tools for problems involving unknown data transformation or correspondence. We will apply these methods to several challenging real-world problems in signal processing, computer vision, medical imaging, and multimedia retrieval, which will be developed to the level of prototype systems.