Robust Spectral Compressed Sensing via Structured Matrix Completion

Abstract

The paper explores the problem of \emph{spectral compressed sensing}, which aims to recover a spectrally sparse signal from a small random subset of its $n$ time domain samples. The signal of interest is assumed to be a superposition of $r$ multi-dimensional complex sinusoids, while the underlying frequencies can assume any \emph{continuous} values in the normalized frequency domain. Conventional compressed sensing paradigms suffer from the basis mismatch issue when imposing a discrete dictionary on the Fourier representation. To address this issue, we develop a novel algorithm, called \emph{Enhanced Matrix Completion (EMaC)}, based on structured matrix completion that does not require prior knowledge of the model order. The algorithm starts by arranging the data into a low-rank enhanced form exhibiting multi-fold Hankel structure, and then attempts recovery via nuclear norm minimization. Under mild incoherence conditions, EMaC allows perfect recovery as soon as the number of samples exceeds the order of $r{\log }^{4}n$, and is stable against bounded noise. Even if a constant portion of samples are corrupted with arbitrary magnitude, EMaC still allows exact recovery, provided that the sample complexity exceeds the order of $r^2{\log }^{3}n$. Along the way, our results demonstrate the power of convex relaxation in completing a low-rank multi-fold Hankel or Toeplitz matrix from minimal observed entries. The performance of our algorithm and its applicability to super resolution are further validated by numerical experiments.

accepted to IEEE Transactions on Information Theory

Cited by in corpus (29)

• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• On Gridless Sparse Methods for Line Spectral Estimation From Complete and Incomplete Data
• Incoherence-Optimal Matrix Completion
• Gridless DOA Estimation and Root-MUSIC for Non-Uniform Arrays
• Adaptive Interference Removal for Un-coordinated Radar/Communication Co-existence
• Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution
• Variational Bayesian Inference of Line Spectra
• Hankel Matrix Nuclear Norm Regularized Tensor Completion for $N$-dimensional Exponential Signals
• Three more Decades in Array Signal Processing Research: An Optimization and Structure Exploitation Perspective
• Radial Velocity Data Analysis with Compressed Sensing Techniques
• Vandermonde Factorization of Hankel Matrix for Complex Exponential Signal Recovery -- Application in Fast NMR Spectroscopy
• MUSIC for multidimensional spectral estimation: stability and super-resolution
• Compressive Parameter Estimation for Sparse Translation-Invariant Signals Using Polar Interpolation
• Quantized Spectral Compressed Sensing: Cramer-Rao Bounds and Recovery Algorithms
• Accelerated Structured Alternating Projections for Robust Spectrally Sparse Signal Recovery
• Convex recovery of continuous domain piecewise constant images from non-uniform Fourier samples
• Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing
• Spectrally Sparse Signal Recovery via Hankel Matrix Completion with Prior Information
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• Two-Dimensional Super-Resolution via Convex Relaxation
• Multidimensional Variational Line Spectra Estimation
• Projected Gradient Descent for Spectral Compressed Sensing via Symmetric Hankel Factorization
• Compressed Super-Resolution of Positive Sources
• High-dimensional Fast Convolutional Framework (HICU) for Calibrationless MRI
• Robustness of Two-Dimensional Line Spectral Estimation Against Spiky Noise
• Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent
• Performance of Compressive Parameter Estimation via K-Median Clustering
• On the Robustness of Cross-Concentrated Sampling for Matrix Completion
• Low-Rank Toeplitz Matrix Restoration: Descent Cone Analysis and Structured Random Matrix