Optimization Online


Atomic norm denoising with applications to line spectral estimation

Badri Bhaskar (bnbhaskar***at***wisc.edu)
Gongguo Tang (gtang5***at***wisc.edu)
Benjamin Recht (brecht***at***cs.wisc.edu)

Abstract: The sub-Nyquist estimation of line spectra is a classical problem in signal processing, but currently popular subspace-based techniques have few guarantees in the presence of noise and rely on a priori knowledge about system model order. Motivated by recent work on atomic norms in inverse problems, we propose a new approach to line spectral estimation that provides theoretical guarantees for the mean-squared-error performance in the presence of noise and without advance knowledge of the model order. We propose an abstract theory of denoising with atomic norms and specialize this theory to provide a convex optimization problem for estimating the frequencies and phases of a mixture of complex exponentials with guaranteed bounds on the mean-squared error. We show that the associated convex optimization problem, called ``Atomic norm Soft Thresholding'' (AST), can be solved in polynomial time via semidefinite programming. For very large scale problems we provide an alternative, efficient algorithm, called ``Discretized Atomic norm Soft Thresholding'' (DAST), based on the Fast Fourier Transform that achieves nearly the same error rate as that guaranteed by the semidefinite programming approach. We compare both AST and DAST with Cadzow's canonical alternating projection algorithm and demonstrate that AST outperforms DAST which outperforms Cadzow in terms of mean-square reconstruction error over a wide range of signal-to-noise ratios. For very large problems DAST is considerably faster than both AST and Cadzow.

Keywords: Line Spectral Estimation. Atomic Norms. Basis Pursuit.

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Applications -- Science and Engineering (Data-Mining )


Download: [PDF]

Entry Submitted: 04/02/2012
Entry Accepted: 04/02/2012
Entry Last Modified: 04/02/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society