Method and apparatus to perform functional compression
AssigneeMassachusetts Institute of Technology
InventorsMuriel Médard, Soheil Feizi-Khankandi
Life of this patent
Estimating the term…
Abstract
A functional compression scheme involves determining a minimal entropy coloring of a characteristic graph of a random variable. Various scenarios are disclosed where the determination of the minimal entropy coloring of a characteristic graph is easy and tractable.
Claims15
In a network having multiple source nodes that each generate a random variable and that are to transmit information to a receiver node that will allow the receiver node to compute a function of the random variables, a method for compressing and transmitting data at a first node of the network, comprising:
- generating a characteristic graph for a random variable associated with the first node of the network with respect to random variables associated with other nodes of the network, a joint probability distribution between random variables of the network, and the function of the random variables that is to be computed at the receiver node, wherein the vertices of the characteristic graph are the possible values of the random variable associated with the first node;
- determining a minimum entropy coloring of the characteristic graph for the random variable associated with the first node, wherein determining a minimum entropy coloring of the characteristic graph includes:
- identifying maximal independent sets of the characteristic graph for the random variable associated with the first node;
- and
- assigning a different color to the vertices of each identified maximal independent set;
- encoding the minimum entropy coloring of the characteristic graph to generate an encoded minimum entropy coloring of the characteristic graph;
- and
- transmitting the encoded minimum entropy coloring of the characteristic graph for the random variable associated with the first node to another node in the network.
A node device for use in a network having multiple source nodes and a receiver node, the multiple source nodes to each generate a random variable and to transmit information to the receiver node that will allow the receiver node to calculate a function of the random variables, the node device comprising:
- a first processor to generate a characteristic graph for a random variable associated with the node device, wherein the characteristic graph is generated with respect to other random variables in the network, the joint probability distributions p(x1, x2) between the random variables, and a network function to be calculated at the receiver node;
- a second processor to determine a minimum entropy coloring of the characteristic graph, wherein the second processor determines the minimum entropy coloring by first identifying maximal independent sets of the characteristic graph for the random variable and then assigning a different color to the vertices of each identified maximal independent set;
- an encoder to encode the minimum entropy coloring of the characteristic graph to generate an encoded minimum entropy coloring;
- and
- a transmitter to transmit the encoded minimum entropy coloring to another node in the network.
A non-transitory computer readable medium for use in connection with a network having multiple source nodes that each generate a random variable and that are to transmit information to a receiver node that will allow the receiver node to compute a function of the random variables, the computer readable medium having instructions stored thereon that, when executed by a computer, perform the method of:
- generating a characteristic graph for a random variable associated with a first node of the network with respect to random variables associated with other nodes of the network, a joint probability distribution between random variables of the network, and the function of the random variables that is to be computed at the receiver node, wherein the vertices of the characteristic graph are the possible values of the random variable associated with the first node;
- determining a minimum entropy coloring of the characteristic graph for the random variable associated with the first node, wherein determining a minimum entropy coloring of the characteristic graph includes:
- identifying maximal independent sets of the characteristic graph for the random variable associated with the first node;
- and
- assigning a different color to the vertices of each identified maximal independent set;
- encoding the minimum entropy coloring of the characteristic graph to generate an encoded minimum entropy coloring of the characteristic graph;
- and
- transmitting the encoded minimum entropy coloring of the characteristic graph for the random variable associated with the first node to another node in the network.
Dependencies are inferred from the claim text.