EE4540 Distributed signal processing

In the course Distributed Signal Processing, attention will be paid to decentralised signal processing techniques. Due to the explosion in size and complexity of modern datasets, it is increasingly important to be able to solve problems with a very large number of features or training examples. In industry, this trend has been referred to as ‘Big Data’, and it has had a significant impact in areas as varied as machine learning, internet applications, computational biology, medicine, finance, marketing, journalism, network analysis, weather forecast, telecommunication, and logistics. As a result, both the decentralised collection or storage of these datasets as well as accompanying distributed solution methods are either necessary or at least highly desirable.

Many problems of interest in the above mentioned areas can be posed in the framework of convex optimisation. Even in cases where the cost function is non-convex, for example in algorithms that operate in high-dimensional spaces or that train non-linear models such as tensor models and deep neural networks, convex optimisation is used to solve (convex) relaxed optimisation problems, as non-convex problems are often NP-hard to solve.

Algorithms for distributed signal processing can, in many cases, be analysed in a unified manner using the abstraction of monotone operators and fixed-point theory. We, therefore, will focus on these topics in more detail during the course and use this to solve certain problems in a distributed way. We will analyse the algorithms not only in terms of convergence rate, but will consider the sensitivity to transmission failures and privacy-related issues as well.

We will consider the following topics:

1. Distributed consensus algorithms
   • Synchronous/asynchronous averaging
   • Randomized gossip
   • Geographic gossip
   • Gossip with eavesdropping
   • Sum-weight averaging
2. Distributed optimisation
   • Jacobi and Gauss-Seidel algorithm
   • (Sub)gradient descent
   • Dual ascent, dual decomposition
   • Method of multipliers
   • Alternating direction method of multipliers (ADMM)
   • Primal-dual method of multipliers (PDMM)
3. Monotone operator theory
   • Monotone operators
   • Fixed-point iterations
   • Forward-backward splitting
   • Peaceman-Rachford splitting
   • Douglas-Rachford splitting
4. Privacy and security
   • Differential privacy
   • Secure multi-party computation
   • Subspace perturbation

Teachers

Last modified: 2024-10-02