  Random non-linear Fourier features have recently shown remarkable performance
in a wide-range of regression and classification applications. Motivated by
this success, this article focuses on a sparse non-linear Fourier feature (NFF)
model. We provide a characterization of the sufficient number of data points
that guarantee perfect recovery of the unknown parameters with
high-probability. In particular, we show how the sufficient number of data
points depends on the kernel matrix associated with the probability
distribution function of the input data. We compare our results with the
recoverability bounds for the bounded orthonormal systems and provide examples
that illustrate sparse recovery under the NFF model.
