We endeavour to estimate numerous multi-dimensional means of various probability distributions on a common space based on independent samples. Our approach involves forming estimators through convex combinations of empirical means derived from these samples. We introduce two strategies to find appropriate data-dependent convex combination weights: a first one employing a testing procedure to identify neighbouring means with low variance, which results in a closed-form plug-in formula for the weights, and a second one determining weights via minimization of an upper confidence bound on the quadratic risk. Through theoretical analysis, we evaluate the improvement in quadratic risk offered by our methods compared to the empirical means. Our analysis focuses on a dimensional asymptotics perspective, showing that our methods asymptotically approach an oracle (minimax) improvement as the effective dimension of the data increases. We demonstrate the efficacy of our methods in estimating multiple kernel mean embeddings through experiments on both simulated and real-world datasets.
We study model-order selection and component-mean estimation for multidimensional Gaussian mixture models with a known common covariance matrix. Using empirical characteristic-function measurements, we construct Fourier covariance matrices whose population counterparts have rank equal to the number of mixture components. We establish a minimax lower bound showing that distinguishing a separated k-component mixture from the class of (k−1)-component mixtures requires Ω(Δ−(4k−4)) samples. We then develop an oracle spectral-thresholding estimator with a sufficient sample size of order Δ−(8k−8) for fixed k, together with a practical singular-value-ratio estimator. Given the model order, we estimate the component means by score-initialized gradient descent on a MUSIC-type projection objective. Under an explicit sample-size condition, a qualifying sample initialization lies in a certified attraction region with high probability, after which the iterates converge linearly. For fixed positive component separation, the resulting mean estimates achieve the parametric rate Op(n−1/2). Numerical experiments demonstrate competitive accuracy and lower computational cost than expectation-maximization across a range of multidimensional settings.
We study query time bounds for the fundamental problem of estimating the kernel mean ∣X∣1∑x∈Xk(x,y) of a query y in a finite dataset X⊂Rd up to a prescribed additive error ε. The best known bounds for the Gaussian kernel are O(d/ε2), O(d+1/ε4), and O(d+Δ2/ε2), where Δ is the diameter of a region containing the points. We prove the new bound O~(d+εΔ2+1/ε3), which improves over the previous ones in regimes with small error ε and intermediate diameter Δ. At the center of our proof is a new fast spherical embedding theorem in the sense introduced by Bartal, Recht and Schulman (2011), which limits the embedded data diameter while preserving local Euclidean distances and avoiding ``distance collapse'' at larger scales. This fast embedding theorem may be of independent interest.
Kernel spectral clustering with a single bandwidth can be inadequate for data exhibiting multiple characteristic pairwise-distance scales, a problem particularly prevalent in the high-dimensional regime. We address this issue through a multi-kernel formulation that aggregates kernels with different bandwidths. The bandwidths are selected as prescribed empirical quantiles of the pairwise squared distances, thereby capturing the relevant distance scales without requiring prior population-scale information. We develop a rigorous theoretical analysis of the resulting method under a general high-dimensional, multi-scale mixture model with heterogeneous cluster centers and covariance geometries. We construct a blockwise constant, low-rank informative approximation to the empirical multi-kernel matrix and establish row-wise ℓ2,∞ perturbation bounds for its leading spectral components, as well as for the associated normalized Laplacian matrix. These bounds yield observation-level control of the spectral embedding, which is more informative than conventional global eigenspace perturbation estimates. Under suitable eigen-gap and cluster-separation conditions, we show that approximate K-means applied to the multi-kernel spectral embedding achieves exact recovery with high probability.