Multi-user linearly separable computation sparse factorization meets coding theory

In this work, we explore the problem of multi-user linearly separable computation, where N servers help compute the desired functions (jobs) of K users, and each desired function can be written as a linear combination of up to L (generally non-linear) subtasks (or sub-functions). Each server computes some of the subtasks, and communicates a linear combination of its computed outputs to a fraction of the

users, where then each user linearly combines its received data in order to recover its desired function. We explore the computation and communication relationship between how many subtasks each server computes vs. how much data each user receives.

For a matrix F representing the linear coefficients of the set of requested functions, our problem becomes equivalent to the open problem of matrix factorization F = DE over finite fields, where a sparse decoding matrix D and encoding matrix E imply reduced communication and computation costs respectively. This paper establishes a novel relationship between our problem, matrix factorization, syndrome decoding and covering codes. To reduce the computation cost, the above D is drawn from a here-introduced class of so-called partial-covering codes, whose study here yields the computation cost bounds that we present. To then reduce the communication cost, these coding-theoretic properties are explored in the regime of codes that have low-density parity check matrices. The work reveals — first for the commonly used one-shot scenario — that in the limit of large N, the optimal computation cost per server scales as a parameter γ = ρ ∈ (H−1  (logq(L) N ),H−1 q (K/N)) — where Hq is q-ary entropy

function — and that this can be achieved with communication cost that scales as O(

q logq(N)). This in turn reveals the role of the computational rate logq(L)/N, showing that this rate cannot exceed what one might call the computational capacity Hq(γ) of the system. We show that our coded approach yields unbounded gains over the uncoded scenario. In the end, we also explore the multi-shot scenario, for which we derive bounds on the computational cost.