The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems

DOI10.1137/15M1035793zbMath1365.90195arXiv1507.01562OpenAlexW2605512869MaRDI QIDQ5737722

Nicholas Boyd, Benjamin Recht, Geoffrey Schiebinger

Publication date: 30 May 2017

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

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

zbMATH Keywords

measuresconvex optimizationinverse problemssemi-infinite programmingsparsityconditional gradient methodcompressed sensing

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25) Applications of mathematical programming (90C90) Nonlinear programming (90C30) Numerical methods based on nonlinear programming (49M37) Semi-infinite programming (90C34) Methods of reduced gradient type (90C52) Extreme-point and pivoting methods (90C49)

Related Items

On the Frank–Wolfe algorithm for non-compact constrained optimization problems, Safe Rules for the Identification of Zeros in the Solutions of the SLOPE Problem, Towards off-the-grid algorithms for total variation regularized inverse problems, On the uniqueness of solutions for the basis pursuit in the continuum, Degrees of freedom for off-the-grid sparse estimation, Sparse optimization on measures with over-parameterized gradient descent, Generalized notions of sparsity and restricted isometry property. II: Applications, Nonconvex regularization for sparse neural networks, Stable super-resolution limit and smallest singular value of restricted Fourier matrices, An off-the-grid approach to multi-compartment magnetic resonance fingerprinting, ``FISTA in Banach spaces with adaptive discretisations, A generalized conditional gradient method for dynamic inverse problems with optimal transport regularization, Convergence rates of gradient methods for convex optimization in the space of measures, Short paper -- A note on the Frank-Wolfe algorithm for a class of nonconvex and nonsmooth optimization problems, Dynamical programming for off-the-grid dynamic inverse problems, Dimension reduction, exact recovery, and error estimates for sparse reconstruction in phase space, Asymptotic linear convergence of fully-corrective generalized conditional gradient methods, Dynamic Spike Superresolution and Applications to Ultrafast Ultrasound Imaging, The geometry of off-the-grid compressed sensing, An Epigraphical Approach to the Representer Theorem, A fast homotopy algorithm for gridless sparse recovery, Towards off-the-grid algorithms for total variation regularized inverse problems, On the linear convergence rates of exchange and continuous methods for total variation minimization, MultiDimensional Sparse Super-Resolution, Unnamed Item, Super-resolution by means of Beurling minimal extrapolation, Conditional gradient method for multiobjective optimization, Multi-kernel unmixing and super-resolution using the modified matrix pencil method, The sliding Frank–Wolfe algorithm and its application to super-resolution microscopy, Super-resolution of positive sources on an arbitrarily fine grid, Sparse Inverse Problems over Measures: Equivalence of the Conditional Gradient and Exchange Methods, A Convex Approach to Superresolution and Regularization of Lines in Images, Super-resolution for doubly-dispersive channel estimation, Sparsest piecewise-linear regression of one-dimensional data, Inverse point source location with the Helmholtz equation on a bounded domain, Linear convergence of accelerated conditional gradient algorithms in spaces of measures, A sparse control approach to optimal sensor placement in PDE-constrained parameter estimation problems, TV-based spline reconstruction with Fourier measurements: uniqueness and convergence of grid-based methods, On the extremal points of the ball of the Benamou–Brenier energy

Uses Software

• SDPLR
• SPGL1
• Jellyfish
• k-means++

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Techniques for exploring the suboptimal set
• Conditional gradient algorithms for norm-regularized smooth convex optimization
• Random sampling of sparse trigonometric polynomials
• Conditional gradient algorithms with open loop step size rules
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• The convex geometry of linear inverse problems
• Spectral compressive sensing
• Parallel stochastic gradient algorithms for large-scale matrix completion
• Exact matrix completion via convex optimization
• Compressed Remote Sensing of Sparse Objects
• Semi-Infinite Programming: Theory, Methods, and Applications
• Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization
• Sparse Optimization with Least-Squares Constraints
• Semi-infinite programming, duality, discretization and optimality conditions†
• High-Resolution Radar via Compressed Sensing
• Recovery of Sparse Translation-Invariant Signals With Continuous Basis Pursuit
• Forward–Backward Greedy Algorithms for Atomic Norm Regularization
• Inverse problems in spaces of measures
• Optimal Design of Experiments
• Compressed Sensing Off the Grid
• A sparse signal reconstruction perspective for source localization with sensor arrays
• The effectiveness of lloyd-type methods for the k-means problem
• Towards a Mathematical Theory of Super‐resolution
• Low-rank matrix completion using alternating minimization
• Convex Analysis