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

DOI10.1016/J.ACHA.2017.04.004MaRDI QIDQ1990969zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

composite hard thresholding operatoriterative hard thresholdinglow 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)

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.

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

Cites work

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

Cited in

(28)

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

Describes a project that uses

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)