SPARSITY ESTIMATION FOR DATA TRANSMISSION

• US 20160212245A1
• Filed: 01/21/2015
• Published: 07/21/2016
• Est. Priority Date: 01/21/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Shoaib, Mohammed, Liu, Jie
• Granted Patent: US 10,057,383 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 67/12 specially adapted for proprietary or special-purpose networking environments, e.g. medical networks, sensor networks, networks in vehicles or remote metering networks
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

Disclosed herein are systems and methods for compressing data and for estimating sparsity of datasets to aid in compressing data. A device receives a plurality of samples of the sensor data from the sensor and determine a plurality of bits, in which each bit has a substantially equal probability of being determined as a 0 bit or of being determined as a 1 bit. The device estimates a sparsity value of the sensor data based at least in part on the sequence of bits. The device compresses the received samples of the sensor data based at least in part on the determined sparsity value to provide compressed data and transmits the compressed data via the transmitter to a receiver. Sparse data other than sensor data may also be compressed based at least in part on an estimated sparsity value.

Claims

1. A device comprising:

a sensor configured to output sensor data corresponding to at least one physical property;

a transmitter;

one or more processing unit(s) coupled to the sensor and the transmitter;

one or more computer storage media; and

one or more program modules stored on the one or more computer storage media and executable by the one or more processing unit(s) to;

receive a plurality of samples of the sensor data from the sensor;

determine a plurality of bits, in which each bit has a substantially equal probability of being determined as a 0 bit or of being determined as a 1 bit;

estimate a sparsity value of the sensor data based at least in part on the sequence of bits and the sensor data;

compress the received samples of the sensor data based at least in part on the determined sparsity value to provide compressed data; and

transmit the compressed data via the transmitter to a receiver.

2. The device of claim 1, wherein the one or more program modules are further executable by the one or more processing unit(s) to determine a number of bits to represent the compressed data based at least in part on the estimated sparsity value of the sensor data, and wherein the determined number of bits is positively correlated with the estimated sparsity value.

3. The device of claim 1, wherein the at least one physical property includes a physical property of the device or an environment of the device.

4. The device of claim 1, wherein the one or more program modules are further executable by the one or more processing unit(s) to estimate the sparsity value of the sensor data by:

estimating a respective scale factor of each of a plurality of distributions based at least in part on the plurality of bits and the sensor data; and

estimating the sparsity value by combining the determined respective scale factors.

5. The device of claim 4, wherein the plurality of distributions comprises a Cauchy distribution and a Gaussian distribution and the one or more program modules are further executable by the one or more processing unit(s) to combine the determined respective scale factors by dividing the determined scale factor of the Cauchy distribution by the determined scale factor of the Gaussian distribution.

6. The device of claim 4, wherein the one or more program modules are further executable by the one or more processing unit(s) to estimate the respective scale factor of a selected distribution of the plurality of distributions by:

determining a plurality of distribution vectors from the selected distribution based at least in part on the plurality of bits;

selecting one or more data vector(s) from the received samples of the sensor data;

determining a respective test value for each of the plurality of distribution vectors based at least in part on one of the one or more data vector(s); and

estimating the scale factor by combining the determined respective test values.

7. The device of claim 6, wherein the one or more program modules are further executable by the one or more processing unit(s) to determine the plurality of bits using a linear feedback shift register.

8. The device of claim 6, wherein the one or more program modules are further executable by the one or more processing unit(s) to determine a plurality of elements of each of the plurality of distribution vectors by summing one or more of the plurality of bits.

9. The device of claim 6, wherein the one or more program modules are further executable by the one or more processing unit(s) to sum the one or more of the plurality of bits by determining a respective number of the bits for each of the plurality of distribution vectors based at least in part on a projection basis of the sensor data, and summing the determined number of the bits.

10. A device, comprising:

a bit-sequence generator configured to provide a sequence of bits in which each successive bit has a substantially equal probability of being a 0 bit or a 1 bit;

a sparsity estimator configured to estimate a sparsity value of a data sequence based at least in part on the sequence of bits and a plurality of samples of the data sequence;

a compressor configured to compress the data sequence based at least in part on the estimated sparsity value; and

a transmitter configured to transmit the compressed data sequence.

11. The device of claim 10, wherein the bit-sequence generator includes a linear feedback shift register.

12. The device of claim 10, wherein the sparsity estimator includes:

a first plurality of accumulators configured to determine respective inner products of the sequence of bits with respective values of the data sequence;

a second plurality of accumulators configured to accumulate selected ones of the respective inner products to provide respective test values; and

a plurality of summarizing units configured to provide respective scale factors based at least in part on the respective test values from respective ones of the plurality of second accumulators.

13. The device of claim 12, wherein the first plurality of accumulators includes first, second, and third accumulators, the device further includes a divider configured to output a quotient of the output of the second accumulator and the output of the third accumulator, the second plurality of accumulators includes fourth and fifth accumulators, the fourth accumulator is coupled to the first accumulator, the fifth accumulator is coupled to an output of the divider, and the plurality of summarizing units includes a median-computation unit coupled to the output of the fourth accumulator and a mean-square computation unit coupled to the output of the fifth accumulator.

14. The device of claim 12, further including a processing unit configured to receive a projection basis of the data sequence and determine respective counts for each of the accumulators of the first plurality of accumulators based at least in part on the projection basis, wherein each accumulator of the first plurality of accumulators is configured to accumulate a number of the samples of the data sequence equal to the determined respective count.

15. A data-compression method, comprising:

determining a plurality of bits, in which each individual bit has a substantially equal probability of being determined as a 0 bit or of being determined as a 1 bit;

estimating a sparsity value of data to be compressed based at least in part on the plurality of bits; and

compressing the data based at least in part on the determined sparsity value to provide compressed data.

16. The method of claim 15, wherein the determining comprises operating a linear feedback shift register that produces successive ones of the plurality of bits.

17. The method of claim 15, wherein the estimating comprises:

estimating a respective scale factor of each of a plurality of distributions based at least in part on the plurality of bits and the data to be compressed; and

estimating the sparsity value by combining the determined respective scale factors.

18. The method of claim 17, wherein the estimating the scale factor for a selected distribution of the plurality of distributions comprises:

determining a plurality of distribution vectors from the selected distribution based at least in part on the plurality of bits;

computing inner products of the distribution vectors and corresponding samples of the data to be compressed; and

combining the computed inner products to estimate the scale factor for the selected distribution.

19. The method of claim 18, wherein the estimating the scale factor for a selected distribution of the plurality of distributions further comprises determining a respective number of bits for each of the plurality of distribution vectors based at least in part on a projection basis of the sensor data.

20. The method of claim 17, wherein the plurality of distributions comprises a Cauchy distribution and a Gaussian distribution and the estimating the sparsity value comprises dividing the estimated scale factor of the Cauchy distribution by the estimated scale factor of the Gaussian distribution.