检索结果-内蒙古大学图书馆

Nondegeneracy and weak global convergence of the lloyd algorithm in r^d

SIAM JOURNAL ON NUMERICAL ANALYSIS 2008年第3期46卷 1423-1441页

作者： Emelianenko, Maria Ju, Lili Rand, Alexander George Mason Univ Dept Math Sci Fairfax VA 22030 USA Univ S Carolina Dept Math Columbia SC 29208 USA Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA

The lloyd algorithm originated in the context of optimal quantization and represents a fixed point iteration for computing an optimal quantizer. Reducing average distortion at every step, it constructs a Voronoi partition of the domain and replaces each generator with the centroid of the corresponding Voronoi cell. Optimal quantization is obtained in the case of a centroidal Voronoi tessellation (CVT), which is a special Voronoi tessellation of a domain Omega is an element of R-d having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function rho >= 0, of the corresponding Voronoi cells. The lloyd iteration is currently the most popular and elegant algorithm for computing CVTs and optimal quantizers, but many questions remain about its convergence, especially in d-dimensional spaces (d > 1). In this paper, we prove that any limit point of the lloyd iteration in any dimensional spaces is nondegenerate provided that Omega is a convex and bounded set and. belongs to L-1(Omega) and is positive almost everywhere. This ensures that the fixed point map remains closed and hence the standard theory of descent methods guarantees weak global convergence of the lloyd iteration to the set of nondegenerate fixed point quantizers. While previously only conjectured, the convergence properties of the lloyd iteration are rigorously justified under such minimal regularity assumptions on the density functional. The results presented in this paper go beyond existing convergence theories for CVTs and optimal quantization related algorithms and should be of interest to both the mathematical and engineering communities.

关键词： centroidal Voronoi tessellations quantization lloyd algorithm global convergence

来源：评论

学校读者我要写书评

暂无评论

Convergence of the lloyd algorithm for computing centroidal Voronoi tessellations

引用

SIAM JOURNAL ON NUMERICAL ANALYSIS 2006年第1期44卷 102-119页

作者： Du, Q Emelianenko, M Ju, LL Penn State Univ Dept Math University Pk PA 16802 USA Carnegie Mellon Univ Dept Math Sci Pittsburgh PA 15213 USA Univ S Carolina Dept Math Columbia SC 29208 USA

Centroidal Voronoi tessellations (CVTs) are Voronoi tessellations of a bounded geometric domain such that the generating points of the tessellations are also the centroids (mass centers) of the corresponding Voronoi regions with respect to a given density function. Centroidal Voronoi tessellations may also be defined in more abstract and more general settings. Due to the natural optimization properties enjoyed by CVTs, they have many applications in diverse fields. The lloyd algorithm is one of the most popular iterative schemes for computing the CVTs but its theoretical analysis is far from complete. In this paper, some new analytical results on the local and global convergence of the lloyd algorithm are presented. These results are derived through careful utilization of the optimization properties shared by CVTs. Numerical experiments are also provided to substantiate the theoretical analysis.

关键词： centroidal Voronoi tessellations k-means optimal vector quantizer lloyd algorithm global convergence convergence rate

来源：评论

学校读者我要写书评

暂无评论

A modification of the lloyd algorithm for k-anonymous quantization

引用

INFORMATION SCIENCES 2013年 222卷 185-202页

作者： Rebollo-Monedero, David Forne, Jordi Pallares, Esteve Parra-Arnau, Javier Univ Politecn Cataluna Dept Telemat Engn E-08034 Barcelona Spain

We address the problem of designing quantizers that cluster data while satisfying a k-anonymity requirement. A general data compression perspective is adopted, which considers both discrete and continuous probability distributions, and corresponding constraints on both cell sizes and quantizer index probabilities. Potential applications of this problem extend well beyond the important case of microdata anonymization, to include also optimized task allocation under workload constraints. Our contribution is twofold. First and most importantly, we present a theoretical analysis showing the optimality conditions which probability-constrained quantizers must satisfy, thereby theoretically characterizing optimal k-anonymous aggregation as a special case. As a second contribution, inspired by our theoretical analysis, we propose an alternating optimization algorithm for the design of this type of quantizers. Our algorithm is conceptually motivated by the popular lloyd-Max algorithm for quantization design, originally intended for data compression, also known as the k-means method. Experimental results for synthetic and real data, with mean squared error as a distortion measure, confirm that our method outperforms MDAV, a popular fixed-size microaggregation algorithm for statistical disclosure control. This performance improvement is in terms of data utility, for the exact same k-anonymity constraint, but does come at the expense of higher computational sophistication. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Microdata anonymization k-Anonymity lloyd algorithm k-Means method k-Anonymous quantization

来源：评论

学校读者我要写书评

暂无评论

Candidate of initial value in lloyd algorithm for constructing low-coherence matrix 10

Candidate of initial value in Lloyd algorithm for constructi...

引用

10th International Conference on Intelligent Computation Technology and Automation (ICICTA)

作者： Rong, Rong Fu, Yuli Xiang, Youjun Xu, Junwei South China Univ Technol Sch Elect & Informat Engn Guangzhou 510640 Guangdong Peoples R China

ISBN: (纸本)9781538612309

The problem of constructing matrix with low-coherence is arised in many applications, such as CDMA, compressive sensing (CS), beamforming, etc. Usually the design of low-coherence codebook can be modeled as vector quantization (VQ) problem, and generalized lloyd algorithm is designed to solve it. Since lloyd algorithm is a method of local optimization, its performance is influenced by initial value. In this paper, candidate of initial value of lloyd algorithm is studied. A construction based on finite abelian group which can be used as candidate of initial value will be analyzed. Experimental results prove that using this construction as initial value in lloyd algorithm can improve the performance significantly.

关键词： Beamforming Compressive sensing lloyd algorithm Abelian group Welch Bound

来源：评论

学校读者我要写书评

暂无评论

Modified Vector Quantization for Small-Cell Access Point Placement With Inter-Cell Interference

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2022年第8期21卷 6387-6401页

作者： Gopal, Govind R. Nayebi, Elina Villardi, Gabriel Porto Rao, Bhaskar D. Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA Apple Inc Cupertino CA 95014 USA Univ Calif San Diego Qualcomm Inst Calit2 La Jolla CA 92093 USA Natl Inst Informat & Commun Technol NICT Wireless Network Res Ctr Yokosuka Kanagawa 2390847 Japan

In this paper, we explore the small-cell uplink access point (AP) placement problem in the context of throughput optimality and provide solutions while taking into consideration inter-cell interference (ICI). First, we briefly review the vector quantization (VQ) approach and related single user throughput-optimal formulations for AP placement. Then, we investigate the small-cell case with multiple users and expose the limitations of mean squared error based VQ for solving this problem. While the lloyd algorithm from the VQ approach is found not to strictly solve the small-cell case, based on the tractability and quality of the resulting AP placement, we deem it suitable as a simple and appropriate framework to solve more complicated problems. Accordingly, to minimize ICI and consequently enhance achievable throughput, we design two lloyd-type algorithms, namely the Interference lloyd algorithm and the Inter-AP lloyd algorithm, both of which incorporate ICI in their distortion functions. Simulation results show that both of the proposed algorithms provide superior 95%-likely rate over the traditional lloyd algorithm and the Inter-AP lloyd algorithm yields a significant increase of up to 36.34% in achievable rate over the lloyd algorithm.

关键词： Throughput Signal to noise ratio Interference Antennas Antenna arrays Massive MIMO Fading channels Base station placement beyond 5G lloyd algorithm SINR minimization throughput optimization user cell association

来源：评论

学校读者我要写书评

暂无评论

Vector Quantization Methods for Access Point Placement in Cell-Free Massive MIMO Systems

引用

IEEE TRANSACTIONS ON WIRELESS COMMUNICATIONS 2024年第6期23卷 5425-5440页

作者： Gopal, Govind R. Rao, Bhaskar D. Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA

We examine the problem of uplink cell-free access point (AP) placement in the context of optimal throughput. In this regard, we formulate two main placement problems, namely the sum rate and minimum rate maximization problems, and discuss the challenges associated with solving the underlying optimization problems with the help of some simple scenarios. As a practical solution to the AP placement problem, we suggest a vector quantization (VQ) approach. The suitability of the VQ approach to cell-free AP placement is investigated by examining three VQ-based solutions. First, the standard VQ approach, that is the lloyd algorithm (using the squared error distortion function) is described. Second, the tree-structured VQ (TSVQ), which performs successive partitioning of the distribution space is applied. Third, a probability density function optimized VQ (PDFVQ) procedure is outlined, enabling efficient, low complexity, and scalable placement, and is aimed at a massive distributed multiple-input-multiple-output scenario. While the VQ-based solutions do not explicitly solve the cell-free AP placement problems, numerical experiments show that their sum and minimum rate performances are good enough, and offer a good starting point for gradient-based optimization methods. Among the VQ solutions, PDFVQ, with its distinct advantages, offers a good trade-off between sum and minimum rates.

关键词： Base station placement beyond 5G lloyd algorithm scalability throughput optimization

来源：评论

学校读者我要写书评

暂无评论

GOSSIP COVERAGE CONTROL FOR ROBOTIC NETWORKS: DYNAMICAL SYSTEMS ON THE SPACE OF PARTITIONS

引用

SIAM JOURNAL ON CONTROL AND OPTIMIZATION 2012年第1期50卷 419-447页

作者： Bullo, Francesco Carli, Ruggero Frasca, Paolo Univ Calif Santa Barbara Ctr Control Dynam Syst & Computat Santa Barbara CA 93106 USA Politecn Torino Dipartimento Matemat Turin Italy

Future applications in environmental monitoring, delivery of services, and transportation of goods motivate the study of deployment and partitioning tasks for groups of autonomous mobile agents. These tasks may be achieved by recent coverage algorithms, based upon the classic methods by lloyd. These algorithms, however, rely upon critical requirements on the communication network: information is exchanged synchronously among all agents and long-range communication is sometimes required. This work proposes novel coverage algorithms that require only gossip communication, i.e., asynchronous, pairwise, and possibly unreliable communication. Which robot pair communicates at any given time may be selected deterministically or randomly. A key innovative idea is describing coverage algorithms for robot deployment and environment partitioning as dynamical systems on a space of partitions. In other words, we study the evolution of the regions assigned to each agent rather than the evolution of the agents' positions. The proposed gossip algorithms are shown to converge to centroidal Voronoi partitions under mild technical conditions. Our treatment features a broad variety of results in topology, analysis, and geometry. First, we establish the compactness of a suitable space of partitions with respect to the symmetric difference metric. Second, with respect to this metric, we establish the continuity of various geometric maps, including the Voronoi diagram as a function of its generators, the location of a centroid as a function of a set, and the widely known multicenter function studied in facility location problems. Third, we prove two convergence theorems for dynamical systems on metric spaces described by deterministic and stochastic switches.

关键词： cooperative control multiagent systems gossip communication geometric optimization centroidal Voronoi tessellations lloyd algorithm

来源：评论

学校读者我要写书评

暂无评论

UNIVERSAL L^s-RATE-OPTIMALITY OF L^r-OPTIMAL QUANTIZERS BY DILATATION AND CONTRACTION

引用

ESAIM-PROBABILITY AND STATISTICS 2009年第3期13卷 218-246页

作者： Sagna, Abass Univ Paris 06 Lab Probabilites & Modeles Aleatoires UMR 7599 F-75252 Paris 05 France

We investigate in this paper the properties of some dilatations or contractions of a sequence (alpha(n))(n >= 1) of L-r-optimal quantizers of an R-d-valued random vector X is an element of L-r (P) defined in the probability space (Omega, A, P) with distribution P-X = P. To be precise, we investigate the L-s-quantization rate of sequences alpha(0,mu)(n) = mu + theta(alpha(n) - mu) = {mu + theta(a - mu), a is an element of alpha(n)} when theta is an element of R*(+), mu is an element of R, s is an element of (0, r) or s is an element of (r,+ infinity) and X is an element of L-s(P). We show that for a wide family of distributions, one may always find parameters (theta, mu) such that (alpha(theta,mu)(n))(n >= 1) is L-s-rate-optimal. For the Gaussian and the exponential distributions we show the existence of a couple (theta*, mu*) such that (alpha(theta)*(,mu)*)(n >= 1) also satisfies the so-called L-s-empirical measure theorem. Our conjecture, confirmed by numerical experiments, is that such sequences are asymptotically L-s-optimal. In both cases the sequence (alpha(theta)*(,mu)*)(n >= 1) is incredibly close to L-s-optimality. However we show (see Rem. 5.4) that this last sequence is not L-s-optimal (e.g. when s = 2, r = 1) for the exponential distribution.

关键词： Rate-optimal quantizers empirical measure theorem dilatation lloyd algorithm

来源：评论

学校读者我要写书评

暂无评论

BER criterion and codebook construction for finite-rate precoded spatial multiplexing with linear receivers

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2006年第5期54卷 1653-1665页

作者： Zhou, SL Li, BS Univ Connecticut Dept Elect & Comp Engn Storrs CT 06269 USA

Precoded spatial multiplexing systems with rate-limited feedback have been studied recently based on various precoder selection criteria. Instead of those based on indirect performance indicators, we in this paper propose a new criterion directly based on the exact bit error rate (BER) that is applicable to systems with linear receivers and rectangular/square quadrature-amplitude modulation constellations. The BER criterion outperforms any other alternative in terms of optimizing the BER performance for an uncoded system with linear receivers. We then develop a precoder codebook construction method based on the generalized lloyd algorithm from the vector quantization literature. This construction is not directly based on the BER criterion. Hence, it is suboptimal in the BER sense. However, relative to those currently available, our newfound codebooks improve considerably various minimum distances between any pair of codewords of the codebook. Finally, we analyze the BER-optimal precoder in the asymptotic case with infinite-rate feedback that amounts to perfect channel knowledge at the transmitter. The infinite-rate optimal precoder based on the BER criterion is drastically different from the counterparts with other criteria, and it leads to a benchmark performance for finite-rate precoded spatial multiplexing systems. We observe from numerical results that the BER performance of finite-rate feedback with suboptimal codebooks approaches quickly the benchmark performance of infinite-rate feedback. This suggests that i) the number of feedback bits in practical systems need not be large and ii) the room for performance improvement via further codebook optimization shrinks quickly as the codebook size increases.

关键词： finite-rate feedback lloyd algorithm precoding spatial multiplexing

来源：评论

学校读者我要写书评

暂无评论

AN IMAGE THRESHOLDING METHOD USING A MINIMUM WEIGHTED SQUARED-DISTORTION CRITERION

引用

PATTERN RECOGNITION 1995年第7期28卷 1063-1071页

作者： MORII, F Department of Information and Computer Sciences Faculty of Science Nara Women's University Kita-Uoya Nishimachi Nara 630 Japan

We present a new thresholding method for image segmentation in which thresholds are selected on the basis of a minimum weighted squared-distortion criterion. An iterative algorithm, which is named a supervised lloyd algorithm, to satisfy the criterion is derived. In order to achieve reliable segmentation, we discuss how the weight coefficients of the criterion must be tuned by a supervisor. Two supervised approaches based on a probabilistic histogram model and typical images in processing images are treated in detail.

关键词： IMAGE SEGMENTATION THRESHOLDING SQUARED DISTORTION CRITERION SUPERVISION lloyd algorithm CLASSIFICATION

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：