Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion

DOI10.1016/J.ACHA.2017.04.004zbMATH Open1442.94017arXiv1606.01567OpenAlexW2962694024MaRDI QIDQ1990969FDOQ1990969

Authors: Ke Wei, Jian-Feng Cai, Tianming Wang 

Publication date: 29 October 2018

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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}lo{g}^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.

Full work available at URL: https://arxiv.org/abs/1606.01567

Recommendations

• Spectral Compressed Sensing via Projected Gradient Descent
• Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery
• Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit

zbMATH Keywords

iterative hard thresholdingcomposite hard thresholding operatorlow rank Hankel matrix completionspectrally sparse signal

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Sampling theory in information and communication theory (94A20)

Cites Work

• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• Exact matrix completion via convex optimization
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• Compressed sensing
• User-friendly tail bounds for sums of random matrices
• Iterative hard thresholding for compressed sensing
• Framelet based deconvolution
• Wavelet Algorithms for High-Resolution Image Reconstruction
• A framelet-based image inpainting algorithm
• Low-rank matrix completion by Riemannian optimization
• A simpler approach to matrix completion
• Sensitivity to Basis Mismatch in Compressed Sensing
• Compressed Sensing Off the Grid
• Convergence of fixed-point continuation algorithms for matrix rank minimization
• MUSIC for single-snapshot spectral estimation: stability and super-resolution
• Robust Spectral Compressed Sensing via Structured Matrix Completion
• Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals
• Compressed sensing with coherent and redundant dictionaries
• Hard thresholding pursuit: an algorithm for compressive sensing
• Normalized iterative hard thresholding for matrix completion
• A fast symmetric SVD algorithm for square Hankel matrices
• Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
• CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
• Guarantees of Riemannian optimization for low rank matrix recovery

Cited In (25)

• Rank-deficient spectral factorization and wavelets completion problem
• Image restoration: structured low rank matrix framework for piecewise smooth functions and beyond
• A singular value thresholding with diagonal-update algorithm for low-rank matrix completion
• Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm
• Toeplitz matrix completion via a low-rank approximation algorithm
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• Seasonal signal extraction from GPS coordinate time series using low-rank matrix approximation based on nonconvex log-sum function minimization
• Fast Cadzow's algorithm and a gradient variant
• Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
• Matrix completion for matrices with low-rank displacement
• Improved harmonic incompatibility removal for susceptibility mapping via reduction of basis mismatch
• New low-rank optimization model and algorithms for spectral compressed sensing
• Nonnegative Low Rank Matrix Completion by Riemannian Optimalization Methods
• Multichannel frequency estimation with constant amplitude via convex structured low-rank approximation
• Restoration guarantee of image inpainting via low rank patch matrix completion
• Low-rank matrix completion in a general non-orthogonal basis
• A preconditioned Riemannian gradient descent algorithm for low-rank matrix recovery
• Recovery analysis of damped spectrally sparse signals and its relation to MUSIC
• Hankel Matrix Nuclear Norm Regularized Tensor Completion for $N$-dimensional Exponential Signals
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• A mathematical theory of the computational resolution limit in one dimension
• Title not available (Why is that?)
• Data Driven Tight Frame for Compressed Sensing MRI Reconstruction via Off-the-Grid Regularization
• A penalized method of alternating projections for weighted low-rank Hankel matrix optimization
• Exact matrix completion based on low rank Hankel structure in the Fourier domain

Uses Software

• PROPACK
• CVX

This page was built for publication: Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1990969)