Fast and Provable Algorithms for Spectrally Sparse Signal Reconstruction via Low-Rank Hankel Matrix Completion
Skip to main content
eScholarship
Open Access Publications from the University of California

Department of Mathematics

Other bannerUC Davis

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

  • Author(s): Cai, Jian-Feng
  • Wang, Tianming
  • Wei, Ke
  • et al.

Published Web Location

https://arxiv.org/pdf/1606.01567.pdf
No data is associated with this publication.
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^2\log^2(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 $3$D arrays demonstrate the capability of FIHT on handling large and high-dimensional real data.

Item not freely available? Link broken?
Report a problem accessing this item