Recovery guarantees for polynomial coefficients from weakly dependent data with outliers (Q2209293)

One of the well-known methods to make the learning problem well-posed is to exploit additional properties of the target function. In this paper the authors study the problem of learning nonlinear functions from identically distributed data that are corrupted by outliers and/or contaminated by noise. By expressing the target function in the multivariate polynomial space, the learning problem is recast as a sparse robust linear regression problem where they incorporate both the unknown coefficients and the corruptions in a basis pursuit framework. The main contribution of this paper is to provide a reconstruction guarantee for the associated \(\ell_1\)-optimization problem where the sampling matrix is formed from the data matrix, its powers, and the identity matrix. They show that under weaker conditions, exact and stable recovery is guaranteed and that if the data is not independent but satisfies a suitable concentration inequality, one can provide a recovery guarantee for the learning function problem with corrupted data.