The Library
Convergence of the k-means minimization problem using Γ-convergence
Tools
Thorpe, Matthew, Theil, Florian, Johansen, Adam M. and Cade, Neil (2015) Convergence of the k-means minimization problem using Γ-convergence. SIAM Journal on Applied Mathematics, 75 (6). pp. 2444-2474. doi:10.1137/140974365 ISSN 0036-1399.
An open access version can be found in:
Official URL: http://dx.doi.org/10.1137/140974365
Abstract
The $k$-means method is an iterative clustering algorithm which associates each observation with one of $k$ clusters. It traditionally employs cluster centers in the same space as the observed data. By relaxing this requirement, it is possible to apply the $k$-means method to infinite dimensional problems, for example, multiple target tracking and smoothing problems in the presence of unknown data association. Via a $\Gamma$-convergence argument, the associated optimization problem is shown to converge in the sense that both the $k$-means minimum and minimizers converge in the large data limit to quantities which depend upon the observed data only through its distribution. The theory is supplemented with two examples to demonstrate the range of problems now accessible by the $k$-means method. The first example combines a nonparametric smoothing problem with unknown data association. The second addresses tracking using sparse data from a network of passive sensors.
Item Type: | Journal Article | ||||||||
---|---|---|---|---|---|---|---|---|---|
Alternative Title: | |||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Statistics | ||||||||
Journal or Publication Title: | SIAM Journal on Applied Mathematics | ||||||||
Publisher: | Society for Industrial and Applied Mathematics | ||||||||
ISSN: | 0036-1399 | ||||||||
Official Date: | 12 November 2015 | ||||||||
Dates: |
|
||||||||
Volume: | 75 | ||||||||
Number: | 6 | ||||||||
Page Range: | pp. 2444-2474 | ||||||||
DOI: | 10.1137/140974365 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |