Flow Decomposition
Jonathan Ponniah, Liang‐Liang Xie · 2019
The framework of flow decomposition is proposed to unify regular encoding/decoding schemes in multisource multi-relay multi-cast channels; flows describe encoding schemes and layered partitions describe decoding schemes. Flow decomposition reveals a fundamental duality between compress-forward and decode-forward schemes with broader implications for combinatorial optimization over submodular functions. The main result proves that regular decoding schemes collectively achieve the regional cut-set extension of the one-relay decode-forward rate. The proof mimics interior-point methods in convex optimization. A shifting algorithm is used to construct a sequence of layered partitions that converges to a target rate-vector, where the number of shifts is linear in the network size. Flow decomposition inherits the benefits of regular decoding without the drawbacks of backward decoding: linear (as opposed to exponential) encoding delays and unrestricted (as opposed to strictly hierarchical) flow.