PaperlayerView exact revision on arXiv

Source-linked AI summary

The Alternating Descent Conditional Gradient Method for Sparse Inverse Problems

Nicholas Boyd, Geoffrey Schiebinger, Benjamin Recht

arXiv:1507.01562v1math.OC

TL;DR

Sparse inverse problems require recovering a few parameterized sources from noisy measurements, while common finite-dimensional formulations ignore differentiable structure and can have practical limitations. The paper introduces ADCG, alternating global conditional-gradient steps with nonconvex local search, and reports state-of-the-art performance across several applications. The method combines local convergence behavior with stability and global convergence guarantees.

  • Problem

    Sparse inverse problems must recover a small collection of source parameters and weights from noisy measurements, but common formulations ignore natural differentiable structure in the source space.

  • Method

    ADCG augments the conditional gradient method with an aggressive nonconvex local-search step that exploits differentiable measurement models while operating over finitely supported measures.

  • Results

    ADCG achieves state-of-the-art performance in superresolution fluorescence microscopy, matrix completion, and system identification, and local descent improves performance over standard conditional gradient in all investigated applications.

  • Takeaways & Limitations

    The hybrid framework provides a globally convergent approach that improves practical performance without heuristic post-processing steps.

  • Takeaways & Limitations

    The experiments use naive implementations and omit detailed timing information, while CGM-M can converge slowly and produce undesirably large supports.

Abstract

from arXiv · show

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.

1 Introduction

The paper formulates sparse inverse problems over measures and introduces ADCG, which combines global conditional-gradient steps with differentiability-aware local search. This approach addresses limitations of gridding and other finite-dimensional formulations while retaining convex-optimization guarantees.

  • Problem formulation: Sparse inverse problems recover a few parameterized sources and weights from noisy measurements.Sources can be represented as atomic measures, potentially yielding infinite-dimensional optimization when the parameter space is continuous.
  • Limitations of existing approaches: Grid-based, moment, and atomic-norm formulations respectively face scalability, noise, applicability, or parameter-recovery limitations.Gridding can introduce artifacts requiring heuristic post-processing, while moment methods may be expensive and noise-sensitive.
  • Proposed method: ADCG augments conditional gradient with nonconvex local search that exploits differential structure in the parameter space.The algorithm is designed to produce approximate solutions with bounded support while operating on the original measure space.
  • Mathematical setup: The paper models additive weighted sources through a linear forward operator over measures and minimizes a convex residual loss under a bounded-support or total-mass formulation.The measurement model is determined by a differentiable single-source function ψ and supports nonnegative atomic measures.
  • Connections: The framework connects measure optimization with atomic-norm formulations and includes the nonnegative lasso as a finite-parameter special case.When the parameter space is finite and the loss is squared error, the formulation reduces to a nonnegative lasso problem.

2 Example applications

The paper applies its sparse inverse framework to diverse applications including superresolution, matrix completion, system identification, experimental design, mixture recovery, quadrature, neural spike identification, and radiation therapy. These examples use differentiable measurement models to express source selection, parameter recovery, or sparse design as measure-based optimization problems.

  • Superresolution imaging: Superresolution represents point sources through locations, intensities, and a pixelated point-spread function.The formulation can localize sources below the diffraction limit, and the paper reports state-of-the-art performance on a fluorescence microscopy challenge dataset.
  • Linear system identification: System identification learns unknown linear time-invariant system parameters from input-output sequences by modeling each source as a small differentiable LTI system.The paper states that ADCG matches the state of the art on two standard system-identification datasets.
  • Matrix completion: Matrix completion estimates a large matrix from observed entries using a low-rank, nuclear-norm-inspired sparse inverse formulation.The paper reports state-of-the-art results on the Netflix Challenge benchmark.
  • Bayesian experimental design: Bayesian experimental design selects measurement parameters to reduce posterior uncertainty, which can be expressed as sparse measure optimization with bounded total mass.Under Gaussian assumptions, posterior entropy is related to the volume of an uncertainty ellipsoid.
  • Other applications: Additional applications formulate mixture recovery, numerical quadrature, neural spike identification, and radiation-treatment planning as sparse source-selection or parameter-recovery problems.Radiation therapy favors plans with few beams because repositioning increases procedure cost and motion risk.

3 Conditional gradient method

The paper translates conditional gradient optimization to sparse inverse problems over measures, then augments it with differentiable local support search. ADCG alternates convex global steps with nonconvex descent while retaining CGM bounds and bounded-support guarantees.

  • Classical conditional gradient method: CGM iteratively minimizes a linearization of a differentiable convex objective over a closed, bounded, convex feasible set.The linearized minimization provides a restricted steepest-descent direction, followed by a feasible update.
  • CGM for sparse inverse problems: The fully corrective CGM updates weights over the accumulated support, while the measure formulation represents sparse sources as finite atomic measures.At each iteration, the algorithm selects a source, tunes weights through finite-dimensional convex optimization, and prunes the support.
  • CGM for sparse inverse problems: For measure-valued CGM, the linearized subproblem adds a single point mass τδθ⋆, and iterates can be represented with support on at most d + 1 points.The point θ⋆ minimizes the scalar function F(θ), unless F is positive everywhere, in which case the zero measure is optimal.
  • Alternating descent conditional gradient method: CGM-M performs poorly when closely separated sources require smooth support movement, whereas ADCG is designed to speed convergence and find significantly sparser solutions.CGM-M must repeatedly add and remove support points because it cannot smoothly move them within the parameter space.
  • Alternating descent conditional gradient method: ADCG allows the support to move continuously within Θ and uses differentiability of ψ to locally improve support at each iteration.Its local descent operates on source parameters with weights held fixed, within a finite-dimensional nonconvex problem.
  • Alternating descent conditional gradient method: ADCG alternates descent on the convex infinite-dimensional problem with block coordinate descent on the finite-dimensional nonconvex problem.The standard conditional-gradient bound remains valid as a termination condition, and the local search does not change CGM convergence guarantees.

4 Related work

Prior work uses conditional-gradient variants, gridding, moments, and non-gridded methods for infinite-dimensional inverse problems, but each has stated scope or computational limitations. ADCG extends related rank-one and local-optimization ideas to a more general setting.

  • Conditional gradient methods are simpler to implement than projected or proximal gradient methods because they solve linear rather than quadratic subproblems over the constraint set.
  • ADCG generalizes combinations of rank-one updates and local nonconvex optimization beyond matrix completion and nuclear-norm problems.
  • Gridding approximately solves the infinite-dimensional problem but becomes intractable for even moderately high-dimensional parameter spaces and often requires heuristic post-processing.
  • Non-gridded gradient-flow methods update support and locations but do not solve the finite-dimensional convex problem at every iteration, leaving bounded-memory guarantees unavailable.

5 Theoretical guarantees

The theoretical analysis establishes bounded memory and convergence for ADCG by relating its measure iterates to a finite-dimensional conditional-gradient problem. The guarantees include sparse supports and an accuracy-dependent iteration bound under approximate linear minimization.

  • 5.1 Bounded memory: ADCG has iterates whose support cardinality is uniformly bounded by d + 1, enabling bounded-memory implementation.The bound follows from the fully-corrective step and an optimal finite-dimensional solution with at most d + 1 nonzeros.
  • 5.1 Bounded memory: The finite-dimensional weight problem has an optimal solution with at most d + 1 nonzeros.The argument invokes Carathéodory’s theorem to represent a point in the convex hull using at most d + 1 points.
  • 5.2 Convergence analysis: The measure formulation and its finite-dimensional counterpart have equivalent feasible representations and preserve the objective value.
  • 5.2 Convergence analysis: ℓ(Φµk − y) − ℓ⋆ ≤ 2C / k + 2(1 + ζ), when each linear minimization subproblem is solved to precision Cζ.The convergence theorem applies even when the linear minimization step is approximate.
  • 5.2 Convergence analysis: ADCG’s linearization step coincides with the standard conditional-gradient linear minimization step on the equivalent finite-dimensional problem.The equivalence follows from representing the convex hull through feasible measures and selecting the corresponding atom.
  • 5.2 Convergence analysis: The nonconvex coordinate-descent update is valid because it performs at least as well as the fully-corrective step.

6 Numerical results

The numerical study applies ADCG to three signal-processing examples and compares it with prior methods and related conditional-gradient or gradient-flow algorithms. The implementations emphasize practical accessibility rather than detailed runtime reporting.

  • ADCG is evaluated on superresolution fluorescence microscopy, matrix completion, and system identification.A simple implementation is publicly available on GitHub.
  • The experiments compare ADCG with prior art, standard fully-corrective conditional gradient methods for measures, and a gradient-flow variant.The gradient-flow comparison fully solves the convex problem at each step.
  • The three experiments solve the finite-dimensional convex weight problem using a primal-dual interior-point method.
  • Parameter τ is selected by inspection, using validation data for matrix completion and system identification and image-specific choices for single-molecule imaging.For single-molecule imaging, a large τ is combined with stopping based on the objective decrease from adding a source.
  • The experiments use naive implementations on a standard c4.8xlarge EC2 instance and omit detailed timing information.The stated purpose is to demonstrate ease of implementation and high-quality solutions.

6.1 Superresolution fluorescence microscopy

In fluorescence microscopy, ADCG is evaluated for recovering fluorescent-protein locations and compared with gridding and microscopy-specific baselines. It matches gridding, outperforms quickPALM and CoG, and analyzes all images in under an hour.

  • The task is to recover 2D positions of fluorescent proteins from optical-microscope images.
  • The comparison includes ADCG, gridding, quickPALM, center of Gaussians, CGM, and gradient flow.The gridding baseline discretizes candidate source locations and solves an ℓ1-regularized regression.
  • The gridding method requires heuristic center-of-mass post-processing to remove clustered false positives, and this post-processing performs poorly at high fluorophore density.
  • F1 score at varying radii measures localization accuracy through precision and recall after matching estimated and true point sources.
  • The dataset contains 12000 images with 81049 point sources, covering simulated microtubules.Figure 2 displays a typical image and the recovered locations across the image sequence.
  • ADCG matches gridding performance, significantly beats quickPALM and CoG, and analyzes all images in well under an hour.The gridding approach is reported as significantly slower and dependent on post-processing.

6.2 Matrix completion

ADCG is evaluated on Netflix matrix completion and matches nuclear-norm state-of-the-art performance while outperforming other conditional-gradient variants. Its best RMSE requires over seven hours in the reported implementation.

  • Results: ADCG matches the state of the art for nuclear norm based approaches on the Netflix Prize dataset.The task predicts ratings for 480,189 users across 17,770 movies from observed entries.
  • Results: ADCG outperforms all other CGM variants on Netflix probe-set RMSE.Figure 4 reports RMSE comparisons among ADCG and other conditional-gradient variants.
  • Runtime: The reported implementation takes over 7 hours to achieve its best RMSE.The authors note that more sophisticated implementation or parallelization could improve this runtime.

6.3 System identification

ADCG is applied to flexible-robot-arm and hairdryer system-identification datasets using partial trajectories for training and forward prediction for evaluation. It matches the reference method while exceeding other CGM variants, but runs substantially slower than spectral methods.

  • Datasets and evaluation: The experiments use flexible robot arm and hairdryer datasets, each containing 1000 samples.The first 300 time points identify each system; remaining points evaluate forward predictions against ground truth.
  • Runtime: ADCG’s simple implementation takes about an hour, compared with under a minute for the spectral methods in [19].The reported comparison concerns runtime on these system-identification experiments.

7 Conclusions and future work

The paper concludes that ADCG delivers state-of-the-art performance across three applications without heuristic post-processing, combining global conditional-gradient control with nonconvex local search. Future work targets sharper convergence theory, connections to clustering and cutting-plane methods, and broader applications.

  • Conclusions: ADCG achieves state-of-the-art performance in fluorescence microscopy, matrix completion, and system identification without heuristic post-processing.The conclusion attributes practical gains to coupling conditional-gradient optimization with nonconvex local search under global convergence control.
  • Conclusions: Adding nonconvex local descent significantly improves performance over standard conditional gradient in all investigated applications.The framework is presented as a way to control local search while retaining global convergence guarantees.
  • Future work: Future work should investigate whether ADCG’s convergence bounds can be tightened to better predict its practical performance.The current bounds are shared with ordinary and fully corrective conditional-gradient variants despite observed performance differences.
  • Future work: The authors identify possible connections between ADCG and k-means, cutting-plane methods, and semi-infinite programming.These connections may motivate new variants or analyses of conditional-gradient methods.
  • Future work: The authors believe ADCG may apply broadly to other sparse inverse problems and provide public code to facilitate new applications.They describe new implementations as requiring two user-specified subroutines, though the cited passage is truncated.
Loading 1507.01562v1…