Title: A Fast Interior Point Method for Atomic Norm Soft Thresholding,
Abstract: The atomic norm provides a generalization of the $\ell_1$-norm to continuous
parameter spaces. When applied as a sparse regularizer for line spectral
estimation the solution can be obtained by solving a convex optimization
problem. This problem is known as atomic norm soft thresholding (AST). It can
be cast as a semidefinite program and solved by standard methods. In the
semidefinite formulation there are $O(N^2)$ dual variables and a standard
primal-dual interior point method requires at least $O(N^6)$ flops per
iteration. That has lead researcher to consider alternating direction method of
multipliers (ADMM) for the solution of AST, but this method is still somewhat
slow for large problem sizes. To obtain a faster algorithm we reformulate AST
as a non-symmetric conic program. That has two properties of key importance to
its numerical solution: the conic formulation has only $O(N)$ dual variables
and the Toeplitz structure inherent to AST is preserved. Based on it we derive
FastAST which is a primal-dual interior point method for solving AST. Two
variants are considered with the fastest one requiring only $O(N^2)$ flops per
iteration. Extensive numerical experiments demonstrate that FastAST solves AST
significantly faster than a state-of-the-art solver based on ADMM.