Kolmogorov Complexity of Spherical Vector Quantizers

被引：0

作者：

Ilic, Velimir M. ^{[1
]}

Peric, Zoran H. ^{[2
]}

机构：

[1] Accordia Grp, Ucitelj Tasina 38, Nish 18000, Serbia

[2] Fac Elect Engn, Nish 18000, Serbia

来源：

NEUREL 2008: NINTH SYMPOSIUM ON NEURAL NETWORK APPLICATIONS IN ELECTRICAL ENGINEERING, PROCEEDINGS | 2008年

关键词：

Kolmogorov complexity; vector quantizer; spherical quantizer; Turing machine;

D O I：

暂无

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

In this paper, we investigate memory complexity of spherical vector quantizer from Kolmogorov's perspective. The method for expressing the quantizer as binary string is proposed and minimal description length of the string is considered as Kolmogorov complexity of the quantizer. The Kolmogorov complexity is compared to memory requirements of two main algorithms for spherical vector quantizer design: uniform spherical quantizer and generalized Lloyd-Max's algorithm. It is proven that first of them has the minimal memory requirements needed for spherical quantizer realization, while the other upper bounds the theoretical minimal description length of the quantizer.

引用

页码：45 / +

页数：2

共 14 条

[1]

COVER T, 1991, ELEMENTS INFORM THEO, P145

[2] ON THE STRUCTURE OF VECTOR QUANTIZERS [J].

GERSHO, A .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1982, 28 (02) :157-166

[3]

GERSHO A, 1992, VECTOR QUANTIZATION, P408

[4]

Huang J., 1963, IEEE T COMMUN SYST, V11, P289, DOI 10.1109/TCOM.1963.1088759

[5] PIECEWISE UNIFORM VECTOR QUANTIZERS [J].

KUHLMANN, F ;

BUCKLEW, JA .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1988, 34 (05) :1259-1263

[6] ALGORITHM FOR VECTOR QUANTIZER DESIGN [J].

LINDE, Y ;

BUZO, A ;

GRAY, RM .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1980, 28 (01) :84-95

[7] HIGH-RESOLUTION QUANTIZATION THEORY AND THE VECTOR QUANTIZER ADVANTAGE [J].

LOOKABAUGH, TD ;

GRAY, RM .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1989, 35 (05) :1020-1033

[8] IMAGE-CODING USING VECTOR QUANTIZATION - A REVIEW [J].

NASRABADI, NM ;

KING, RA .

IEEE TRANSACTIONS ON COMMUNICATIONS, 1988, 36 (08) :957-971

[9] Structured audio, Kolmogorov complexity, and generalized audio coding [J].

Scheirer, ED .

IEEE TRANSACTIONS ON SPEECH AND AUDIO PROCESSING, 2001, 9 (08) :914-931

[10]

SUBBARAMU S, 1998, B EUROPEAN ASS THEOR, V69, P150

← 1 2 →