Robust spectral compressive sensing via vanilla gradient descent

Abstract

This paper investigates the recovery of a spectrally sparse signal from its partially revealed noisy entries within the framework of spectral compressive sensing. Nonconvex optimization approaches have recently been proposed based on low-rank Hankel matrix completion and projected gradient descent (PGD). The PGD however involves unknown tuning parameters and its theoretical analysis is available only in the absence of noise. In this paper, we propose a hyperparameter-free, vanilla gradient descent (VGD) algorithm and prove that the VGD enables robust recovery of an $N$-dimensional $K$-spectrally-sparse signal from order $K^{2}lo{g}^{2}N$ number of noisy samples under coherence and other mild conditions. The above sample complexity increases by factor $logN$ as compared with PGD without noise. Numerical simulations are provided that corroborate our analysis and show advantageous performances of VGD.

The definition of the Leave-One-Out sequence for the low-rank Hankel completion model in Section III-B is still uncertain

References in corpus (3)

• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Entrywise Eigenvector Analysis of Random Matrices with Low Expected Rank
• New Low Rank Optimization Model and Convex Approach for Robust Spectral Compressed Sensing