Multidimensional coherent spectroscopy provides insights into the vibronic structure and dynamics of complex systems. In general, the higher the dimensionality, the better the spectral discrimination and the more information that may be extracted about the system. A major impediment to widespread implementation of these methods, however, is that the acquisition time generally increases exponentially with dimensionality, prohibiting practical implementation. We demonstrate the use of nonuniform sampling based on the projection-slice theorem and inverse Radon transform within the context of a fifth-order, 4D technique (GAMERS) designed to correlate the vibrational contributions to different electronic states. Projection-reconstruction (PRO GAMERS) greatly reduces the data sampling requirements without sacrificing frequency resolution. The sensitivity of this technique is demonstrated to surpass conventional uniform sampling by orders of magnitude. The incorporation of projection-reconstruction into multidimensional coherent spectroscopy opens up the possibility to study the structure of complex chemical, biological, and physical systems with unprecedented detail.