Forward - Backward Greedy Algorithms for Atomic Norm Regularization
  In many signal processing applications, the aim is to reconstruct a signal
that has a simple representation with respect to a certain basis or frame.
Fundamental elements of the basis known as "atoms" allow us to define "atomic
norms" that can be used to formulate convex regularizations for the
reconstruction problem. Efficient algorithms are available to solve these
formulations in certain special cases, but an approach that works well for
general atomic norms, both in terms of speed and reconstruction accuracy,
remains to be found. This paper describes an optimization algorithm called
CoGEnT that produces solutions with succinct atomic representations for
reconstruction problems, generally formulated with atomic-norm constraints.
CoGEnT combines a greedy selection scheme based on the conditional gradient
approach with a backward (or "truncation") step that exploits the quadratic
nature of the objective to reduce the basis size. We establish convergence
properties and validate the algorithm via extensive numerical experiments on a
suite of signal processing applications. Our algorithm and analysis also allow
for inexact forward steps and for occasional enhancements of the current
representation to be performed. CoGEnT can outperform the basic conditional
gradient method, and indeed many methods that are tailored to specific
applications, when the enhancement and truncation steps are defined
appropriately. We also introduce several novel applications that are enabled by
the atomic-norm framework, including tensor completion, moment problems in
signal processing, and graph deconvolution.
