Brain-machine interfaces (BMIs) rely on decoding neuronal activity from a large number of electrodes. The implantation procedures, however, do not guarantee that all recorded units encode task-relevant information: selection of task-relevant neurons is critical to performance but is typically performed heuristically. Here, we describe an algorithm for decoding/classification of volitional actions from multiple spike trains, which automatically selects the relevant neurons. The method is based on sparse decomposition of the high-dimensional neuronal feature space, projecting it onto a low-dimensional space of codes serving as unique class labels. The new method is tested against a range of existing methods using recordings of the activity of 716 neurons in 11 neurosurgical patients who performed speech tasks. The suggested method achieves significantly higher accuracies, orders of magnitude faster than existing methods, rendering sparse decomposition highly attractive for BMIs.