A Multicore Convex Optimization Algorithm with Applications to Video Restoration

Feriel Abboud, Emilie Chouzenoux, Jean-Christophe Pesquet, Hugues Talbot

TL;DR

This paper introduces a novel distributed algorithm for solving complex optimization problems that arise in areas like video restoration. By leveraging multicore processors and a hypergraph-based communication strategy, the algorithm achieves significant speedups while maintaining high-quality results, making it well-suited for handling large-scale image and video processing tasks.

What Problem Does This Paper Address?

Many modern image and video processing tasks, such as video restoration, can be framed as complex optimization problems. These problems often involve minimizing a sum of convex functions, some of which may not be "smooth" (i.e., they have sharp corners or kinks). Furthermore, the datasets involved are frequently massive, making traditional, single-processor approaches computationally infeasible. The challenge lies in developing efficient, parallelizable algorithms that can tackle these high-dimensional, non-smooth optimization problems on modern multicore architectures, while also managing communication overhead between processing units.

Methods

The core of this paper is a new asynchronous dual forward-backward (DBFB) scheme designed for multicore architectures. This algorithm builds upon existing primal-dual splitting methods, which are known for their effectiveness in solving such optimization problems. The novelty lies in its distributed and asynchronous nature, allowing different parts of the optimization problem to be handled by different processing cores concurrently.

Key aspects of their method include:

  • Hypergraph Formulation: The problem is structured using a hypergraph, where each function term in the optimization problem is assigned to a "node." Communication is then restricted to "neighboring" nodes that share a common "hyperedge," mimicking how data might be distributed across cores.
  • Distributed Asynchronous Updates: Unlike traditional synchronous algorithms where all processors must wait for each other, this approach allows cores to update their local computations independently. This reduces idle time and improves overall efficiency.
  • Exploiting Sparse Operators: The algorithm is designed to take advantage of the fact that many operators in image processing (like those used for gradients) are "sparse," meaning they only affect a small portion of the data. This reduces the memory and computational burden on each core.
  • Primal-Dual Splitting: This is a well-established technique that breaks down complex optimization problems into simpler sub-problems that can be solved iteratively. The paper leverages this to handle non-smooth functions and linear operators without requiring computationally expensive matrix inversions.

Datasets

The paper evaluates its proposed algorithm on two standard test video sequences:

  • Foreman: A video sequence with 72 frames, each of size 348x284 pixels.
  • Irene: A video sequence with 72 frames, each of size 352x288 pixels.

These sequences are used to demonstrate the algorithm's performance in a realistic video denoising scenario. No new datasets are introduced.

Key Insights and Ideas

  • Hypergraphs for Efficient Communication: The use of a hypergraph structure is a clever way to model the dependencies between different parts of the optimization problem and to define a communication topology that aligns well with multicore architectures. This allows for more targeted and efficient data exchange between processing units.
  • Asynchronicity is Key for Speedup: By allowing cores to work independently and communicate only when necessary, the algorithm avoids the bottlenecks often associated with synchronous parallel processing, leading to significant performance gains.
  • Exploiting Sparsity Pays Off: The algorithm's ability to leverage the sparse nature of image processing operators is crucial for its scalability. It means that each core doesn't need to process the entire dataset, but rather a localized portion, which is much more manageable.
  • Strong Convexity Enables Guarantees: The assumption of strong convexity in the optimization problem is important because it guarantees that the algorithm will converge to a unique, optimal solution.

Key Results

The paper demonstrates the effectiveness of their algorithm through simulations on video denoising:

  • Significant Speedup: Figure 2 shows a substantial speedup in execution time as the number of cores increases. For the Foreman and Irene sequences, the speedup is initially close to linear, especially up to 12 cores. While it saturates beyond that (as predicted by Amdahl's Law), the gains are still considerable.
  • High-Quality Restoration: Figure 3 presents examples of degraded and restored video frames. The restored images exhibit good visual quality, with the denoising algorithm achieving SNRs of 32.04 dB for Foreman and 30.97 dB for Irene.
  • Reduced Memory Footprint: By exploiting the sparse structure of operators, the algorithm reduces the local memory requirements for each processing unit, making it feasible for large-scale problems.

Limitations and Future Work

  • Saturation of Speedup: The authors acknowledge that the speedup begins to saturate after a certain number of cores (around 12 in their experiments). This is attributed to the increasing dominance of inter-CPU communication overhead compared to inter-core communication, a phenomenon described by Amdahl's Law.
  • Future Work: The authors suggest that evaluating their proposed optimization strategy on more distributed parallel computing systems would be an interesting avenue for future research. This could involve exploring different communication patterns or hardware architectures.

Summary updated

Abstract

In this paper, we present a new distributed algorithm for minimizing a sum of non-necessarily differentiable convex functions composed with arbitrary linear operators. The overall cost function is assumed strongly convex. Each involved function is associated with a node of a hypergraph having the ability to communicate with neighboring nodes sharing the same hyperedge. Our algorithm relies on a primal-dual splitting strategy with established convergence guarantees. We show how it can be efficiently implemented to take full advantage of a multicore architecture. The good numerical performance of the proposed approach is illustrated in a problem of video sequence denoising, where a significant speedup is achieved.
BibTeX
@inproceedings{abboud2018multicore,
  author = {Feriel Abboud and Emilie Chouzenoux and Jean-Christophe Pesquet and Hugues Talbot},
  title = {{A Multicore Convex Optimization Algorithm with Applications to Video Restoration}},
  booktitle = {ICIP},
  year = {2018},
  doi = {10.1109/icip.2018.8451798},
}
Figure