# Spectral Compressed Sensing via Projected Gradient Descent

arXiv: https://arxiv.org/abs/1707.09726 · HTML: https://mlsanity.com/paper/1707.09726/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jul 2017.

## Built on by (most cited first, 5 of 5)

- [Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent](https://mlsanity.com/paper/2406.07409/) (2024)
- [Deep Hashing with Semantic Hash Centers for Image Retrieval](https://mlsanity.com/paper/2507.08404/) (2025)
- [On Asymptotic Linear Convergence of Projected Gradient Descent for Constrained Least Squares](https://mlsanity.com/paper/2112.11760/) (2021)
- [Learning Transition Operators From Sparse Space-Time Samples](https://mlsanity.com/paper/2212.00746/) (2022)
- [Euclidean Distance Matrix Completion via Asymmetric Projected Gradient Descent](https://mlsanity.com/paper/2504.19530/) (2025)

## Abstract (arXiv)

Let x∈mathbbCn 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(r2log(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.