Sparse Recovery With Non-Linear Fourier Features
This work addresses sparse recovery for researchers in machine learning, but it is incremental as it builds on existing non-linear Fourier feature methods.
The paper tackles the problem of sparse recovery in non-linear Fourier feature models, establishing theoretical bounds on the number of data points needed for perfect parameter recovery with high probability, with results compared to bounded orthonormal systems.
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.