Orthogonal matching pursuit-based algorithms for the Birkhoff-von Neumann decomposition

Birkhoff-von Neumann (BvN) decomposition writes a doubly stochastic matrix as a convex combination of permutation matrices. For a given doubly stochastic matrix, the decomposition in general is not unique. In many applications a sparsest decomposition, that is with the smallest number of permutation matrices is of interest. This problem is known to be NP-complete, and heuristics are used to obtain sparse solutions. We propose heuristics based on the well-known orthogonal matching pursuit for sparse BvN decomposition. We experimentally compare our heuristics with the state of the art from the literature and show how our methods advance the known heuristics.

Recommended citation: Damien Lesens, Jérémy E. Cohen, Bora Uçar. "Orthogonal matching pursuit-based algorithms for the Birkhoff-von Neumann decomposition ." EUSCIPCO 2024. 1(1).
Download Paper | Download Slides