The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems

2015/07/06 by Nicholas Boyd, Boyd, Nicholas, Geoffrey Schiebinger +4 · 7 citations
Engineering · Mathematics · #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC) #Photoacoustic and Ultrasonic Imaging #Sparse and Compressive Sensing Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.1507.01562

arxiv created 2015/07/06 · openalex publication_date 2015/07/06 · arxiv updated 2015/07/07 · openalex created_date 2022/10/04 · openalex updated_date 2026/07/28

Abstract

We propose a variant of the classical conditional gradient method for sparse inverse problems with differentiable measurement models. Such models arise in many practical problems including superresolution, time-series modeling, and matrix completion. Our algorithm combines nonconvex and convex optimization techniques: we propose global conditional gradient steps alternating with nonconvex local search exploiting the differentiable measurement model. This hybridization gives the theoretical global optimality guarantees and stopping conditions of convex optimization along with the performance and modeling flexibility associated with nonconvex optimization. Our experiments demonstrate that our technique achieves state-of-the-art results in several applications.

Citations

• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization

Cited by

• Convexifying Mean-Field Control: An Occupation-Measure and Frank-Wolfe Approach
• Hearing the Shape of a Cuboid Room Using Sparse Measure Recovery
• Lazifying point insertion algorithms in spaces of measures
• Frank-Wolfe algorithm for star-convex functions
• Frank-Wolfe Recursions for the Emergency Response Problem on Measure Spaces
• Effective regions and kernels in continuous sparse regularisation, with application to sketched mixtures
• Exact Dimensionality Reduction for Partial Line Spectra Estimation Problems

Related

• Sparse Inverse Problems Over Measures: Equivalence of the Conditional Gradient and Exchange Methods
• Model Function Based Conditional Gradient Method with Armijo-like Line Search
• Alternating minimization and alternating descent over nonconvex sets
• Hybrid Conditional Gradient - Smoothing Algorithms with Applications to Sparse and Low Rank Regularization
• First Order Methods beyond Convexity and Lipschitz Gradient Continuity with Applications to Quadratic Inverse Problems