  The multi-user linearly-separable distributed computing problem is considered
here, in which $N$ servers help to compute the real-valued functions requested
by $K$ users, where each function can be written as a linear combination of up
to $L$ (generally non-linear) subfunctions. Each server computes a fraction
$\gamma$ of the subfunctions, then communicates a function of its computed
outputs to some of the users, and then each user collects its received data to
recover its desired function. Our goal is to bound the ratio between the
computation workload done by all servers over the number of datasets. To this
end, we here reformulate the real-valued distributed computing problem into a
matrix factorization problem and then into a basic sparse recovery problem,
where sparsity implies computational savings. Building on this, we first give a
simple probabilistic scheme for subfunction assignment, which allows us to
upper bound the optimal normalized computation cost as $\gamma \leq
\frac{K}{N}$ that a generally intractable $\ell_0$-minimization would give. To
bypass the intractability of such optimal scheme, we show that if these optimal
schemes enjoy $\gamma \leq - r\frac{K}{N}W^{-1}_{-1}(- \frac{2K}{e N r} )$
(where $W_{-1}(\cdot)$ is the Lambert function and $r$ calibrates the
communication between servers and users), then they can actually be derived
using a tractable Basis Pursuit $\ell_1$-minimization. This newly-revealed
connection between distributed computation and compressed sensing opens up the
possibility of designing practical distributed computing algorithms by
employing tools and methods from compressed sensing.
