Skip to content
DraconiticResearch
Search Sources API
190,335 studies31 sourcesUpdated 3 min ago
PreprintarXiv licencearXiv

Stochastic complexity of vectors containing cluster structure

  • Daniel Nicorici
  • Olli Yli-Harja
  • Jaakko Astola
Open at sourcePDFDOICite

Abstract

This paper studies the problem of computing the stochastic probability (shortest code length) of the encoded vectors containing cluster structure using Normalized Maximum Likelihood (NML) model. This is of great theoretical and practical importance in data clustering based on Minimum Description Length (MDL) principle, such as for estimating the best number of clusters and best cluster structure for the data. Straightforward computation of the shortest code length of the vector containing cluster structure based on the NML model requires polynomial time with respect to the size of the vector and number of clusters. We show that this is a tractable problem by introducing a recursion formula for the efficient computation of normalizing constant from the NML model. The time complexity of the new formula is linear opposed to previous polynomial time with respect to the size of the vector and number of clusters.

Related

  1. Complexity of flows with interactions and stochastic analysis
    Yifan Shi
    arXivPreprintarXiv licenceFull textProbabilityarXiv
  2. On the complexity of two-stage stochastic linear optimization with small second stage
    Christoph Buchheim
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  3. On the Complexity of Finding Stationary Points in Stochastic (L0, L1)-Smooth Nonconvex Optimization
    Yanpeng Liang, Luo Luo
    arXivPreprintCC BY 4.0Full textOptimisation & controlarXiv
  4. Lower Bounds on Inference Complexity for Polyak-Ruppert Averaged Stochastic Gradient Descent
    Denis Belomestny, Alexey Naumov, Sergey Samsonov
    arXivPreprintarXiv licenceFull textOptimisation & controlStatisticsarXiv
  5. Tight Sampling Complexity with Stochastic Gradient Oracles in Fixed Dimensions
    Weiming Ou, Xiao Wang
    arXivPreprintCC BY 4.0Full textProbabilityStatisticsarXiv

Cite

BibTeXRIS
BibTeX
@misc{nicorici2026stochastic,
  title = {{Stochastic complexity of vectors containing cluster structure}},
  author = {Daniel Nicorici and Olli Yli-Harja and Jaakko Astola},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.00084},
  eprint = {2609.00084},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.00084},
}
RIS
TY  - UNPB
TI  - Stochastic complexity of vectors containing cluster structure
AU  - Daniel Nicorici
AU  - Olli Yli-Harja
AU  - Jaakko Astola
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2609.00084
UR  - https://arxiv.org/abs/2609.00084
AB  - This paper studies the problem of computing the stochastic probability (shortest code length) of the encoded vectors containing cluster structure using Normalized Maximum Likelihood (NML) model. This is of great theoretical and practical importance in data clustering based on Minimum Description Length (MDL) principle, such as for estimating the best number of clusters and best cluster structure for the data. Straightforward computation of the shortest code length of the vector containing cluster structure based on the NML model requires polynomial time with respect to the size of the vector and number of clusters. We show that this is a tractable problem by introducing a recursion formula for the efficient computation of normalizing constant from the NML model. The time complexity of the new formula is linear opposed to previous polynomial time with respect to the size of the vector and number of clusters.
ER  -