The EM Perspective of Directional Mean Shift Algorithm

• URL: http://arxiv.org/abs/2101.10058v1
• Date: Mon, 25 Jan 2021 13:17:12 GMT
• Title: The EM Perspective of Directional Mean Shift Algorithm
• Authors: Yikun Zhang, Yen-Chi Chen
• Abstract summary: The directional mean shift (DMS) algorithm is a nonparametric method for pursuing local modes of densities defined by kernel density estimators on the unit hypersphere. We show that any DMS can be viewed as a generalized Expectation-Maximization (EM) algorithm.
• Score: 3.60425753550939
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The directional mean shift (DMS) algorithm is a nonparametric method for pursuing local modes of densities defined by kernel density estimators on the unit hypersphere. In this paper, we show that any DMS iteration can be viewed as a generalized Expectation-Maximization (EM) algorithm; in particular, when the von Mises kernel is applied, it becomes an exact EM algorithm. Under the (generalized) EM framework, we provide a new proof for the ascending property of density estimates and demonstrate the global convergence of directional mean shift sequences. Finally, we give a new insight into the linear convergence of the DMS algorithm.

Related papers

• Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm [80.94861441583275]
  We investigate the complexity of the generalization bound of the decentralized gradient descent (D-SGDA) algorithm. Our results analyze the impact of different top factors on the generalization of D-SGDA. We also balance it with the generalization to obtain the optimal convex-concave setting.
  arXiv  Detail & Related papers  (2023-10-31T11:27:01Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Low-Discrepancy Points via Energetic Variational Inference [5.936959130012709]
  We propose a deterministic variational inference approach and generate low-discrepancy points by minimizing the kernel discrepancy. We name the resulting algorithm EVI-MMD and demonstrate it through examples in which the target distribution is fully specified. Its performances are satisfactory compared to alternative methods in the applications of distribution approximation, numerical integration, and generative learning.
  arXiv  Detail & Related papers  (2021-11-21T03:09:07Z)
• Improving Metric Dimensionality Reduction with Distributed Topology [68.8204255655161]
  DIPOLE is a dimensionality-reduction post-processing step that corrects an initial embedding by minimizing a loss functional with both a local, metric term and a global, topological term. We observe that DIPOLE outperforms popular methods like UMAP, t-SNE, and Isomap on a number of popular datasets.
  arXiv  Detail & Related papers  (2021-06-14T17:19:44Z)
• Linear Convergence of the Subspace Constrained Mean Shift Algorithm: From Euclidean to Directional Data [3.60425753550939]
  We argue that the SCMS algorithm is a special variant of a subspace constrained gradient ascent algorithm with an adaptive step size. We prove the linear convergence of our proposed directional SCMS algorithm.
  arXiv  Detail & Related papers  (2021-04-29T01:46:35Z)
• Space Partitioning and Regression Mode Seeking via a Mean-Shift-Inspired Algorithm [5.990174495635326]
  Mean shift (MS) algorithm is a nonparametric method used to cluster sample points and find the local modes of kernel density estimates. We develop an algorithm to estimate the modes of regression functions and partition the sample points in the input space.
  arXiv  Detail & Related papers  (2021-04-20T16:35:17Z)
• Quantum Algorithm for DOA Estimation in Hybrid Massive MIMO [1.7404865362620803]
  Direction of arrival (DOA) estimation in array signal processing is an important research area. In this article, we present a quantum algorithm for MUSIC-based DOA estimation. Our algorithm can achieve an exponential speedup on some parameters and a speedup on others under mild conditions.
  arXiv  Detail & Related papers  (2021-02-08T02:15:07Z)
• Sampling in Combinatorial Spaces with SurVAE Flow Augmented MCMC [83.48593305367523]
  Hybrid Monte Carlo is a powerful Markov Chain Monte Carlo method for sampling from complex continuous distributions. We introduce a new approach based on augmenting Monte Carlo methods with SurVAE Flows to sample from discrete distributions. We demonstrate the efficacy of our algorithm on a range of examples from statistics, computational physics and machine learning, and observe improvements compared to alternative algorithms.
  arXiv  Detail & Related papers  (2021-02-04T02:21:08Z)
• Kernel Smoothing, Mean Shift, and Their Learning Theory with Directional Data [2.8935588665357077]
  This paper studies both statistical and computational problems of kernel smoothing for directional data. We generalize the classical mean shift algorithm to directional data, which allows us to identify local modes of the directional kernel density estimator (KDE)
  arXiv  Detail & Related papers  (2020-10-23T01:53:47Z)
• A Dynamical Systems Approach for Convergence of the Bayesian EM Algorithm [59.99439951055238]
  We show how (discrete-time) Lyapunov stability theory can serve as a powerful tool to aid, or even lead, in the analysis (and potential design) of optimization algorithms that are not necessarily gradient-based. The particular ML problem that this paper focuses on is that of parameter estimation in an incomplete-data Bayesian framework via the popular optimization algorithm known as maximum a posteriori expectation-maximization (MAP-EM) We show that fast convergence (linear or quadratic) is achieved, which could have been difficult to unveil without our adopted S&C approach.
  arXiv  Detail & Related papers  (2020-06-23T01:34:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.