Multiple-Description $l_{1}$ -Compression

Multiple descriptions (MDs) is a method to obtain reliable signal transmissions on erasure channels. An MD encoder forms several descriptions of the signal and each description is independently transmitted across an erasure channel. The reconstruction quality then depends on the set of received descriptions. In this paper, we consider the design of redundant descriptions in an MD setup using l₁-minimization with Euclidean distortion constraints. In this way we are able to obtain sparse descriptions using convex optimization. The proposed method allows for an arbitrary number of descriptions and supports both symmetric and asymmetric distortion design. We show that MDs with partial overlapping information corresponds to enforcing coupled constraints in the proposed convex optimization problem. To handle the coupled constraints, we apply dual decompositions which makes first-order methods applicable and thereby admit solutions for large-scale problems, e.g., coding entire images or image sequences. We show by examples that the proposed framework generates non-trivial sparse descriptions and non-trivial refinements. We finally show that the sparse descriptions can be quantized and encoded using off-the-shell encoders such as the set partitioning in hierarchical trees (SPIHT) encoder, however, the proposed method shows a rate-distortion loss compared to state-of-the-art image MD encoders.