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 based on heuristics. 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 simulations and recordings of the activity of 1592 neurons in 23 neurosurgical patients who performed motor or speech tasks. The parameter estimation algorithm is orders of magnitude faster than existing methods and achieves significantly higher accuracies for both simulations and human data, rendering sparse decoding highly attractive for BMIs.