Rapid Near-Optimal VQ Design with a Deterministic Data Net
Michelle Effros
1
and Leonard J. Schulman
2
California Institute of Technology
·
Pasadena, California 91125
We present a new algorithm for fixed-rate vector
quantizer (VQ) design.
A fixed-rate VQ of dimen-
sion
d
and rate (log
K
)
/d
represents each vector in
IR
d
by one of
K
possible codewords. Given a pdf
p
(
x
)onIR
d
and an integer
K
≥
1, an optimal VQ
{
μ
1
,...,μ
K
}⊂
IR
d
achieves expected distortion ∆ =
min
{
μ
1
,...,μ
K
}⊂
IR
d
∫
IR
d
p
(
x
)min
k
∈{
1
,...,K
}
||
x
−
μ
k
||
2
d
x
.
Let
p
(
x
) denote the empirical distribution of an
n
-
point training set. Optimal VQ design is NP-hard even
for
K
= 2 [1]. Iterative design finds a locally optimal
VQ [4]. For any
ε>
0, an
ε
-approximation algorithm
guarantees a VQ with expected distortion
D
≤
(1 +
ε
)∆.
The best prior
ε
-approximation algorithms are a deter-
ministic
O
(
ε
−
2
K
2
d
n
log
K
n
)-time
ε
-approximation [5] and
a randomized
O
(exp(
ε
−
8
K
3
(ln
K
)(ln
1
ε
+ln
K
))
n
log
K
n
)-
time
ε
-approximation [2]. (The problem is called “
K
-
clustering” and “
K
-median” in those papers.)
We present a new deterministic
ε
-approximation algo-
rithm running in time quasilinear in
n
. The algorithm,
which also serves as an approximation algorithm for the
d
-dimensional fixed-rate operational distortion-rate func-
tion, extends to a variety of network VQ problems.
Define a
data net
to be a set
Z⊂
IR
d
,regions
{
A
z
}
z
∈Z
,
and mapping
ζ
:IR
d
→Z
such that
1.
∫
A
z
p
(
x
)
||
x
−
z
||
2
d
x
≤
ε
∆
/K
for all
z
∈Z
2. For any
μ
∈
R
d
and
x
∈
A
ζ
(
μ
)
,
||
x
−
ζ
(
μ
)
||
2
≤
(1 +
ε
)
||
x
−
μ
||
2
.
Our deterministic algorithm designs a data net of size
M
=
c
d
K
2
(
K
2
+
ε
−
2
)
ε
−
d
−
1
for some constant
c
, within
time
Mn
log log
n
and then returns the best codebook
{
μ
1
,...,μ
K
}⊂Z
.
Theorem 1
The above deterministic algorithm finds a
rate-
(log
K
)
/d
fixed-rate VQ with distortion
D
≤
(1+
ε
)∆
within time
Mn
log log
n
+
M
K
+1
n.
Subsequent to codebook design, individual encodings can
be peformed in time log(
K/ε
) using [3].
We can improve Theorem 1’s dependence on
K
at the
expense of
d
. The algorithm can also perform efficient VQ
design for simply characterized continuous distributions.
The algorithm generalizes to give
ε
-approximation al-
gorithms for many network VQ design problems. A few
1
M. Effros (
effros@caltech.edu
) is partially supported by NSF
CCR-0220039 and Caltech’s Lee Center for Advanced Networking.
2
L. J. Schulman (
schulman@caltech.edu
) is partially supported
by NSF CCR-0049092, the Charles Lee Powell Foundation, and a
visiting membership at MSRI.
examples follow. Many more examples (including all com-
bintations of listed examples) follow similarly.
Multiresolution VQ (MRVQ):
A transmitter de-
scribes source
X
to
L
receivers. Receiver
gets only the
first
∑
i
=1
log
K
i
bits of the binary description.
Multiple description VQ (MDVQ):
A transmitter
sends
L
packets describing source
X
. Any subset of pack-
ets may be lost in transmission.
Side information VQ (SIVQ):
A transmitter describes
source
X
to a receiver that has access to side information
unavailable to the encoder.
Broadcast VQ (BCVQ):
A transmitter describes mul-
tiple sources to a family of decoders. Each source is in-
tended for a distinct subset of the receivers, and each
component of the description is received by a distinct
subset of the receivers.
Joint source-channel VQ (JSCVQ):
A transmitter
describes a single source to a single receiver. The de-
scription may be corrupted during transmission.
Remote source VQ (RSVQ):
An encoder observes a
noisy copy of the true source and describes it to the de-
coder. The decoder reconstructs the true source as accu-
rately as possible.
In each example, let
S
be the number of sources (
S
=1
in all but the BCVQ),
K
be the maximal number of code-
words that can be distinguished by any single decoder,
T
be the total number of
d
-dimensional codewords in the
code, and ∆ be the optimal performance (an expected
distortion over some distribution on the reconstructions
at different receivers).
Theorems 2–7
In each scenario above, designing a
data net of size
M
=
c
d
K
2
(
K
2
+
ε
−
2
)
ε
−
d
−
1
for each
source, and using the best
T
codewords from those data
nets gives a code with performance
D
≤
(1 +
ε
)∆
in time
SMn
log log
n
+(
SM
)
T
+1
n.
References
[1] P. Drineas, A. Frieze, R. Kannan, S. Vempala, and V. Vinay.
Clustering in large graphs and matrices. In
Proc. 10th Annual
ACM-SIAM Symposium on Discrete Algorithms (SODA)
, 1999.
[2] W. Fernandez de la Vega, M. Karpinski, C. Kenyon, and Y. Ra-
bani. Approximation schemes for clustering problems. In
Proc.
35’th Ann. Symp. on Theory of Computing (STOC)
, 2003.
[3] S. Har-Peled. A replacement for Voronoi diagrams in near linear
size. In
Proc. 42nd Annual IEEE Symposium on Foundations
of Computer Science (FOCS)
, 2001.
[4] Y. Linde, A. Buzo, and R. M. Gray. An algorithm for vector
quantizer design.
IEEE Trans. Comm.
, 28(1):84–95, 1980.
[5] J. Matousek. On approximate geometric
k
-clustering.
Discrete
& Computational Geometry
, 24:61–84, 2000.
ISIT 2004, Chicago, USA, June 27 – July 2, 2004
,(((