Linear Compressive Networks

Michael Christoph Gastpar, Naveen Goela
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa, 2009
Conference paper

Abstract

A linear compressive network (LCN) is defined as a graph of sensors in which each encoding sensor compresses incoming jointly Gaussian random signals and transmits (potentially) low-dimensional linear projections to neighbors over a noisy uncoded channel. Each sensor has a maximum power to allocate over signal subspaces. The networks of focus are acyclic, directed graphs with multiple sources and multiple destinations. LCN pathways lead to decoding leaf nodes that estimate linear functions of the original high dimensional sources by minimizing a mean squared error (MSE) distortion cost function. An iterative Optimization of local compressive matrices for all graph nodes is developed using an optimal quadratically constrained quadratic program (QCQP) step. The performance of the optimization is marked by power-compression-distortion spectra, with converse bounds based on cut-set arguments. Examples include single layer and multi-layer (e.g. p-layer tree cascades, butterfly) networks. The LCN is a generalization of the Karhunen-Loeve Transform to noisy multi-layer networks, and extends previous approaches for point-to-point and distributed compression-estimation of Gaussian signals. The framework relates to network coding in the noiseless case, and uncoded transmission in the noisy case.

Official source

https://infoscience.epfl.ch/record/169539?ln=en

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Related publications

Distributed Karhunen-Loeve Transform With Nested Subspaces

Michael Christoph Gastpar, Naveen Goela

A network in which sensors observe a common Gaussian source is analyzed. Using a fixed linear transform, each sensor compresses its high-dimensional observation into a low-dimensional representation. The latter is provided to a central decoder that reconstructs the source according to a mean squared error (MSE) distortion metric. The Distributed Karhunen-Loeve Transform (d-KLT) has been shown to provide a (locally) optimal linear solution for compression at each sensor. While the d-KLT achieves the lowest distortion linear reconstruction known, it does not maintain a nested subspace structure. In the case of ideal links to the decoder, this paper presents transforms that maintain nested subspaces, allowing the decoder to approximate a delay-limited source in an online fashion according to a desired sensor schedule. A distortion envelope for one distributed transform with nested subspace properties (d-nested-KLT) is provided. In the case of i.i.d. noise to the decoder, under assumptions of power allocation over subspaces, it is also possible to achieve nested subspaces utilizing correlations between sensors' observations. Results are applicable for data access over networks, and online information processing in sensor networks.

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

A model called the linear transform network (LTN) is proposed to analyze the compression and estimation of correlated signals transmitted over directed acyclic graphs (DAGs). An LTN is a DAG network with multiple source and receiver nodes. Source nodes transmit subspace projections of random correlated signals by applying reduced-dimension linear transforms. The subspace projections are linearly processed by multiple relays and routed to intended receivers. Each receiver applies a linear estimator to approximate a subset of the sources with minimum mean squared error (MSE) distortion. The model is extended to include noisy networks with power constraints on transmitters. A key task is to compute all local compression matrices and linear estimators in the network to minimize end-to-end distortion. The nonconvex problem is solved iteratively within an optimization framework using constrained quadratic programs (QPs). The proposed algorithm recovers as special cases the regular and distributed Karhunen–Loève transforms (KLTs). Cut-set lower bounds on the distortion region of multi-source, multi-receiver networks are given for linear coding based on convex relaxations. Cut-set lower bounds are also given for any coding strategy based on information theory. The distortion region and compression-estimation tradeoffs are illustrated for different communication demands (e.g., multiple unicast), and graph structures.

Institute of Electrical and Electronics Engineers2012

Network information theory studies the communication of information in a network and considers its fundamental limits. Motivating from the extensive presence of the networks in the daily life, the thesis studies the fundamental limits of particular networks including channel coding such as Gaussian multiple access channel with feedback and source coding such as lossy Gaussian Gray-Wyner network. On one part, we establish the sum-Capacity of the Gaussian multiple-access channel with feedback. The converse bounds that are derived from the dependence-balance argument of Hekstra and Willems meet the achievable scheme introduced by Kramer. Even though the problem is not convex, the factorization of lower convex envelope method that is introduced by Geng and Nair, combined with a Gaussian property are invoked to compute the sum-Capacity. Additionally, we characterize the rate region of lossy Gaussian Gray-Wyner network for symmetric distortion. The problem is not convex, thus the method of factorization of lower convex envelope is used to show the Gaussian optimality of the auxiliaries. Both of the networks, are a long-standing open problem. On the other part, we consider the common information that is introduced by Wyner and the natural relaxation of Wyner's common information. Wyner's common information is a measure that quantifies and assesses the commonality between two random variables. The operational significance of the newly introduced quantity is in Gray-Wyner network. Thus, computing the relaxed Wyner's common information is directly connected with computing the rate region in Gray-Wyner network. We derive a lower bound to Wyner's common information for any given source. The bound meets the exact Wyner's common information for sources that are expressed as sum of a common random variable and Gaussian noises. Moreover, we derive an upper bound on an extended variant of information bottleneck. Finally, we use Wyner's common information and its relaxation as a tool to extract common information between datasets. Thus, we introduce a novel procedure to construct features from data, referred to as Common Information Components Analysis (CICA). We establish that in the case of Gaussian statistics, CICA precisely reduces to Canonical Correlation Analysis (CCA), where the relaxing parameter determines the number of CCA components that are extracted. In this sense, we establish a novel rigorous connection between information measures and CCA, and CICA is a strict generalization of the latter. Moreover, we show that CICA has several desirable features, including a natural extension to beyond just two data sets.

EPFL2021