Computational Mathematics and Statistics Seminar by Philip Lo: The Sample Complexity of Noisy Curve Recovery

Speaker: Philip Lo, University of Chicago

Title: The Sample Complexity of Noisy Curve Recovery

Abstract: We consider the problem of recovering a high dimensional curve from noisy observations. In the low noise regime, a straightforward approach of locally approximating the data with curves is feasible. However, in the high noise regime, it becomes impossible to localize any data point to a portion of the curve. Indeed, we will demonstrate an information-theoretic lower bound on the sample complexity of high-noise curve recovery, that the number of observations needed to estimate a curve with high noise is cubic in the noise level. We will then show preliminary results on a third-moment based recovery algorithm for recovering noisy curves with a particular multiscale structure. Joint work with Yuehaw Khoo.

Computational Mathematics and Statistics Seminar