Fast and Provable Algorithms for Spectrally Sparse Signal Reconstruction via Low-Rank Hankel Matrix Completion

2016/06/05 by Jian‐Feng Cai, Cai, Jian-Feng, Tianming Wang +3 · 1 citation
Computer Science · Engineering · #FOS: Computer and information sciences #Image and Signal Denoising Methods #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1606.01567

openalex publication_date 2016/06/05 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28

Abstract

A spectrally sparse signal of order r is a mixture of r damped or undamped complex sinusoids. This paper investigates the problem of reconstructing spectrally sparse signals from a random subset of n regular time domain samples, which can be reformulated as a low rank Hankel matrix completion problem. We introduce an iterative hard thresholding (IHT) algorithm and a fast iterative hard thresholding (FIHT) algorithm for efficient reconstruction of spectrally sparse signals via low rank Hankel matrix completion. Theoretical recovery guarantees have been established for FIHT, showing that O(r²log²(n)) number of samples are sufficient for exact recovery with high probability. Empirical performance comparisons establish significant computational advantages for IHT and FIHT. In particular, numerical simulations on 3D arrays demonstrate the capability of FIHT on handling large and high-dimensional real data.

Citations

• A framelet-based image inpainting algorithm
• Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• A Simpler Approach to Matrix Completion
• Iterative hard thresholding for compressed sensing
• MUSIC for single-snapshot spectral estimation: Stability and super-resolution

Cited by

• Fast and Provable Hankel Tensor Completion for Multi-measurement Spectral Compressed Sensing

Related

• Projected Wirtinger Gradient Descent for Low-Rank Hankel Matrix Completion in Spectral Compressed Sensing
• Spectral Compressed Sensing via Projected Gradient Descent
• Robust spectral compressive sensing via vanilla gradient descent
• Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
• A Low-rank Projected Proximal Gradient Method for Spectral Compressed Sensing