CORRECTING DATA CORRUPTION ERRORS FOR MULTIVARIATE FUNCTION APPROXIMATION

Abstract

We discuss the problem of constructing an accurate function approximation when data are corrupted by unexpected errors. The unexpected corruption errors are different from the standard observational noise in the sense that they can have much larger magnitude and in most cases are sparse. By focusing on overdetermined case, we prove that the sparse corruption errors can be effectively eliminated by using l(1)-minimization, also known as the least absolute deviations method. In particular, we establish probabilistic error bounds of the l(1)-minimization solution with the corrupted data. Both the lower bound and the upper bound are related only to the errors of the l(1) and l(2)-minimization solutions with respect to the uncorrupted data and the sparsity of the corruption errors. This ensures that the l(1)-minimization solution with the corrupted data are close to the regression results with uncorrupted data, thus effectively eliminating the corruption errors. Several numerical examples are presented to verify the theoretical finding.