Image de couverture de livre

The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Lederman, Roy R., Silva-Sánchez, David, Chen, Ziling, Mordant, Gilles, Balanov, Amnon, Bendory, Tamir
Format:	Preprint
Publié:	2026
Sujets:	Machine Learning Statistics Theory
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

The generalized method of moments is (almost) statistically efficient in low-SNR Gaussian latent-variable models
par: Balanov, Amnon, et autres
Publié: (2026)

The interplay of signal-to-noise ratio and variance misspecification in Gaussian mixtures
par: Serov, Vladimir, et autres
Publié: (2026)

Einstein from Noise: Statistical Analysis
par: Balanov, Amnon, et autres
Publié: (2024)

Projected multi-reference alignment
par: Balanov, Amnon, et autres
Publié: (2026)

A note on the sample complexity of multi-target detection
par: Balanov, Amnon, et autres
Publié: (2025)

Group-invariant moments under tomographic projections
par: Balanov, Amnon, et autres
Publié: (2026)

Orbit recovery under the rigid motions group
par: Balanov, Amnon, et autres
Publié: (2025)

Confirmation Bias in Gaussian Mixture Models
par: Balanov, Amnon, et autres
Publié: (2024)

The entropic optimal (self-)transport problem: Limit distributions for decreasing regularization with application to score function estimation
par: Mordant, Gilles
Publié: (2024)

An Observation on Lloyd's k-Means Algorithm in High Dimensions
par: Silva-Sánchez, David, et autres
Publié: (2025)

Sample Complexity Analysis of Multi-Target Detection via Markovian and Hard-Core Multi-Reference Alignment
par: Abraham, Kweku, et autres
Publié: (2025)

Structure from Noise: Confirmation Bias in Particle Picking in Structural Biology
par: Balanov, Amnon, et autres
Publié: (2025)

An Ultra-Fast MLE for Low SNR Multi-Reference Alignment
par: Kreymer, Shay, et autres
Publié: (2026)

Expectation-maximization for low-SNR multi-reference alignment
par: Balanov, Amnon, et autres
Publié: (2025)

Quantifying the noise sensitivity of the Wasserstein metric for images
par: Lager, Erik, et autres
Publié: (2025)

Inhomogeneous Submatrix Detection
par: Oren-Loberman, Mor, et autres
Publié: (2026)

Rényi-Induced Information Geometry and Hartigan's Prior Family
par: Kuntz, Rebecca Maria, et autres
Publié: (2025)

Bayesian Perspective for Orientation Determination in Cryo-EM with Application to Structural Heterogeneity Analysis
par: Xu, Sheng, et autres
Publié: (2024)

Extremes in High Dimensions: Methods and Scalable Algorithms
par: Lederer, Johannes, et autres
Publié: (2023)

Manifold Learning with Sparse Regularised Optimal Transport
par: Zhang, Stephen, et autres
Publié: (2023)

Estimation of Algebraic Sets: Extending PCA Beyond Linearity
par: González-Sanz, Alberto, et autres
Publié: (2025)

Learning Curves and Benign Overfitting of Spectral Algorithms in Large Dimensions
par: Lu, Weihao, et autres
Publié: (2026)

Entangled Mean Estimation in High-Dimensions
par: Diakonikolas, Ilias, et autres
Publié: (2025)

An Optimal Linear Fusion Estimation Algorithm of Reduced Dimension for T-Proper Systems with Multiple Packet Dropouts
par: Fernández-Alcalá, Rosa M., et autres
Publié: (2024)

Solving ill-conditioned polynomial equations using score-based priors with application to multi-target detection
par: Beinhorn, Rafi, et autres
Publié: (2025)

Superconsistency of Tests in High Dimensions
par: Kock, Anders Bredahl, et autres
Publié: (2021)

An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise
par: Düngler, Johanna, et autres
Publié: (2025)

Analysis of the rSVDdpd Algorithm: A Robust Singular Value Decomposition Method using Density Power Divergence
par: Roy, Subhrajyoty, et autres
Publié: (2023)

Conformal and kNN Predictive Uncertainty Quantification Algorithms in Metric Spaces
par: Lugosi, Gábor, et autres
Publié: (2025)

Partition-Insensitive Parallel ADMM Algorithm for High-dimensional Linear Models
par: Wu, Xiaofei, et autres
Publié: (2023)

Minimax Optimal Algorithms with Fixed-$k$-Nearest Neighbors
par: Ryu, J. Jon, et autres
Publié: (2022)

Asymptotic Theory of Geometric and Adaptive $k$-Means Clustering
par: Jaffe, Adam Quinn
Publié: (2022)

Mean Estimation from Coarse Data: Characterizations and Efficient Algorithms
par: Kalavasis, Alkis, et autres
Publié: (2026)

Computation of Optimal Type-II Progressing Censoring Scheme Using Genetic Algorithm Approach
par: Roy, Ujjwal, et autres
Publié: (2025)

Adjusted Scores for Discrete Langevin Algorithms
par: Gissler, Armand, et autres
Publié: (2026)

Tight Bounds on the Laplace Approximation Accuracy in High Dimensions
par: Katsevich, Anya
Publié: (2023)

Bayesian Sparse Gaussian Mixture Model in High Dimensions
par: Yao, Dapeng, et autres
Publié: (2022)

Posterior Sampling in High Dimension via Diffusion Processes
par: Montanari, Andrea, et autres
Publié: (2023)

Overflow-Avoiding Memory AMP
par: Huang, Shunqi, et autres
Publié: (2024)

A Sub-Quadratic Time Algorithm for Robust Sparse Mean Estimation
par: Pensia, Ankit
Publié: (2024)