On convergence of Lloyd's method I
IEEE Transactions on Information TheoryPublished 1 January 1992
Xiaolin Wu
Citations29
SJR quartileQ1
SJR score1.46
SNIP1.76
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This correspondence proves that Lloyd's method I converges for a large class of error measures, if the density function is continuous, positive, and defined on a finite interval.
Abstract
Although Lloyd's method I for optimal quantization was proposed more than thirty years ago and has been frequently referred to in the literature, its convergence has so far not been shown. This correspondence proves that Lloyd's method I converges for a large class of error measures, if the density function is continuous, positive, and defined on a finite interval. The proof is done by modeling the behavior of a continuous optimization algorithm by a finite state machine.>
Keywords
Computer Science
IEEE Transactions on Information TheoryLeast squares quantization in PCM
15,578 Citations1982Sheelagh Lloyd
The corresponding result for any finite number of quanta is derived; that is, necessary conditions are found that the quanta and associated quantization intervals of an optimum finite quantization scheme must satisfy.
IEEE Transactions on CommunicationsAn Algorithm for Vector Quantizer Design
7,183 Citations1980Y. Linde, A. Buzo +1 more
An efficient and intuitive algorithm is presented for the design of vector quantizers based either on a known probabilistic model or on a long training sequence of data.
IEEE Transactions on Information TheoryQuantizing for minimum distortion
2,064 Citations1960J. Max
This paper discusses the problem of the minimization of the distortion of a signal by a quantizer when the number of output levels of the quantizer is fixed and an algorithm is developed to simplify their numerical solution.
IEEE Transactions on Pattern Analysis and Machine IntelligenceK-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality
1,194 Citations1984Shokri Z. Selim, Mohamed A. Ismail
It is shown that under certain conditions the K-means algorithm may fail to converge to a local minimum, and that it converges under differentiability conditions to a Kuhn-Tucker point.
IEEE Transactions on Information TheoryGlobal convergence and empirical consistency of the generalized Lloyd algorithm
143 Citations1986Michael J. Sabin, Robert M. Gray
The generalized Lloyd algorithm for vector quantizer design is analyzed as a descent algorithm for nonlinear programming and a well-known convergence theorem is applied to show that iterative applications of the algorithm produce a sequence of quantizers that approaches the set of fixed-point quantizers.
Information and ControlLocally optimal block quantizer design
141 Citations1980Robert M. Gray, John C. Kieffer +1 more
Several properties are developed for a recently proposed algorithm for the design of block quantizers based either on a probabilistic source model or on a long training sequence of data.
IEEE Transactions on Information TheorySufficient conditions for uniqueness of a locally optimal quantizer for a class of convex error weighting functions
130 Citations1982A. Trushkin
The simple condition of concavity of In p(x) is sufficient for uniqueness of a locally optimal quantizer being a stationary point of the quantization distortion measure E[f(x,\eta)].
Least Squares Quantization in PCM
87 Citations1982S. P. Lloyd
IEEE Transactions on Information TheoryUniqueness of locally optimal quantizer for log-concave density and convex error weighting function
80 Citations1983John C. Kieffer
It is shown that if X has a log-concave density, then there exists a unique locally optimal quantizer Q and Lloyd's Method I may be used to find Q \ast.
IEEE Transactions on Information TheoryExponential rate of convergence for Lloyd's method I
70 Citations1982John C. Kieffer
For a random variable with finite second moment and log-concave density, a unique quantizer exists which produces the minimum expected encoding error, using squared-error distortion, and it is shown that the convergence takes place exponentially fast if the logarithm of the density is not piecewise affine.
SIAM Journal on Applied MathematicsConvergence of Vector Quantizers with Applications to Optimal Quantization
57 Citations1984Efren F. Abaya, G.L. Wise
Sufficient conditions are given to guarantee the convergence for both scalar and vector quantizers with a general class of distortion measures and the convergence of a proposed algorithm for constructing optimal quantizers is shown.
Bell System Technical JournalOptimum Quantizer Design Using a Fixed-Point Algorithm
37 Citations1976Arun N. Netravali, Romesh Saigal
A fixed-point algorithm has been used to obtain the parameters (i.e., decision and representative levels) of an “optimum” quantizer that minimizes a quite general distortion measure, subject to an entropy constraint on its output.
IEEE Transactions on Information TheoryOptimal bi-level quantization and its application to multilevel quantization
7 Citations1991Xiaolin Wu
A special form of optimal quantization is studied, a fixed-point method is embedded in a search scheme to find all the locally optimal bilevel quantizers, resulting in an algorithm for computing the globally optimal bILEvel quantizer.