Efficiently estimates mean in contaminated Gaussian data with near-optimal sample complexity.
problem Robust mean estimation in the presence of mean-shift contamination.
method First computationally efficient algorithm with near-optimal sample complexity and polynomial-time running.
result Approximates the target mean to any desired accuracy with constant fraction of outliers tolerated.
A method to remove mean-shift noise from PCA using knockoffs.
problem High sensitivity of PCA to mean-shift contamination in high-dimensional data.
method Introducing knockoff mean-shift perturbation to separate and remove mean-shift components from PCA.
result The mean-shift spikes are spectrally separable from stable eigenvalues, allowing for robust PCA.
The mean-shift algorithm is a popular algorithm in computer vision and image processing. It can also be cast as a minimum gamma-divergence estimation. In this paper we focus on the "blurring" mean shift algorithm, which is one version of the mean-shift process that successively blurs the dataset. The analysis of the bl…
In this paper, we study how the mean shift algorithm can be used to denoise a dataset. We introduce a new framework to analyze the mean shift algorithm as a denoising approach by viewing the algorithm as an operator on a distribution function. We investigate how the mean shift algorithm changes the distribution and sho…
A feature-weighted mean shift algorithm improves clustering in high-dimensional data.
problem Clustering high-dimensional data with traditional mean shift algorithms.
method Feature-weighted mean shift algorithm.
result The algorithm outperforms conventional mean shift and preserves computational simplicity.
Epanechnikov Mean Shift is a simple yet empirically very effective algorithm for clustering. It localizes the centroids of data clusters via estimating modes of the probability distribution that generates the data points, using the `optimal' Epanechnikov kernel density estimator. However, since the procedure involves n…
Interpolates mean shift and spectral clustering on graphs.
problem Data clustering algorithms.
method Fokker-Planck equations on data graphs.
result New theoretical insights on diffusion maps and mean shift dynamics.
A natural way to characterize the cluster structure of a dataset is by finding regions containing a high density of data. This can be done in a nonparametric way with a kernel density estimate, whose modes and hence clusters can be found using mean-shift algorithms. We describe the theory and practice behind clustering…
Develops an MS-inspired algorithm for regression mode finding and space partitioning.
problem Finding local modes of regression functions and partitioning input space.
method Mean-shift-inspired algorithm for iterative gradient ascent.
result Proves convergence and rates of convergence for estimated local modes.
Study guarantees convergence of mean shift mode estimation.
problem Ensuring reliable mode estimation in KDE using mean shift.
method Utilizes Łojasiewicz inequality to prove convergence rate.
result Extends convergence guarantees to biweight kernel.
We introduce the functional mean-shift algorithm, an iterative algorithm for estimating the local modes of a surrogate density from functional data. We show that the algorithm can be used for cluster analysis of functional data. We propose a test based on the bootstrap for the significance of the estimated local modes …
Mean shift clustering finds the modes of the data probability density by identifying the zero points of the density gradient. Since it does not require to fix the number of clusters in advance, the mean shift has been a popular clustering algorithm in various application fields. A typical implementation of the mean shi…
The paper studies kernel smoothing and mean shift for directional data, deriving convergence rates and mode estimation.
problem Statistical and computational problems of kernel smoothing for directional data.
method Generalization of mean shift to directional data, derivation of convergence rates, and investigation of mode estimation.
result Statistical convergence rates of directional KDE and its derivatives, ascending property of directional mean shift, and mode estimation.
Robust data fusion via subsampling improves model performance for rare data types.
problem Challenges in integrating large, contaminated external data with limited target data.
method Subsampling strategies to reduce biases and minimize variances, combined with error bounds analysis.
result Proposed methods enhance transfer learning performance, especially for rare data types.
Paper shows DMS as an EM algorithm with improved convergence.
problem Improving the convergence of DMS algorithm.
method Shows DMS as a generalized EM algorithm and provides new proofs.
result Demonstrates global convergence and linear convergence of DMS.
New methods for Bayesian inference using mean shift particle systems.
problem Approximating expectations with unnormalized densities in Bayesian inference.
method Mean shift interacting particle systems that minimize maximum mean discrepancy (MMD).
result Mean shift interacting particle systems converge quickly and capture complex distributions.
HypeGBMS clusters data in hyperbolic space, overcoming Euclidean limitations.
problem Clustering in hierarchical or tree-like datasets in curved spaces.
method Hyperbolic Gaussian Blurring Mean Shift with Möbius-weighted means.
result HypeGBMS effectively captures latent hierarchies in non-Euclidean data.
We explore the performance of several automatic bandwidth selectors, originally designed for density gradient estimation, as data-based procedures for nonparametric, modal clustering. The key tool to obtain a clustering from density gradient estimators is the mean shift algorithm, which allows to obtain a partition not…
The mean shift algorithm is a popular way to find modes of some probability density functions taking a specific kernel-based shape, used for clustering or visual tracking. Since its introduction, it underwent several practical improvements and generalizations, as well as deep theoretical analysis mainly focused on its …
New algorithm improves clustering and quantization using MMD.
problem Approximating probability distributions with weighted mixtures of Dirac measures.
method Gradient flow, mean shift, and MMD-optimal quantization.
result MSIP algorithm is more robust than state-of-the-art methods.
Estimates modes and ridges in mixed Euclidean and directional spaces.
problem Estimating local modes and density ridges in product spaces combining Euclidean and directional metrics.
method Extends mean shift algorithm to product spaces, addressing challenges in generalization.
result Established convergence of the proposed methods and demonstrated effectiveness on real-world datasets.
Paper proves linear convergence of SCMS algorithm for directional data.
problem Identifying density ridges in directional data.
method Generalized SCMS algorithm to directional data, derived from SCGA with adaptive step size.
result Linear convergence of the proposed directional SCMS algorithm.
The paper develops methods to accurately locate change points in high-dimensional mean shift models.
problem Locating change points in high-dimensional mean shift models.
method Locally refitted least squares estimator, component-wise and simultaneous rates of estimation.
result Asymptotic validity of component-wise and simultaneous confidence intervals for change point parameters.
Unified view of clustering algorithms presented.
problem Presenting a unified view of clustering algorithms.
method Identifying relationships between five clustering algorithms.
result A novel interpretation of DBSCAN as a climbing procedure.
In this paper we present a new method for motion tracking of tumors in liver ultrasound image sequences. Our algorithm has two main steps. In the first step, we apply mean shift algorithm with multiple features to estimate the center of the target in each frame. Target in the first frame is defined using an ellipse. Ed…
In this paper we target the class of modal clustering methods where clusters are defined in terms of the local modes of the probability density function which generates the data. The most well-known modal clustering method is the k-means clustering. Mean Shift clustering is a generalization of the k-means clustering wh…
Bayesian inference for inverse problems using mean-shift interacting particles
problem Bayesian inference for inverse problems
method Amortized mean-shift interacting particles
result Improves accuracy of Bayesian inference by reducing the number of samples needed
Paper proves MS convergence for radially symmetric kernels with large bandwidths.
problem Proving convergence of mean shift algorithm with radially symmetric kernels.
method Analyzes convergence of mean shift algorithm with radially symmetric, positive definite kernels.
result Guaranteed convergence for sufficiently large bandwidth in any dimension.
Two new algorithms recover ridge lines from point clouds with convergence guarantees.
problem Extracting filamentary structure from point clouds.
method Proposes two novel algorithms with convergence guarantees.
result The algorithms can asymptotically recover the full ridge set.
This paper introduces a novel clustering algorithm for heteroscedastic Gaussian data without needing to know the number of clusters.
problem Clustering heteroscedastic Gaussian data without prior knowledge of the number of clusters.
method Introduces a novel cost function and fixed-point analysis to estimate centroids, introduces Wald kernel for measurement plausibility, and derives CENTRE-X algorithm.
result CENTRE-X algorithm can estimate centroids without prior knowledge of the number of clusters and performs comparably to standard algorithms K-means and Mean-Shift.
This work addresses the problem of segmentation in time series data with respect to a statistical parameter of interest in Bayesian models. It is common to assume that the parameters are distinct within each segment. As such, many Bayesian change point detection models do not exploit the segment parameter patterns, whi…
In addition to finding meaningful clusters, centroid-based clustering algorithms such as K-means or mean-shift should ideally find centroids that are valid patterns in the input space, representative of data in their cluster. This is challenging with data having a nonconvex or manifold structure, as with images or text…
A contamination in a 3-manifold is an object interpolating between the contact structure and the lamination. Contaminations seem to provide a link between 3-dimensional contact geometry and the classical topology of 3-manifolds, as described in a separate paper. In this paper we deal with contaminations carried by bran…
A robust loss for anomaly mitigation and unsupervised contamination classification
problem Detecting and mitigating contamination in supervised and unsupervised settings
method Neural Bayesian Anomaly Mitigation (NBAM)
result Recovering the structure of contamination and identifying label-flip pairs
Many clustering algorithms exist that estimate a cluster centroid, such as K-means, K-medoids or mean-shift, but no algorithm seems to exist that clusters data by returning exactly K meaningful modes. We propose a natural definition of a K-modes objective function by combining the notions of density and cluster assignm…
Study minimax robustness in statistical estimation under Wasserstein contamination.
problem Adversarial perturbations in statistical data.
method Developed minimax theory for ℓqr losses under Wasserstein-r contaminations. result Exact minimax risk identified for joint contaminations in location estimation and prediction in linear regression.
Study shows robust method for estimating density ratios even with heavy contamination.
problem Estimating density ratios in the presence of heavy contamination.
method Weighted density ratio estimation (DRE) with doubly strong robustness.
result Weighted DRE achieves sparse consistency under heavy contamination.
Generative models can still learn from contaminated data, but with limitations.
problem How much contamination can generative models tolerate?
method Characterized robustness under contaminated enumerations, proving generation is achievable for all countable collections if contamination fraction converges to zero.
result Generation under contamination is achievable for all countable collections if contamination fraction converges to zero, but dense generation is strictly less robust.
Algorithm identifies Pareto set in bandits with contaminated feedback.
problem Identifying Pareto set in multi-objective bandits with adversarial contamination.
method Sample median-based multi-objective adaptive elimination algorithm.
result Sample complexity bound that depends on contamination probability.
New algorithm resists contamination in high-dimensional regression with optimal performance.
problem Adversarial and measurement errors in high-dimensional data.
method Adversarial Contamination-resistant Iterative Hard Thresholding (AC-IHT) algorithm.
result Achieves minimax near-optimal estimation and signal-adaptive support recovery.
Motivated by applications of bandit algorithms in education, we consider a stochastic multi-armed bandit problem with ε-contaminated rewards. We allow an adversary to give arbitrary unbounded contaminated rewards with full knowledge of the past and future. We impose the constraint that for each time t the…
Paper introduces RAS for robust MTL with contamination.
problem Representation-based multi-task learning struggles with contamination.
method Robust and Adaptive Spectral (RAS) method.
result RAS prevents negative transfer and performs well with up to 80% contamination.
Trimming helps in conformal prediction when it separates anomaly scores.
problem Effectiveness of trimming in conformal prediction under contamination.
method Analyse fixed-threshold trimming as a replacement of the contaminated calibration law with a retained law.
result Trimming helps when it separates anomaly scores, reducing clean-target coverage to a one-dimensional score-CDF transfer problem.
Improved robust regression with clean covariates achieves better rates than Huber's model.
problem Robust regression under adaptive contamination of responses with clean covariates.
method Exploiting clean covariates to construct an estimator achieving better rates than Huber's model.
result Improved estimation rate even with constant contamination, achieving consistency.
Bayesian method estimates contamination factor for unsupervised anomaly detection.
problem No good methods for estimating contamination factor in unsupervised anomaly detection.
method Bayesian approach using mixture formulation of anomaly detector outputs.
result Estimated contamination factor distribution is well-calibrated and improves anomaly detection performance.
New test ensures quality of shared data in machine learning.
problem Ensuring quality of external data in machine learning tasks.
method Distribution-free two-sample testing procedures grounded in conformal outlier detection.
result Identifies valuable external data agents for model personalization.
New method trims network data to resist adversarial contamination.
problem Adversarial contamination in network data affects statistical and algorithmic performance.
method Proposes a new trimming method operating in model space to address both block and white noise contamination.
result Demonstrates superior performance in simulations compared to direct trimming.
New algorithm reduces contamination in supervised learning.
problem Learning with contamination in supervised learning.
method Iterative polynomial filtering.
result Efficient learning of functions with contamination.