In this paper, we address the problem of gesture recognition using the theory of random projection (RP) and by formulating the whole recognition problem as an -minimization problem. The gesture recognition system operates primarily on data from a single 3-axis accelerometer and comprises two main stages: a training stage and a testing stage. For training, the system employs dynamic time warping as well as affinity propagation to create exemplars for each gesture while for testing, the system projects all candidate traces and also the unknown trace onto the same lower dimensional subspace for recognition. A dictionary of 18 gestures is defined and a database of over 3700 traces is created from seven subjects on which the system is tested and evaluated. To the best of our knowledge, our dictionary of gestures is the largest in published studies related to acceleration-based gesture recognition. The system achieves almost perfect user-dependent recognition, and mixed-user and user-independent recognition accuracies that are highly competitive with systems based on statistical methods and with the other accelerometer-based gesture recognition systems available in the literature.