Robust Spectral Compressed Sensing via Structured Matrix Completion

DOI10.1109/TIT.2014.2343623zbMATH Open1360.94064arXiv1304.8126OpenAlexW3106271742MaRDI QIDQ2986119FDOQ2986119

Authors: Yuxin Chen, Yuejie Chi 

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (33)

• Title not available (Why is that?)
• Spectral Compressed Sensing via Projected Gradient Descent
• Rank-deficient spectral factorization and wavelets completion problem
• Image restoration: structured low rank matrix framework for piecewise smooth functions and beyond
• Stable separation and super-resolution of mixture models
• A multi-stage convex relaxation approach to noisy structured low-rank matrix recovery
• Toeplitz matrix completion via smoothing augmented Lagrange multiplier algorithm
• A semi-smoothing augmented Lagrange multiplier algorithm for low-rank Toeplitz matrix completion
• Toeplitz matrix completion via a low-rank approximation algorithm
• Noisy matrix completion: understanding statistical guarantees for convex relaxation via nonconvex optimization
• High resolution 3D imaging in MIMO radar with sparse array
• Spectral compressive sensing
• An upper bound on the minimum rank of a symmetric Toeplitz matrix completion problem
• Fast Cadzow's algorithm and a gradient variant
• Robust recovery of complex exponential signals from random Gaussian projections via low rank Hankel matrix reconstruction
• A class of deterministic sensing matrices and their application in harmonic detection
• Matrix completion for matrices with low-rank displacement
• New low-rank optimization model and algorithms for spectral compressed sensing
• Off-the-grid recovery of piecewise constant images from few Fourier samples
• Multichannel frequency estimation with constant amplitude via convex structured low-rank approximation
• Low-rank matrix completion in a general non-orthogonal basis
• Nonconvex Low-Rank Tensor Completion from Noisy Data
• Bridging convex and nonconvex optimization in robust PCA: noise, outliers and missing data
• Structured Gradient Descent for Fast Robust Low-Rank Hankel Matrix Completion
• Compressed sensing, sparse inversion, and model mismatch
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution Under Random Designs
• Regular and limiting normal cones to the graph of the subdifferential mapping of the nuclear norm
• On the Compressive Spectral Method
• 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
• Median-truncated gradient descent: a robust and scalable nonconvex approach for signal estimation
• Exact matrix completion based on low rank Hankel structure in the Fourier domain
• Fast and provable algorithms for spectrally sparse signal reconstruction via low-rank Hankel matrix completion

This page was built for publication: Robust Spectral Compressed Sensing via Structured Matrix Completion

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