The work considers the $N$-server distributed computing scenario with $K$ users requesting functions that are linearly-decomposable over an arbitrary basis of $L$ real (potentially non-linear) subfunctions. In our problem, the aim is for each user to receive their function outputs, allowing for reduced reconstruction error (distortion) $\epsilon$, reduced computing cost ($\gamma$; the fraction of subfunctions each server must compute), and reduced communication cost ($\delta$; the fraction of users each server must connect to). For any given set of $K$ requested functions -- which is here represented by a coefficient matrix $\mathbf { F} \in \mathbb{ R}^{ K \times L}$ -- our problem is made equivalent to the open problem of sparse matrix factorization that seeks -- for a given parameter $T$, representing the number of shots for each server -- to minimize the reconstruction distortion $\frac{ 1}{ KL}\|\mathbf { F} - \mathbf{ D}\mathbf{ E}\|^2_{ F}$ overall $\delta$-sparse and $\gamma$-sparse matrices $\mathbf{ D}\in \mathbb{ R}^{ K \times NT}$ and $\mathbf{ E} \in \mathbb{ R}^{ NT \times L}$. With these matrices respectively defining which servers compute each subfunction, and which users connect to each server, we here design our $\mathbf{ D},\mathbf{ E}$ by designing tessellated-based and SVD-based fixed support matrix factorization methods that first split $\mathbf{ F}$ into properly sized and carefully positioned submatrices, which we then approximate and then decompose into properly designed submatrices of $\mathbf{ D}$ and $\mathbf{ E}$.
Categories: cs.IT math.IT