1 March 2007 Dynamics of low-cost transmission on the optimal path
Author Affiliations +
Abstract
The transmission system must simultaneously determine transmission rates that balance total profit from bit allocation with transmission costs. The objective is to maximize the present value of the satisfaction derived from progressive transmission over the future, subject to constraints imposed by the initial conditions and the prioritization and transmission technologies. The analytical results demonstrate an oscillatory behavior over time of the rent component of profit depending on the incremental cost of cumulative transmission and not the current marginal transmission cost. This oscillatory behavior of rent over time necessitates devising a stabilizing scheme for its optimal use in the transmission.
Garcia, Rodriguez-Sánchez, and Fdez-Valdivia: Dynamics of low-cost transmission on the optimal path

1.

Introduction

In any efficient transmission system there must be visual data of low-cost transmission that enter into a prioritization protocol and are used up. The available low-cost bit streams cannot be increased. In the long run, the limited availability of these exhaustible bit streams would begin to act as a constraint on the performance of the transmission system. Within such a system, the “rent” component of profit for the transmission of visual data at present time t can be defined as the difference between profit and transmission cost. It reflects the opportunity cost of transmitting a unit of visual information at time t rather than conserving it for the future bit allocation. Thus, the time path of this rent has strong implications for the transmission.

Of course, the exhaustibility of bit streams with low-cost transmission could restrict the efficiency at higher bit rates.1, 2, 3 Hence there is a concern for this problem and understanding its implications is essential to attaining efficiency in intertemporal models of progressive transmission. In fact, the issue of depletion in low-cost bit resources forces us to think about bit allocation over time: The more we allocate low-cost visual data for transmission at this time, the less that will be available at higher bit rates. For example, assuming that the rent component received from progressive transmission would steadily decrease as the low-cost bit resource is depleted, the system should prefer to transmit data at this time over conserving them for the future. The danger is that if the trends in rent component of profit shift from declining to rising at least temporarily over time, heavy losses may be incurred in the form of foregone transmission opportunities in the future. Therefore, it would be too risky to rely on predictions of a monotonic time path of the rent component for bit resources from models that predict steadily rising rents or steadily declining rents.

Following Ref. 4, here we show the difficulty of predicting the rent component of profit. It warns us not to base long-term bit allocation decisions on extrapolations of the rent component of profit during a transitory phase of the oscillatory long-term path. For example, a progressive transmission scheme seeks the largest distortion reduction by ordering the coefficients by magnitude and transmitting the most significant bits first; whereas zero trees are used to the prediction of insignificant coefficients across scales to be efficiently represented as part of exponentially growing trees.5 It assumes therefore a declining rent component since the distortion reduction decreases over time and it becomes increasingly difficult to expect zero trees to occur, even though it is possible that the rent component shifts from declining to rising at least temporarily due to the complexity of the visual data.

2.

Present Satisfaction Derived from Progressive Transmission over the Future

Consider a transmission system that chooses a rate of transmission at time t given by bit allocation qt . This system takes as the profit pt×qt that would be obtained by qt at t , where pt is the unit profit derived from the transmission at time t .

Because, in general, most of the coding gain is at lower bit rates, an exponentially decaying factor exp(δt) , with δ> 0 , will be introduced in the analysis to be able to compute the discounted value of profit from transmission at future times using higher bit rates, with δ being the discount rate. It diminishes the weight given to future profits (at higher bit rates) in the summation of the satisfaction over all the bit rates to form a total score. The smaller the weight, the larger the discount rate δ . Within this model of transmission, the center is given by this intertemporal conflict between present and future bit use and its profits.

Also, we assume that the total cost of transmission at time t is given by a twice continuously differentiable function Ct=C(qt,zt,Rt) with zt being the cumulative bit streams transmitted by time t : zt=0tqτdτ ; and Rt is an index of the state of prioritization and transmission technologies at time t , with Ṙt=dRtdt> 0 measuring its incremental improvement over time due to optimal exploratory activity to build a knowledge base.6

For a given condition of prioritization and transmission technologies, the total transmission cost Ct=C(qt,zt,Rt) increases with the transmission rate qt at the present time as well as the cumulative bit streams zt transmitted by time t . That is, we have that Cqt=Ctqt> 0 and Czt=Ctzt> 0 . There is also a cost-reducing effect of exploratory activity to increase the knowledge level for prioritization and transmission, and so we have that CRt=CtRt<0 .

Then, the transmission system must simultaneously determine transmission rates that balance total profit from bit allocation with transmission costs. The objective is to maximize the present value of the satisfaction (value function) derived from progressive transmission over the future

1

max0exp(δt)s(qt)dt
with
s(qt)=ptqtCt
and subject to constraints imposed by the initial conditions and the prioritization and transmission technologies

2

dztdt=qt0
and given that

3

z0=0.

Pontryagin’s maximum principle7 provides a solution to this optimization problem where the variable of control is the rate of transmission qt through which we expect to characterize the optimal transmission plan, and the variable of state is the cumulative bit streams zt transmitted by time t . Thus, we can form the Hamiltonian H of this optimization problem, using the equation of motion 2

4

H=[ptqtCt]exp(δt)+λtexp(δt)qt.

We can derive the necessary conditions for solving this problem and then use them to establish the behavior of the rent component of profit. The canonical equation of the Pontryagin’s maximum principle,7 for the control variable is Htqt=0 . Hence, maximizing with respect to the control variable qt , we obtain the necessary condition

5

pt+λt=Cqt
with Cqt=Ctqt .

For the state and costate variables, we have the condition Hzt=d[λtexp(δt)]dt . Hence, differentiating H with respect to the state variable zt gives the dynamic equation for λt

6

λ̇tδλt=Czt
with λ̇t=dλtdt and Czt=Ctzt . The key to understanding our interpretation of optimal control theory is the shadow value λt of the cumulative bit resources zt transmitted by time t . The very definition of the shadow value originates from one of the relationships between the maximum principle and dynamic programming, namely, the shadow value (costate variable) λt is the rate of change of the satisfaction measure (value function) with respect to the change of the cumulative bit resource zt prioritized by time t (state variable). Seen from a different vantage point, λt is just the shadow value of an unexploited unit of bit resource still available at time t , or simply, the shadow value of the rent component of profit at time t .

For an interior optimum, qt0 , we must have that

7

limtλtexp(δt)=0,and0<limtzt=z¯<,
where z¯ represents the upper limit of the cumulative transmission.

By solving the differential equation 6, we have that

8

λt=texp[δ(τt)]Czτdτ.
Thus, it follows that the shadow rent component of profit λt measures the discounted sum of the incremental transmission costs that an additional unit of bit resources transmitted at t brings about in that period and over all future periods by increasing cumulative bit streams zτ transmitted by time τ with τt .

Following Ref. 4, we have that, on the optimal transmission path, the profit pt for the transmission at any time should cover the marginal transmission cost Cqt(qt,zt,Rt) plus the shadow rent component of profit λt

9

pt=Cqt(qt,zt,Rt)+texp[δ(τt)]Czτ(qτ,zτ,Rτ)dτ,
where Cqt(qt,zt,Rt)=C(qt,zt,Rt)qt and similarly Czτ(qτ,zτ,Rτ)=C(qτ,zτ,Rτ)zτ .

We can now examine the change of the rent component of profit and the optimal path of bit depletion for the transmission of visual data by differentiating Eq. 5 with respect to time and using Eq. 6

10

ddtln(ptCqt)=δCzttexp[δ(τt)]Czτdτ
with Cqt=Cqt(qt,zt,Rt) and Czτ=Czτ(qτ,zτ,Rτ) . It follows that the rent component of profit changes at a rate equal to the discount rate δ minus the ratio between Czt and texp[δ(τt)]Czτdτ , which, in general, varies with time.

Consider that f(t)=texp(δτ)Czτdτ and g(t)=exp(δt) . From Eq. 8, it follows that

11

limtλt=limtf(t)g(t).
Using L’Hôpital’s rule for 00 , it follows that if limf(t)=limg(t)=0 , then limf(t)g(t)=lim[(df(t)dt)(dg(t)dt)] , so we have that the limit of λt is

12

limtλt=1δlimtCzt(qt,zt,Rt),
which gives the behavior of λt over time.

Substituting Eq. 8 into Eq. 6 and integrating by parts, it follows that

13

λ̇t=texp[δ(τt)]ddτCzτ(qτ,zτ,Rτ)dτ
with
ddτCzτ(qτ,zτ,Rτ)=Czτqτdqτdτ+Czτzτqτ+CzτRτdRτdτ.

3.

Behavior of the Rent Component of Profit

From Eqs. 8, 12, 13, it is evident that the shadow rent component of profit is complex, because it depends on the shape of Czτ and its rate of change with time. Thus λt can increase monotonically, monotonically decrease, remain constant, or change nonmonotically over time, depending on how the incremental cost of cumulative transmission Czτ varies with time, τt , and not the current marginal transmission cost Cqt at time t . The optimal path of the rent component of profit does not need to have any particular relationship with movements in the marginal transmission cost Cqt .

If Czτ increases (respectively, decreases) monotonically over time, (ddτ)Czτ> 0 (respectively, (ddτ)Czτ<0 ), then from Eq. 13, it follows that λt increases (respectively, decreases) monotonically.

In the case that Czτ takes a nonmonotonic form, then there exists a τ*> 0 such that (ddτ)Czτ*=0 and (ddτ)Czτ0 in some interval of τ* . From Eq. 12, and the continuity of λt and Czt on t , it follows that

14

limtĊzt=limtλ̇t=0,
because limtλ̇t=0 by taking limit of Eq. 6 as t and using Eq. 12. Then by Eqs. 13, 14, we have that there exits some t=t* for which λt=0 . Hence it follows that λt will be nonmonotonic.

Because some state of the art models seem to assume a declining rent component without any consideration to the behavior of the incremental cost of cumulative transmission Czτ , an interesting question is whether there exist special cases where the rent component of profit falls monotonically to zero regardless of the incremental cost of cumulative transmission. Effectively, assuming δ=0 in the exponentially decaying factor exp(δt) that was used to compute the discounted value of profit from transmission at future times (i.e., we do not diminish the weight given to future profits), we have that Eq. 12 reduces to

λt=tCzτdτ.
Then, since Czτ> 0 , we have that
limtλt=0
and differentiating with respect to t
λ̇t=Czt<0.
Thus it follows that, if we do not diminish the weight given to future profits in the summation of the satisfaction over all the bit rates to form a total score, then the rent component of profit falls monotonically to zero regardless of the shape of the incremental cost of cumulative transmission. However, in this special case, the underlying assumption (regarding the intertemporal conflict between present and future bit use and its profits) fails to note that, in general, most of the coding gain is at lower bit rates.

Using Eq. 8, the path of the rent component of profit for particular definitions of the incremental cost of cumulative transmission Czt can be seen:

  • 1. In the case where Czt is constant over time (i.e., Czt=a ), substituting this in Eq. 8 and integrating yields a constant path for the rent component of profit over time λt=aδ .

  • 2. But in the case where Czt=a+bt+ct2 , the rent component of profit is obtained from the integration of Eq. 8 as λt=[aδ+bδ2+2cδ3]+[bδ+2cδ2]t+[cδ]t2 , where the rent component of profit may first increase to a maximum and then decline to a minimum, or alternatively, the rent may also exhibit the reverse nonmonotonic behavior (i.e., it first declines and then increases). This illustrates the oscillatory behavior over time of the rent component of profit, depending on the incremental cost of cumulative transmission.

4.

Conclusion

Under the assumption of either oscillatory or increasing behavior of rent component of profit over time, heavy losses may be incurred in the form of foregone transmission opportunities in the future if the transmission system prefers to transmit data at this time over conserving (at least a part of them) for the future. It calls for a saving rate and an accumulation of low-cost bits at the present time than would be necessary in the case of a steadily declining rent component of profit. The system would then modify the transmission condition accordingly to render it dynamically efficient over time.

Acknowledgments

This research was sponsored by the Spanish Board for Science and Technology (CICYT) under Grant No. TIC2003-00473. The authors thank Michael Bove for suggesting improvements to the original manuscript.

References

1.  H. Wang, G. M. Schuster, and A. K. Katsaggelos, “Rate-distortion optimal bit allocation for object-based video coding,” IEEE Trans. Circuits Syst. Video Technol.1051-8215 15(9), 1113–1123 (2005). Google Scholar

2.  C. Jianfei, H. Zhihai, and W. C. Chang, “A novel frame-level bit allocation based on two-pass video encoding for low bit rate video streaming applications,” J. Visual Commun. Image Represent1047-3203 17, 783–798 (2006). Google Scholar

3.  L. Zhijun and D. G. Nicolas, “An accurate bit-rate control algorithm for video transcoding,” J. Visual Commun. Image Represent1047-3203 10.1016/S1047-3203(03)00018-X 14, 321–339 (2003). Google Scholar

4.  Y. H. Farzin, “The time path of scarcity rent in the theory of exhaustible resources,” Econom. J.0013-0133 102, 813–830 (1992). Google Scholar

5.  B.-J. Kim, Z. Xiong, and W. A. Pearlman, “Low bit-rate scalable video coding with 3D set partitioning in hierarchical trees (3D-SPIHT),” IEEE Trans. Circuits Syst. Video Technol.1051-8215 10.1109/76.889025 10, 1374–1387 (2000). Google Scholar

6.  J. A. Garcia, R. Rodriguez-Sanchez, and J. Fdez-Valdivia, “Optimal exploratory effort to build knowledge for video transmission,” Opt. Eng.0091-3286 46 (2007). Google Scholar

7.  L. S. Pontryagin, V. G. Boltayanskii, R. V. Gamkrelidze, and E. F. Mishchenko, “The mathematical theory of optimal processes,” Wiley, Hoboken, NJ (1962) (Translated from Russian). Google Scholar

Jose Antonio Garcia, Rosa Rodriguez-Sanchez, Joaquin Fdez-Valdivia, "Dynamics of low-cost transmission on the optimal path," Optical Engineering 46(3), 030503 (1 March 2007). https://doi.org/10.1117/1.2717132
JOURNAL ARTICLE
3 PAGES


SHARE
Back to Top