  We study the robust matrix completion problem for the low-rank Hankel matrix,
which detects the sparse corruptions caused by extreme outliers while we try to
recover the original Hankel matrix from the partial observation. In this paper,
we explore the convenient Hankel structure and propose a novel non-convex
algorithm, coined Hankel Structured Gradient Descent (HSGD), for large-scale
robust Hankel matrix completion problems. HSGD is highly computing- and
sample-efficient compared to the state-of-the-arts. The recovery guarantee with
a linear convergence rate has been established for HSGD under some mild
assumptions. The empirical advantages of HSGD are verified on both synthetic
datasets and real-world nuclear magnetic resonance signals.
