Improved bounds for the rate loss of multiresolution source codes

We present new bounds for the rate loss of multiresolution source codes (MRSCs). Considering an M-resolution code, the rate loss at the ith resolution with distortion D_i is defined as L_i=R_i-R(D_i), where R_i is the rate achievable by the MRSC at stage i. This rate loss describes the performance degradation of the MRSC compared to the best single-resolution code with the same distortion. For two-resolution source codes, there are three scenarios of particular interest: (i) when both resolutions are equally important; (ii) when the rate loss at the first resolution is 0 (L₁=0); (iii) when the rate loss at the second resolution is 0 (L₂=0). The work of Lastras and Berger (see ibid., vol.47, p.918-26, Mar. 2001) gives constant upper bounds for the rate loss of an arbitrary memoryless source in scenarios (i) and (ii) and an asymptotic bound for scenario (iii) as D₂ approaches 0. We focus on the squared error distortion measure and (a) prove that for scenario (iii) L₁<1.1610 for all D₂1; (b) tighten the Lastras-Berger bound for scenario (ii) from L₂≤1 to L₂<0.7250; (c) tighten the Lastras-Berger bound for scenario (i) from L_i≤1/2 to L_i<0.3802, i∈{1,2}; and (d) generalize the bounds for scenarios (ii) and (iii) to M-resolution codes with M≥2. We also present upper bounds for the rate losses of additive MRSCs (AMRSCs). An AMRSC is a special MRSC where each resolution describes an incremental reproduction and the kth-resolution reconstruction equals the sum of the first k incremental reproductions. We obtain two bounds on the rate loss of AMRSCs: one primarily good for low-rate coding and another which depends on the source entropy.