اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFast computation of Tukey trimmed regions and median in dimension $p>2$
391
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given data in $mathbb{R}^{p}$, a Tukey $kappa$-trimmed region is the set of all points that have at least Tukey depth $kappa$ w.r.t. the data. As they are visual, affine equivariant and robust, Tukey regions are useful tools in nonparametric multivariate analysis. While these regions are easily defined and interpreted, their practical use in applications has been impeded so far by the lack of efficient computational procedures in dimension $p > 2$. We construct two novel algorithms to compute a Tukey $kappa$-trimmed region, a na{i}ve one and a more sophisticated one that is much faster than known algorithms. Further, a strict bound on the number of facets of a Tukey region is derived. In a large simulation study the novel fast algorithm is compared with the na{i}ve one, which is slower and by construction exact, yielding in every case the same correct results. Finally, the approach is extended to an algorithm that calculates the innermost Tukey region and its barycenter, the Tukey median.
قيم البحث
اقرأ أيضاً
Let $V$ be a finite set of indices, and let $B_i$, $i=1,ldots,m$, be subsets of $V$ such that $V=bigcup_{i=1}^{m}B_i$. Let $X_i$, $iin V$, be independent random variables, and let $X_{B_i}=(X_j)_{jin B_i}$. In this paper, we propose a recursive compu
tation method to calculate the conditional expectation $Ebigl[prod_{i=1}^mchi_i(X_{B_i}) ,|, Nbigr]$ with $N=sum_{iin V}X_i$ given, where $chi_i$ is an arbitrary function. Our method is based on the recursive summation/integration technique using the Markov property in statistics. To extract the Markov property, we define an undirected graph whose cliques are $B_j$, and obtain its chordal extension, from which we present the expressions of the recursive formula. This methodology works for a class of distributions including the Poisson distribution (that is, the conditional distribution is the multinomial). This problem is motivated from the evaluation of the multiplicity-adjusted $p$-value of scan statistics in spatial epidemiology. As an illustration of the approach, we present the real data analyses to detect temporal and spatial clustering.
The Oja median is one of several extensions of the univariate median to the multivariate case. It has many nice properties, but is computationally demanding. In this paper, we first review the properties of the Oja median and compare it to other mult
ivariate medians. Afterwards we discuss four algorithms to compute the Oja median, which are implemented in our R-package OjaNP. Besides these algorithms, the package contains also functions to compute Oja signs, Oja signed ranks, Oja ranks, and the related scatter concepts. To illustrate their use, the corresponding multivariate one- and $C$-sample location tests are implemented.
We present the 2-point function from Fast and Accurate Spherical Bessel Transformation (2-FAST) algorithm for a fast and accurate computation of integrals involving one or two spherical Bessel functions. These types of integrals occur when projecting
the galaxy power spectrum $P(k)$ onto the configuration space, $xi_ell^ u(r)$, or spherical harmonic space, $C_ell(chi,chi)$. First, we employ the FFTlog transformation of the power spectrum to divide the calculation into $P(k)$-dependent coefficients and $P(k)$-independent integrations of basis functions multiplied by spherical Bessel functions. We find analytical expressions for the latter integrals in terms of special functions, for which recursion provides a fast and accurate evaluation. The algorithm, therefore, circumvents direct integration of highly oscillating spherical Bessel functions.
We provide a method for fast and exact simulation of Gaussian random fields on spheres having isotropic covariance functions. The method proposed is then extended to Gaussian random fields defined over spheres cross time and having covariance functio
ns that depend on geodesic distance in space and on temporal separation. The crux of the method is in the use of block circulant matrices obtained working on regular grids defined over longitude $times$ latitude.
Computing the dominant Fourier coefficients of a vector is a common task in many fields, such as signal processing, learning theory, and computational complexity. In the Sparse Fast Fourier Transform (Sparse FFT) problem, one is given oracle access t
o a $d$-dimensional vector $x$ of size $N$, and is asked to compute the best $k$-term approximation of its Discrete Fourier Transform, quickly and using few samples of the input vector $x$. While the sample complexity of this problem is quite well understood, all previous approaches either suffer from an exponential dependence of runtime on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT algorithm of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is $O(Nlog N)$ in any dimension $d$. In this work, we introduce a new high-dimensional Sparse FFT toolkit and use it to obtain new algorithms, both on the exact, as well as in the case of bounded $ell_2$ noise. This toolkit includes i) a new strategy for exploring a pruned FFT computation tree that reduces the cost of filtering, ii) new structural properties of adaptive aliasing filters recently introduced by Kapralov, Velingker and ZandiehSODA19, and iii) a novel lazy estimation argument, suited to reducing the cost of estimation in FFT tree-traversal approaches. Our robust algorithm can be viewed as a highly optimized sparse, stable extension of the Cooley-Tukey FFT algorithm. Finally, we explain the barriers we have faced by proving a conditional quadratic lower bound on the running time of the well-studied non-equispaced Fourier transform problem. This resolves a natural and frequently asked question in computational Fourier transforms. Lastly, we provide a preliminary experimental evaluation comparing the runtime of our algorithm to FFTW and SFFT 2.0.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
