We consider a class of data analysis problems where the input data has been embedded into a lower-dimensional space using a randomized and periodic feature map. An is the technique of random Fourier features, which have been successfully employed in speeding up kernel-based inference in large datasets. I

n this work, we demonstrate that with a mild increase in the dimension of the embedding, it is also possible to stably reconstruct the data vector from such periodic random feature maps, provided that the underlying data is sparse enough. In particular, we propose a simple, numerically stable algorithm for reconstructing the data vector given the nonlinear features and analyze its sample complexity. We support the efficacy of our approach via numerical experiments.