A Tight Converse to the Spectral Resolution Limit via Convex Programming

Ferreira Da Costa, Maxime; Dai, Wei

doi:10.1109/ISIT.2018.8437490

A Tight Converse to the Spectral Resolution Limit via Convex Programming

Maxime Ferreira Da Costa and Wei Dai

IEEE International Symposium on Information Theory (ISIT 2018).

Finalist for the IEEE ISIT Jack Keil Wolf Award

arXiv IEEE

Abstract

It is now well understood that convex programming can be used to estimate the frequency components of a spectrally sparse signal from 2m+1 uniform temporal measurements. It is conjectured that a phase transition on the success of the total-variation regularization occurs when the distance between the spectral components of the signal to estimate crosses 1/m. We prove the necessity part of this conjecture by demonstrating that this regularization can fail whenever the spectral distance of the signal of interest is asymptotically equal to 1/m.

Cite

@inproceedings{FerreiraDaCosta2018Tight,
  author    = {Ferreira Da Costa, Maxime and Dai, Wei},
  title     = {A Tight Converse to the Spectral Resolution Limit via Convex Programming},
  booktitle = {2018 IEEE International Symposium on Information Theory (ISIT)},
  pages     = {901-905},
  year      = {2018},
  doi       = {10.1109/ISIT.2018.8437490}
}