Forward–Backward Greedy Algorithms for Atomic Norm Regularization

DOI10.1109/TSP.2015.2461515zbMATH Open1394.94471arXiv1404.5692OpenAlexW1613006380MaRDI QIDQ4580894FDOQ4580894

Nikhil Rao, Parikshit Shah, Stephen J. Wright

Publication date: 22 August 2018

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1404.5692

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (7)

• Towards off-the-grid algorithms for total variation regularized inverse problems
• Cut Pursuit: Fast Algorithms to Learn Piecewise Constant Functions on General Weighted Graphs
• The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
• Approximate support recovery of atomic line spectral estimation: a tale of resolution and precision
• An Extended Frank--Wolfe Method with “In-Face” Directions, and Its Application to Low-Rank Matrix Completion
• Screening for a reweighted penalized conditional gradient method
• Enhancing Sparsity and Resolution via Reweighted Atomic Norm Minimization

This page was built for publication: Forward–Backward Greedy Algorithms for Atomic Norm Regularization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580894)