Greedy sparse recovery has become a popular tool in many applications, although its complexity is still prohibitive when large sparsifying dictionaries or sensing matrices have to be exploited. In this paper, we formulate first a new class of sparse recovery problems that exploit multidimensional dictionaries and the separability of the measurement matrices that appear in certain problems. Then we develop a new algorithm, Separable Multidimensional Orthogonal Matching Pursuit (SMOMP), which can solve this class of problems with low complexity. Finally, we apply SMOMP to the problem of joint localization and communication at mmWave, and numerically show its effectiveness to provide, at a reasonable complexity, high accuracy channel and position estimations.