  Atomic norm minimization is of great interest in various applications of
sparse signal processing including super-resolution line-spectral estimation
and signal denoising. In prac-tice, atomic norm minimization (ANM) is
formulated as semi-definite programming (SDP) that is generally hard to solve.
This work introduces a low-complexity solver for a type of ANM known as atomic
norm soft thresholding (AST). The proposed method uses the framework of
coordinate descent and exploits the sparsity-inducing nature of atomic-norm
regularization. Specifically, this work first provides an equivalent,
non-convex formulation of AST. It is then proved that applying a coordinate
descent algorithm on the non-convex formulation leads to convergence to the
global solution. For the case of a single measurement vector of length N and
complex exponential basis, the complexity of each step in the coordinate
descent procedure is O(N log N ), rendering the method efficient for
large-scale problems. Through simulations, the proposed solver is shown to be
faster than alternating direction method of multiplier (ADMM) or customized
interior point SDP solver if the problems are sparse. It is demonstrated that
the coordinate descent solver can be modified for AST with multiple dimensions
and multiple measurement vectors as well as a variety of general basis.
