  Consider the problem of source coding in networks with multiple receiving
terminals, each having access to some kind of side information. In this case,
standard coding techniques are either prohibitively complex to decode, or
require network-source coding separation, resulting in sub-optimal transmission
rates. To alleviate this problem, we offer a joint network-source coding scheme
based on matrix sparsification at the code design phase, which allows the
terminals to use an efficient decoding procedure (syndrome decoding using
LDPC), despite the network coding throughout the network. Via a novel relation
between matrix sparsification and rate-distortion theory, we give lower and
upper bounds on the best achievable sparsification performance. These bounds
allow us to analyze our scheme, and, in particular, show that in the limit
where all receivers have comparable side information (in terms of conditional
entropy), or, equivalently, have weak side information, a vanishing density can
be achieved. As a result, efficient decoding is possible at all terminals
simultaneously. Simulation results motivate the use of this scheme at
non-limiting rates as well.
