Atomic decomposition (AD) can be used to efficiently decompose an arbitrary signal. In this paper, we present a method to detect neonatal electroencephalogram (EEG) seizure based on AD via orthogonal matching pursuit using a novel, application-specific, dictionary. The dictionary consists of pseudoperiodic Duffing oscillator atoms which are designed to be coherent with the seizure epochs. The relative structural complexity (a measure of the rate of convergence of AD) is used as the sole feature for seizure detection. The proposed feature was tested on a large clinical dataset of 826 h of EEG data from 18 full-term newborns with 1389 seizures. The seizure detection system using the proposed dictionary was able to achieve a median receiver operator characteristic area of 0.91 (IQR 0.87-0.95) across 18 neonates.