Linear Coding Schemes for the Distributed Computation of Subspaces
| Autor: | Lalitha, V., Prakash, N., Vinodh, K., Kumar, P. Vijay, Pradhan, S. Sandeep |
|---|---|
| Rok vydání: | 2013 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1109/JSAC.2013.130406 |
| Popis: | Let $X_1, ..., X_m$ be a set of $m$ statistically dependent sources over the common alphabet $\mathbb{F}_q$, that are linearly independent when considered as functions over the sample space. We consider a distributed function computation setting in which the receiver is interested in the lossless computation of the elements of an $s$-dimensional subspace $W$ spanned by the elements of the row vector $[X_1, \ldots, X_m]\Gamma$ in which the $(m \times s)$ matrix $\Gamma$ has rank $s$. A sequence of three increasingly refined approaches is presented, all based on linear encoders. The first approach uses a common matrix to encode all the sources and a Korner-Marton like receiver to directly compute $W$. The second improves upon the first by showing that it is often more efficient to compute a carefully chosen superspace $U$ of $W$. The superspace is identified by showing that the joint distribution of the $\{X_i\}$ induces a unique decomposition of the set of all linear combinations of the $\{X_i\}$, into a chain of subspaces identified by a normalized measure of entropy. This subspace chain also suggests a third approach, one that employs nested codes. For any joint distribution of the $\{X_i\}$ and any $W$, the sum-rate of the nested code approach is no larger than that under the Slepian-Wolf (SW) approach. Under the SW approach, $W$ is computed by first recovering each of the $\{X_i\}$. For a large class of joint distributions and subspaces $W$, the nested code approach is shown to improve upon SW. Additionally, a class of source distributions and subspaces are identified, for which the nested-code approach is sum-rate optimal. Comment: To appear in IEEE Journal of Selected Areas in Communications (In-Network Computation: Exploring the Fundamental Limits), April 2013 |
| Databáze: | arXiv |
| Externí odkaz: |
|