The decomposition of high-density surface EMG (HD-sEMG) interference patterns into the contribution of motor units is still a challenging task. We introduce a new, fast solution to this problem. The method uses a data-driven approach for selecting a set of electrodes to enable discrimination of present motor unit action potentials (MUAPs). Then, using shapes detected on these channels, the hierarchical clustering algorithm as reported by Quian Quiroga et al. (Neural Comput 16:1661-1687, 2004) is extended for multichannel data in order to obtain the motor unit action potential (MUAP) signatures. After this first step, more motor unit firings are obtained using the extracted signatures by a novel demixing technique. In this demixing stage, we propose a time-efficient solution for the general convolutive system that models the motor unit firings on the HD-sEMG grid. We constrain this system by using the extracted signatures as prior knowledge and reconstruct the firing patterns in a computationally efficient way. The algorithm performance is successfully verified on simulated data containing up to 20 different MUAP signatures. Moreover, we tested the method on real low contraction recordings from the lateral vastus leg muscle by comparing the algorithm's output to the results obtained by manual analysis of the data from two independent trained operators. The proposed method showed to perform about equally successful as the operators.