Entropy-constrained uniform quantization
AssigneeVMware, Inc.
InventorsYaniv Ben-Itzhak, Shay Vargaftik, Ron Dorfman
Life of this patent
Estimating the term…
Abstract
Embodiments of the present disclosure provide a data compression technique, referred to as entropy-constrained uniform quantization (ECUQ), that performs lossy compression of a real valued vector in a manner that ensures a size budget for the compressed vector. In one set of embodiments, ECUQ achieves this by finding “close-to-the-best” quantization values for quantizing the vector in view of the size budget via a fast and robust search procedure.
Claims21
A method comprising:
- receiving, by a computer system, a vector comprising a plurality of real value coordinates;
- determining, by the computer system, an interval between a minimal coordinate of the vector and a maximal coordinate of the vector;
- dividing, by the computer system, the interval into K bins using a fixed rule;
- determining, by the computer system, a set of K quantization values based on the K bins;
- quantizing, by the computer system, the vector using the set of K quantization values, resulting in a quantized vector;
- computing, by the computer system, an empirical distribution of the quantized vector;
- computing, by the computer system, a Shannon entropy of the quantized vector based on the empirical distribution;
- and
- checking, by the computer system, whether the Shannon entropy is within a threshold distance below a per-coordinate size budget b for the vector after compression.
A non-transitory computer readable storage medium having stored thereon program code executable by a computer system, the program code causing the computer system to execute a method comprising:
- receiving a vector comprising a plurality of real value coordinates;
- determining an interval between a minimal coordinate of the vector and a maximal coordinate of the vector;
- dividing the interval into K bins using a fixed rule;
- determining a set of K quantization values based on the K bins;
- quantizing the vector using the set of K quantization values, resulting in a quantized vector;
- computing an empirical distribution of the quantized vector;
- computing a Shannon entropy of the quantized vector based on the empirical distribution;
- and
- checking whether the Shannon entropy is within a threshold distance below a per-coordinate size budget b for the vector after compression.
A computer system comprising:
- a processor;
- and
- a non-transitory computer readable medium having stored thereon program code that, when executed, causes the processor to:
- receive a vector comprising a plurality of real value coordinates;
- determine an interval between a minimal coordinate of the vector and a maximal coordinate of the vector;
- divide the interval into K bins using a fixed rule;
- determine a set of K quantization values based on the K bins;
- quantize the vector using the set of K quantization values, resulting in a quantized vector;
- compute an empirical distribution of the quantized vector;
- compute a Shannon entropy of the quantized vector based on the empirical distribution;
- and
- check whether the Shannon entropy is within a threshold distance below a per-coordinate size budget b for the vector after compression.
Dependencies are inferred from the claim text.