  Nonlinear function estimation is core to modern machine learning
applications. In this paper, to perform nonlinear function estimation, we
reduce a nonlinear inverse problem to a linear one using a polynomial kernel
expansion. These kernels increase the feature set, and may result in poorly
conditioned matrices. Nonetheless, we show several examples where the matrix in
our linear inverse problem contains only mild linear correlations among
columns. The coefficients vector is modeled within a Bayesian setting for which
approximate message passing (AMP), an algorithmic framework for signal
reconstruction, offers Bayes-optimal signal reconstruction quality. While the
Bayesian setting limits the scope of our work, it is a first step toward
estimation of real world nonlinear functions. The coefficients vector is
estimated using two AMP-based approaches, a Bayesian one and empirical Bayes.
Numerical results confirm that our AMP-based approaches learn the function
better than LASSO, offering markedly lower error in predicting test data.
