EUVIMEDEUVIMED entdecken
Crossref

The Capacity of 3 User Linear Computation Broadcast

Yuhang Yao, Syed A. Jafar

IEEE Transactions on Information Theory · 2024-06 · 70 (6) · 4414-4438

DOI: 10.1109/tit.2024.3392685 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2024-06. Verfasst von Yuhang Yao und 1 weiteren Autor:innen. Die Arbeit wurde bisher 11-mal zitiert (Crossref) und nennt 66 Literaturangaben. Gefördert von: NSF, Office of Naval Research.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The K User Linear Computation Broadcast (LCBC) problem is comprised of d dimensional data (from $\mathbb {F}_{q}$ ), that is fully available to a central server, and K users, who require various linear computations of the data, and have prior knowledge of various linear functions of the data as side-information. The optimal broadcast cost is the minimum number of q-ary symbols to be broadcast by the server per computation instance, for every user to retrieve its desired computation. The reciprocal of the optimal broadcast cost is called the capacity. The main contribution of this paper is the exact capacity characterization for the $K=3$ user LCBC for all cases, i.e., for arbitrary finite fields $\mathbb {F}_{q}$ , arbitrary data dimension d, and arbitrary linear side-informations and demands at each user. A remarkable aspect of the converse (impossibility result) is that unlike the 2 user LCBC whose capacity was determined previously, the entropic formulation (where the entropies of demands and side-informations are specified, but not their functional forms) is insufficient to obtain a tight converse for the 3 user LCBC. Instead, the converse exploits functional submodularity. Notable aspects of achievability include sufficiency of vector linear coding schemes, subspace decompositions that parallel those found previously by Yao Wang in degrees of freedom (DoF) studies of wireless broadcast networks, and efficiency tradeoffs that lead to a constrained waterfilling solution. Random coding arguments are invoked to resolve compatibility issues that arise as each user has a different view of the subspace decomposition, conditioned on its own side-information.

Förderung

  • NSF
  • Office of Naval Research

Zitieren

APA

Yao, Y., & Jafar, S. A. (2024). The Capacity of 3 User Linear Computation Broadcast. IEEE Transactions on Information Theory, 70(6), 4414-4438. https://doi.org/10.1109/tit.2024.3392685

Vancouver

Yao Y, Jafar SA. The Capacity of 3 User Linear Computation Broadcast. IEEE Transactions on Information Theory. 2024;70(6):4414-4438. doi:10.1109/tit.2024.3392685

BibTeX
@article{Yao2024,
  author = {Yao, Yuhang and Jafar, Syed A.},
  title = {The Capacity of 3 User Linear Computation Broadcast},
  journal = {IEEE Transactions on Information Theory},
  year = {2024},
  volume = {70},
  number = {6},
  pages = {4414--4438},
  doi = {10.1109/tit.2024.3392685}
}
Kostenlos starten →