Robust Spectral Compressed Sensing via Structured Matrix Completion

DOI10.1109/TIT.2014.2343623MaRDI QIDQ2986119zbMATH OpenOpenAlexFDO

Authors Yuxin Chen, Yuejie Chi

Publication date 16 May 2017

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

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

Mathematics Subject Classification ID

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

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.

Cited in

(33)

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

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)