Robust spectral compressive sensing via vanilla gradient descent

This paper investigates robust recovery of an undamped or damped spectrally sparse signal from its partially revealed noisy entries within the framework of spectral compressed sensing. Nonconvex optimization approaches such as projected gradient descent (PGD) based on low-rank Hankel matrix completion model have recently been proposed for this problem. However, the analysis of PGD relies heavily on the operation of projection onto feasible set involving two tuning parameters, and the theoretical guarantee in noisy case is still missing. In this paper, we propose a vanilla gradient descent (VGD) algorithm without projection based on low-rank Hankel noisy matrix completion, and prove that VGD can achieve the sample complexity $O(K^2\log^2 N)$, where $K$ is the number of the complex exponential functions and $N$ is the signal dimensions, to ensure robust recovery from noisy observations when noise parameter satisfies some mild conditions. Moreover, we show the possible performance loss of PGD, suffering from the inevitable estimation of the above two unknown parameters of feasible set. Numerical simulations are provided to corroborate our analysis and show more stable performance obtained by VGD than PGD when dealing with damped spectrally sparse signal.