We present a generic method for automatic detection of abnormal regions in medical images as deviations from a normative data base. The algorithm decomposes an image, or more broadly a function defined on the image grid, into the superposition of a normal part and a residual term. A statistical model is constructed with regional sparse learning to represent normative anatomical variations among a reference population (e.g., healthy controls), in conjunction with a Markov random field regularization that ensures mutual consistency of the regional learning among partially overlapping image blocks. The decomposition is performed in a principled way so that the normal part fits well with the learned normative model, while the residual term absorbs pathological patterns, which may then be detected through a statistical significance test. The decomposition is applied to multiple image features from an individual scan, detecting abnormalities using both intensity and shape information. We form an iterative scheme that interleaves abnormality detection with deformable registration, gradually improving robustness of the spatial normalization and precision of the detection. The algorithm is evaluated with simulated images and clinical data of brain lesions, and is shown to achieve robust deformable registration and localize pathological regions simultaneously. The algorithm is also applied on images from Alzheimer’s disease patients to demonstrate the generality of the method.