Processing math: 100%
Spectral Radii of Asymptotic Mappings and the Convergence Speed of the Standard Fixed Point Algorithm | IEEE Conference Publication | IEEE Xplore

Spectral Radii of Asymptotic Mappings and the Convergence Speed of the Standard Fixed Point Algorithm


Abstract:

Important problems in wireless networks can often be solved by computing fixed points of standard or contractive interference mappings, and the conventional fixed point a...Show More

Abstract:

Important problems in wireless networks can often be solved by computing fixed points of standard or contractive interference mappings, and the conventional fixed point algorithm is widely used for this purpose. Knowing that the mapping used in the algorithm is not only standard but also contractive (or only contractive) is valuable information because we obtain a guarantee of geometric convergence rate, and the rate is related to a property of the mapping called modulus of contraction. To date, contractive mappings and their moduli of contraction have been identified with case-by-case approaches that can be difficult to generalize. To address this limitation of existing approaches, we show in this study that the spectral radii of asymptotic mappings can be used to identify an important subclass of contractive mappings and also to estimate their moduli of contraction. In addition, if the fixed point algorithm is applied to compute fixed points of positive concave mappings, we show that the spectral radii of asymptotic mappings provide us with simple lower bounds for the estimation error of the iterates. An immediate application of this result proves that a known algorithm for load estimation in wireless networks becomes slower with increasing traffic.
Date of Conference: 15-20 April 2018
Date Added to IEEE Xplore: 13 September 2018
ISBN Information:
Electronic ISSN: 2379-190X
Conference Location: Calgary, AB, Canada

1. Introduction

The objective of this study is to investigate convergence properties of the sequence generated by the following instance of the standard fixed point algorithm: \begin{equation*} \pmb{x}_{n+1}=T(\pmb{x}_{n}), \tag{1} \end{equation*} where is an arbitrary initial point; denotes the set of nonnegative vectors of dimension ; and : is a standard interference mapping as defined in [1] or a ( -)contractive mapping as defined in [2], or both. Previous studies [1], [2] have shown that, if is a standard interference mapping with or a contractive mapping, then Fix is a singleton, and the sequence generated by (1) converges to the fixed point Fix . The algorithm in (1) plays a pivotal role in many power and resource allocation mechanisms in wireless networks [1]–[14], so establishing its convergence rate is a problem of significant practical importance [2], [5], [6], [8].

References

References is not available for this document.