Spectral radii of asymptotic mappings and the convergence speed of the\n standard fixed point algorithm

Renato L. G. Cavalcante, Sławomir StańczakarXiv 2018 · DOI · arXiv

Abstract

Important problems in wireless networks, such as power control and load estimation, are often solved by computing fixed points of interference mappings. While the standard fixed-point algorithm is widely used, determining its convergence rate—governed by the modulus of contraction—has historically required case-by-case analysis. This paper introduces a general framework using the spectral radii of asymptotic mappings to identify contractive mappings and estimate their convergence speeds. For positive concave mappings, this approach provides simple lower bounds for estimation errors, revealing that algorithms for network load estimation naturally slow down as traffic increases.

Introduction

In wireless network optimization, many critical tasks are modeled as finding a stable state, or "fixed point," of a system mapping ($T$). The efficiency of these systems depends on the standard fixed-point algorithm, which iteratively applies the mapping until convergence. A key challenge for researchers is determining whether a mapping is "contractive" and identifying its "modulus of contraction," which dictates the geometric rate at which the error decreases.

Existing methods for identifying these properties are often manual and difficult to generalize. This study addresses this limitation by leveraging asymptotic mappings ($T_\infty$), which describe the behavior of the system at large scales, to provide a computationally efficient tool for convergence analysis.

Methodology

The core of this framework is the relationship between the spectral radius ($\rho$) of an asymptotic mapping and the convergence properties of the original algorithm. The authors provide an iterative method to compute this spectral radius and apply it to two primary classes of mappings:

  1. Convex Mappings: For convex interference mappings, the spectral radius of the asymptotic mapping is both a necessary and sufficient condition for contractivity. If $\rho(T_\infty) < 1$, the algorithm is guaranteed to converge geometrically.
  2. Concave Mappings: For positive concave mappings, the spectral radius provides a theoretical "speed limit"—a lower bound on the estimation error that the algorithm cannot exceed.

Numerical Validation and Key Insights

The researchers validated their framework using a simulated LTE/5G network scenario with 1,500 users. By testing a nonlinear load estimation mapping, they compared actual iteration errors against the theoretical bounds derived from the spectral radius.

Convergence of the fixed-point algorithm (FPI) compared to theoretical bounds for different mappings.

As shown in the figure above, the theoretical lower bounds derived from the spectral radius closely track the actual estimation error over hundreds of iterations. This confirms that the spectral radius of the simpler asymptotic form $T_\infty$ accurately reflects the fundamental convergence limits of the complex nonlinear mapping $T$.

The Traffic-Speed Tradeoff

A significant finding of this research is the formal proof of the traffic-speed tradeoff. As network traffic increases, the spectral radius of the load estimation mapping approaches 1. This provides a rigorous mathematical explanation for why fixed-point algorithms become significantly slower exactly when the network is under the highest stress, as the modulus of contraction nears the limit of non-convergence.

Conclusion

By shifting the focus to asymptotic mappings, this study provides a generalized tool for analyzing convergence in wireless networks. While currently optimized for purely convex or concave mappings, this framework offers a foundation for designing acceleration techniques. Understanding the spectral properties of interference mappings allows for more predictable and efficient network optimization, particularly as systems scale in complexity.

Summary updated

Abstract

Important problems in wireless networks can often be solved by computing\nfixed points of standard or contractive interference mappings, and the\nconventional fixed point algorithm is widely used for this purpose. Knowing\nthat the mapping used in the algorithm is not only standard but also\ncontractive (or only contractive) is valuable information because we obtain a\nguarantee of geometric convergence rate, and the rate is related to a property\nof the mapping called modulus of contraction. To date, contractive mappings and\ntheir moduli of contraction have been identified with case-by-case approaches\nthat can be difficult to generalize. To address this limitation of existing\napproaches, we show in this study that the spectral radii of asymptotic\nmappings can be used to identify an important subclass of contractive mappings\nand also to estimate their moduli of contraction. In addition, if the fixed\npoint algorithm is applied to compute fixed points of positive concave\nmappings, we show that the spectral radii of asymptotic mappings provide us\nwith simple lower bounds for the estimation error of the iterates. An immediate\napplication of this result proves that a known algorithm for load estimation in\nwireless networks becomes slower with increasing traffic.\n
BibTeX
@misc{cavalcante2018spectral,
  author = {Renato L. G. Cavalcante and Sławomir Stańczak},
  title = {{Spectral radii of asymptotic mappings and the convergence speed of the\textbackslash\{\}n standard fixed point algorithm}},
  year = {2018},
  eprint = {1803.05671},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1803.05671},
}
Figure