Spectral Compressed Sensing via Projected Gradient Descent

Abstract

Let $x\in {\mathbb{C}}^n$ be a spectrally sparse signal consisting of $r$ complex sinusoids with or without damping. We consider the spectral compressed sensing problem, which is about reconstructing $x$ from its partial revealed entries. By utilizing the low rank structure of the Hankel matrix corresponding to $x$, we develop a computationally efficient algorithm for this problem. The algorithm starts from an initial guess computed via one-step hard thresholding followed by projection, and then proceeds by applying projected gradient descent iterations to a non-convex functional. Based on the sampling with replacement model, we prove that $O(r^2\log (n))$ observed entries are sufficient for our algorithm to achieve the successful recovery of a spectrally sparse signal. Moreover, extensive empirical performance comparisons show that our algorithm is competitive with other state-of-the-art spectral compressed sensing algorithms in terms of phase transitions and overall computational time.

References in corpus (12)

• General Deviants: An Analysis of Perturbations in Compressed Sensing
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Global Optimality of Local Search for Low Rank Matrix Recovery
• Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees
• Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decomposition
• Low-rank Solutions of Linear Matrix Equations via Procrustes Flow
• Fast Algorithms for Robust PCA via Gradient Descent
• Hankel Matrix Nuclear Norm Regularized Tensor Completion for $N$-dimensional Exponential Signals
• Convergence Analysis for Rectangular Matrix Completion Using Burer-Monteiro Factorization and Gradient Descent
• MUSIC for multidimensional spectral estimation: stability and super-resolution
• Rapid, Robust, and Reliable Blind Deconvolution via Nonconvex Optimization
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion

Cited by in corpus (2)

• Vandermonde Factorization of Hankel Matrix for Complex Exponential Signal Recovery -- Application in Fast NMR Spectroscopy
• Harnessing Structures in Big Data via Guaranteed Low-Rank Matrix Estimation