Tessellated Distributed Computing of Non-Linearly Separable Functions

The work considers the $N$-server distributed computing scenario with $K$ users requesting functions that are arbitrary multi-variable polynomial evaluations of $L$ real (potentially non-linear) basis subfunctions of a certain degree. Our aim is to reduce both the computational cost at the servers, as well as the load of communication between the servers and the users. To do so, we take a novel approach, which involves transforming our distributed computing problem into a sparse tensor factorization problem $\bar{\mathcal{F}}= \bar{\mathcal{E}}\times_1 \mathbf {D}$, where tensor $\bar{\mathcal{F}}$ represents the requested non-linearly-decomposable jobs expressed as the mode-1 product between tensor $\bar{\mathcal{E}}$ and matrix $\mathbf{D}$, where $\mathbf{D}$ and $\bar{\mathcal{E}}$ respectively define the communication and computational assignment, and where their sparsity respectively allows for reduced communication and computational costs.We here design an achievable scheme, designing $\bar{\mathcal{E}},\mathbf{D}$ by utilizing novel fixed-support SVD-based tensor factorization methods that first split $\bar{\mathcal{F}}$ into properly sized and carefully positioned subtensors, and then decompose them into properly designed subtensors of $\bar{\mathcal{E}}$ and submatrices of $\mathbf{D}$. For the zero-error case and under basic dimensionality assumptions, this work reveals a lower bound on the optimal rate $K/N$ with a given communication and computational load.