Forward - Backward Greedy Algorithms for Atomic Norm Regularization

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.

To appear in IEEE Transactions on Signal Processing

References in corpus (10)

• Consistency of the group Lasso and multiple kernel learning
• Square Deal: Lower Bounds and Improved Relaxations for Tensor Recovery
• Block-Coordinate Frank-Wolfe Optimization for Structural SVMs
• Statistical estimation and testing via the sorted L1 norm
• Orthogonal Matching Pursuit with Replacement
• Convexity in source separation: Models, geometry, and algorithms
• Forward-Backward Greedy Algorithms for General Convex Smooth Functions over A Cardinality Constraint
• Sparse Overlapping Sets Lasso for Multitask Learning and its Application to fMRI Analysis
• Convex relaxations of structured matrix factorizations
• Solving OSCAR regularization problems by proximal splitting algorithms

Cited by in corpus (23)

• Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution
• Quantized Spectral Compressed Sensing: Cramer-Rao Bounds and Recovery Algorithms
• Mathematical Theory of Atomic Norm Denoising In Blind Two-Dimensional Super-Resolution (Extended Version)
• Approximate Support Recovery of Atomic Line Spectral Estimation: A Tale of Resolution and Precision
• Sparsity Constrained Minimization via Mathematical Programming with Equilibrium Constraints
• High-dimensional Time Series Prediction with Missing Values
• Blended Conditional Gradients: the unconditioning of conditional gradients
• On Asymptotic Linear Convergence Rate of Iterative Hard Thresholding for Matrix Completion
• Linearly-Convergent FISTA Variant for Composite Optimization with Duality
• Towards Off-the-grid Algorithms for Total Variation Regularized Inverse Problems
• On Approximation Guarantees for Greedy Low Rank Optimization
• The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems
• Polar Alignment and Atomic Decomposition
• Low-Rank Matrix Recovery from Noise via an MDL Framework-based Atomic Norm
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families
• On Learning High Dimensional Structured Single Index Models
• Stochastic In-Face Frank-Wolfe Methods for Non-Convex Optimization and Sparse Neural Network Training
• Generalized conditional subgradient and generalized mirror descent: duality, convergence, and symmetry
• Accelerated Nonnegative Tensor Completion via Integer Programming
• Nonnegative Tensor Completion via Integer Optimization
• Sparse Optimization on General Atomic Sets: Greedy and Forward-Backward Algorithms
• Robust Structured Statistical Estimation via Conditional Gradient Type Methods
• Efficient atom selection strategy for iterative sparse approximations