ENTROPY-CONSTRAINED UNIFORM QUANTIZATION
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.
1 . 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.
2 . The method of claim 1 further comprising:
upon determining that the Shannon entropy is within the threshold distance, encoding the quantized vector using an entropy encoding scheme; and
upon determining that the Shannon entropy is not within the threshold distance, performing a search procedure for finding a maximal number of quantization values that will cause the Shannon entropy of the quantized vector to fall within the threshold distance.
3 . The method of claim 2 wherein the search procedure is a double binary search.
4 . The method of claim 1 wherein the K bins are uniformly spaced across the interval.
5 . The method of claim 1 wherein K is initialized to 2 b .
6 . The method of claim 1 wherein K is initialized based a number of quantization values used to quantize another similar vector.
7 . The method of claim 1 wherein the computer system quantizes the vector using deterministic quantization.
8 . 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.
9 . The non-transitory computer readable storage medium of claim 8 wherein the method further comprises:
upon determining that the Shannon entropy is within the threshold distance, encoding the quantized vector using an entropy encoding scheme; and
upon determining that the Shannon entropy is not within the threshold distance, performing a search procedure for finding a maximal number of quantization values that will cause the Shannon entropy of the quantized vector to fall within the threshold distance.
10 . The non-transitory computer readable storage medium of claim 9 wherein the search procedure is a double binary search.
11 . The non-transitory computer readable storage medium of claim 8 wherein the K bins are uniformly spaced across the interval.
12 . The non-transitory computer readable storage medium of claim 8 wherein K is initialized to 2 b .
13 . The non-transitory computer readable storage medium of claim 8 wherein K is initialized based a number of quantization values used to quantize another similar vector.
14 . The non-transitory computer readable storage medium of claim 8 wherein the computer system quantizes the vector using deterministic quantization.
15 . 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.
16 . The computer system of claim 15 wherein the program code further causes the processor to:
upon determining that the Shannon entropy is within the threshold distance, encode the quantized vector using an entropy encoding scheme; and
upon determining that the Shannon entropy is not within the threshold distance, perform a search procedure for finding a maximal number of quantization values that will cause the Shannon entropy of the quantized vector to fall within the threshold distance.
17 . The computer system of claim 16 wherein the search procedure is a double binary search.
18 . The computer system of claim 15 wherein the K bins are uniformly spaced across the interval.
19 . The computer system of claim 15 wherein K is initialized to 2 b .
20 . The computer system of claim 15 wherein K is initialized based a number of quantization values used to quantize another similar vector.
21 . The computer system of claim 15 wherein the computer system quantizes the vector using deterministic quantization.