Greed is Super: A Fast Algorithm for Super-Resolution

Abstract

We present a fast two-phase algorithm for super-resolution with strong theoretical guarantees. Given the low-frequency part of the spectrum of a sequence of impulses, Phase I consists of a greedy algorithm that roughly estimates the impulse positions. These estimates are then refined by local optimization in Phase II. In contrast to the convex relaxation proposed by Candès et al., our approach has a low computational complexity but requires the impulses to be separated by an additional logarithmic factor to succeed. The backbone of our work is the fundamental work of Slepian et al. involving discrete prolate spheroidal wave functions and their unique properties.

Cited by in corpus (8)

• Convolutional Phase Retrieval via Gradient Descent
• Sampling and Reconstruction of Sparse Signals in Shift-Invariant Spaces: Generalized Shannon's Theorem Meets Compressive Sensing
• When does OMP achieve exact recovery with continuous dictionaries?
• Regularized Gradient Descent: A Nonconvex Recipe for Fast Joint Blind Deconvolution and Demixing
• Device Activity Detection and Channel Estimation for Millimeter-Wave Massive MIMO
• Stable Super-Resolution of Images: A Theoretical Study
• Time-Limited Toeplitz Operators on Abelian Groups: Applications in Information Theory and Subspace Approximation
• The Nonconvex Geometry of Linear Inverse Problems