Method of Moments for Estimation of Noisy Curves

Abstract

In this paper, we study the problem of recovering a ground truth high dimensional piecewise linear curve $C^{\ast }(t):[0,1]\to {\mathbb{R}}^d$ from a high noise Gaussian point cloud with covariance ${\sigma }^{2}I$ centered around the curve. We establish that the sample complexity of recovering $C^{\ast }$ from data scales with order at least ${\sigma }^6$. We then show that recovery of a piecewise linear curve from the third moment is locally well-posed, and hence $O({\sigma }^6)$ samples is also sufficient for recovery. We propose methods to recover a curve from data based on a fitting to the third moment tensor with a careful initialization strategy and conduct some numerical experiments verifying the ability of our methods to recover curves. All code for our numerical experiments is publicly available on GitHub.

To appear in SIAM Journal on Mathematics of Data Science