Sparse methods are widely used in image and audio processing for denoising and classification, but there have been few previous applications to neural signals for brain-computer interfaces (BCIs). We used the dictionary- learning algorithm K-SVD, coupled with Orthogonal Matching Pursuit, to learn dictionaries of spatial and temporal EEG primitives. We applied these to P300 and ErrP data to denoise the EEG and better estimate the underlying P300 and ErrP signals. This methodology improved single-trial classification performance across 13 of 14 subjects, indicating that some of the background noise in EEG signals, presumably from neural or muscular sources, is highly structured. Furthermore, this structure can be captured via dictionary learning and sparse coding algorithms, and exploited to improve BCIs.