Computing the Oja Median in R : The Package OjaNP

JSS Jou nal o S a is ical So wa e Feb ua y 2020, Volume 92, Issue 8. doi: 10.18637/jss. 092.i08 Compu ing he Oja Median in R: The Package OjaNP Daniel Fische Na u al Resou ces Ins i u e Finland & Uni e si y o Tampe e Ka l Mosle Uni e si y o Cologne Jy ki Mö önen Uni e si y o Helsinki Klaus No dhausen Vienna Uni e si y o Technology Oleksii Poko ylo Uni e si y o Cologne Daniel Vogel Uni e si y o Abe deen Abs ac The Oja median is one o se e al ex ensions o he uni a ia e median o he mul i a i- a e case. I has many desi able p ope ies, bu is compu a ionally demanding. In his pape , we i s e iew he p ope ies o he Oja median and compa e i o o he mul i- a ia e medians. Then, we discuss ou algo i hms o compu e he Oja median, which a e implemen ed in ou Rpackage OjaNP. Besides hese algo i hms, he package con ains also unc ions o compu e Oja signs, Oja signed anks, Oja anks, and he ela ed sca - e concep s. To illus a e hei use, he co esponding mul i a ia e one- and C-sample loca ion es s a e implemen ed. Keywo ds: Oja median, Oja signs, Oja signed anks, Oja anks, R,C++. 1. In oduc ion The uni a ia e median is a popula loca ion es ima o . I is, howe e , no s aigh o wa d o gene alize i o he mul i a ia e case since no gene aliza ion is known ha e ains all p op- e ies o he uni a ia e es ima o , and he e o e di e en gene aliza ions emphasize di e en p ope ies o he uni a ia e median. So besides he Oja median desc ibed he e, he e a e se e al o he mul i a ia e median concep s. Hay o d (1902) sugges ed he i s gene aliza ion by simply using he ec o o he ma ginal medians. O he popula mul i a ia e medians a e Tukey’s median (Tukey 1975) and he spa ial median (also known as L1median). The spa- ial median was ini ially de ined as a bi a ia e median (Webe 1909,1929) and subsequen ly 2OjaNP: Compu ing he Oja Median in R ex ended o he gene al mul i a ia e case. These and mo e mul idimensional medians a e su eyed in Small (1990) and Oja (2013). While he ec o o ma ginal medians is qui e easy o compu e, he o he mul i a ia e medians a e mo e compu a ionally expensi e. Pa icula ly he Oja median (Oja 1983) has, despi e i s compelling s a is ical p ope ies, no been used e y o en in p ac ice so a , since i is di icul o compu e. The main opic o his pape is o desc ibe he R(RCo e Team 2019) package OjaNP (Fische , Mosle , Mö önen, No d- hausen, Poko ylo, and Vogel 2020), which p o ides se e al algo i hms o he compu a ion o he Oja median in Rand is a ailable om he Comp ehensi e RA chi e Ne wo k (CRAN) a h ps://CRAN.R-p ojec .o g/package=OjaNP. The ou line o his pape is as ollows. In Sec ion 2.1, we e iew and compa e some mul i- a ia e medians and show which p ope ies o he uni a ia e median is gene alized by which mul i a ia e median. Ou main ocus is on he Oja median, whose basic p ope ies a e dis- cussed in Sec ion 2.2, ollowed by an in oduc ion o Oja signs and anks (Sec ion 2.3), Oja signed anks (Sec ion 2.4) and Oja sign and ank co a iance ma ices (Sec ion 2.5). To demon- s a e he applica ion o he Oja median and i s sign and ank concep s, Sec ion 2.6 discusses one- and C-sample es s o loca ion. In Sec ion 3, we ocus on he di e en algo i hms p o ided by he package OjaNP o calcula e he Oja median. Fou di e en algo i hms a e a ailable: wo exac algo i hms and wo app oxima e algo i hms based on di e en designs. Sec ion 4shows how o use he package OjaNP in o de o calcula e he Oja median and ela ed s a is ics. We p o ide simple examples, and addi ional benchma ks a e calcula ed o analyze he pe o mance o he implemen a ions. A concep equen ly encoun e ed in his pape is a ine equi a iance. We use i in he sense o ull- ank a ine equi a iance, which is common in obus s a is ics. Gi en he k-dimensional sample x1,...,xnwe le X= (x1. . . xn)>be he da a ma ix o dimension n×k, con aining he da a poin s as ows. Subsequen ly he da a sample is iden i ied wi h X. Fo a gi en a ine- linea ans o ma ion T:Rk→Rk,x7→ Ax +bwi h b∈Rkand A∈Rk×knon-singula , he da a ma ix Yo he ans o med da a T(x1), . . . , T(xn)is gi en by Y=T(X) = XA>+1b>, whe e 1deno es he n×1 ec o consis ing o ones. We call an Rk- alued loca ion s a is ic µ(X)a ine equi a ian , i µ(T(X)) = T(µ(X)) o all Tas abo e. (1) This applies analogously o se - alued loca ion s a is ics µ, such as median se s. Fo a ma ix- alued sca e s a is ic S aking on alues in Rk×k, a ine equi a iance is commonly unde s ood as S(T(X)) = AS(X)A>. Fo a mo e de ailed in oduc ion o a ine equi a iance, see Oja (2010). Jou nal o S a is ical So wa e 3 2. Oja median and ela ed concep s 2.1. Oja median and o he mul i a ia e medians We s a by in oducing he uni a ia e median o dis ibu ions. Gi en a dis ibu ion unc ion F, le F−11 2−= in x∈R:F(x)≥1 2and F−11 2+= sup x∈R:F(x)≤1 2. Then he median (se ) o Fis gi en by he in e al Med(F) = F−11 2−, F−11 2+.(2) Any poin o he in e al di ides he dis ibu ion in wo hal es o equal p obabili y weigh and can ep esen he median. In case a unique selec ion is needed, we use he g a i y cen e o he median se as a (single-poin ) median and deno e i by he lowe case symbol, med(F) = F−11 2++F−11 2− 2.(3) Fo a gi en sample X= (x1, . . . , xn), he median med(X)is ob ained as med(X) =    x(n+1 2)i nis odd , 1 2x(n 2)+x(n 2+1)i nis e en , wi h x(i)being he i h o de s a is ic. The la e de ini ion is a special case o (3), ob ained by aking F o be he empi ical dis ibu ion o X, which gi es equal p obabili y mass o each o he poin s x1, . . . , xn. No e ha med(X)is an a ine equi a ian loca ion s a is ic. Now le X= (X1,...,Xk)be a k-dimensional da a se , whe e Xideno es he i h column o Xand co esponds hence o he i h a iable. The many exis ing no ions o a k- a ia e median o such da a ha e in common ha hey educe o he uni a ia e median o k= 1. Mul i a ia e medians a e gene ally non-unique, and we selec , as abo e, he g a i y cen e o he median se o ob ain a unique ep esen a ion. To he bes o ou knowledge he i s gene aliza ion o he uni a ia e median o he mul i- a ia e case is he ec o o ma ginal medians mmed desc ibed in Hay o d (1902). De ini ion 1. The ec o o ma ginal medians mmed o he sample Xis de ined as mmed(X) = (med(X1), . . . , med(Xp))>. The ec o o ma ginal medians is easily compu ed bu no a ine equi a ian . Example 1. A simple o a ion o wo-dimensional da a isualizes he p oblem o no a ine equi a ian ans o ma ions. In he le pa o Figu e 1a wo-dimensional da a se is plo ed and o a ed a ound he cen e poin +. A he same ime he ma ginal median mmed is 4OjaNP: Compu ing he Oja Median in R ● ● ● ● ● ● ● ● ● í í í í      í í í í      ; < ● ● ● ● ● ● ● ; < ● ● ● ● ● ● ● ● í í    Figu e 1: T ans o ma ion o diffe en mul i a ia e medians. con inuously plo ed in ed. An affine equi a ian median would ollow he o a ion on a ci cle, meaning ha i would no be affec ed by he deg ee o he o a ion o he o iginal da a. The blue ci cle ep esen s he Oja median and hence, illus a es he beha io o an affine equi a ian median. In he igh pa o Figu e 1we isualize he beha io o a o a ion in a ian es ima o ha is no scale in a ian . We use he spa ial median smed as an example o a no scale in a ian s a is ic, see Defini ion 3below. Fo fi e example poin s he median is calcula ed and indica ed as he cen e poin , connec ed wi h lines o he da a poin s. Then, he scale o hose fi e poin s was ans o med in o he s a shape on he igh side o his plo . The loca ion o he spa ial median o he ans o med da a is indica ed a he op o cu ed a ow. An affine equi a ian median, howe e , would s ill be equi alen o he ans o med median o he o iginal da a. The Oja median (and any o he affine equi a ian s a is ic) ulfills his c i e ion. The second gene aliza ion o he uni a ia e median e iewed he e is based on he ac ha o a gi en sample Xand i s median med(x) he equa ion n  i=1 11(−∞,med(x)](xi)= n  i=1 11[med(x),∞)(xi) holds, whe e 11A(xi)=1i xi∈Aand =0o he wise. This means, he e a e as many obse a ions smalle han med(x)as a e bigge , as i was poin ed ou , e.g., in Ho elling (1929). Gi en a k-dimensional da a se , we conside hal spaces in e e y di ec ion ∈Sk−1= {x|x=1}.Le H deno e he “minimal” hal space wi h no mal ec o ha con ains a leas hal o he da a poin s, i.e., o any o he hal space ˜ H wi h hese p ope ies H ⊂˜ H holds. The in e sec ion o all H , ∈Sk−1, o ms he Tukey median Tmed(X). I he da a a e in gene al posi ion, each such hal space is bo de ed by a hype plane h ough exac ly k da a poin s, and he Tukey median is in gene al no single on. (A se o k- a ia e da a is in gene al posi ion i a mos ko hem lie on he same hype plane.) The unique Tukey median med(X) is defined as he g a i y poin o his median se ; see Tukey (1975)andDonoho and Gasko (1992). I is affine equi a ian (Chen 1995) and can be in oduced as he maximize o a dep h unc ion as ollows. Defini ion 2. Le Xbe a k-dimensional sample as abo e. Fo any x∈Rk, depX(x)= 1 nmin  =1 #{i: xi≥ x}(4) Jou nal o S a is ical So wa e 5 is called he Tukey dep h o loca ion dep h o xw. . . X. (He e #{S}deno es he ca dinali y o a se S.) The Tukey median Tmed(X)o he sample Xis de ined as he maximize o he Tukey dep h, Tmed(X) = a gmax x∈Rk{ depX(x)}.(5) Ano he way o gene alize he uni a ia e median is o ans e i s minimizing ea u e in o highe dimensions. Conside again a uni a ia e sample X= (x1, . . . , xn)in R. When mini- mizing he sum Pn i=1 |xi−x|o e x∈Rwe ob ain med(X) = a gmin x∈R n X i=1 |xi−x|.(6) This minimizing ea u e o he uni a ia e median is in e p e able in wo ways: I is he sum o absolu e de ia ions, bu i can also be iewed as he sum o one-dimensional simplices. The i s in e p e a ion will lead us o he spa ial median, he second o he Oja median. The spa ial median is p esumably he mos popula mul i a ia e median and almos as old as he ma ginal median. Webe (1909) i s desc ibed he spa ial median and used i o sol e an economic p oblem: He was looking o he bes place o a dis ibu ion cen e in he sense, ha he sum o dis ances be ween ou pos s and he dis ibu ion cen e becomes minimal. The k-dimensional ex ension o his app oach is he spa ial median. De ini ion 3. The spa ial median smed o a k- a ia e da a sample Xis de ined as smed(X) = a gmin x∈Rk(n X i=1 kxi−xk2).(7) He e k·k2deno es he Euclidean no m. The spa ial median is some imes also e e ed o as he L1median since i minimizes he L1no m o he n- a ia e ec o o dis ances kxi−xk2. The spa ial median is no a ine equi a ian as is isualized in he igh pa o Figu e 1. Gi en an a ine ans o ma ion T:R2→R2which ans o ms he da a poin s om he le s a -shaped igu e in o he igh s a -shaped igu e, he cen e o each s a is he spa ial median o he da a poin s. Howe e , due o he lack o a ine equi a iance, he ans o med spa ial median T(smed(X)) (ma ked wi h he a ow) does no coincide wi h he spa ial median smed(T(X)) o he ans o med da a se . The spa ial median is o a ion in a ian , bu no scale in a ian . Oja (1983) in oduced a mul i a ia e median based on olumes o simplices. A k-dimensional simplex is he con ex hull o (k+ 1) spanning poin s in gene al loca ion. Le x1= (x1,1, . . . , x1,k)>,x2= (x2,1, . . . , x2,k)>,...,xk+1 = (xk+1,1, . . . , xk+1,k)> be k+ 1 poin s in gene al loca ion om Rk. The olume V(x1,...,xk+1)o he simplex spanned by he poin s x1,...,xk+1 is hen gi en by V(x1,...,xk+1) = abs         1 k!de         1 1 ··· 1 x1,1x2,1··· xk+1,1 x1,2x2,2··· xk+1,2 . . .. . .. . . x1,k x2,k ··· xk+1,k                 ,(8) 6OjaNP: Compu ing he Oja Median in R see, e.g., S ein (1966). Le Fbe a dis ibu ion on Rkha ing ini e i s momen . The Oja median Omed(F)o Fis de ined as ollows: o i.i.d. andom ec o s X1,...,Xk, each dis ibu ed wi h F, de ine he Oja median se as Omed(F) = a gmin µ∈Rk E(V(X1,...,Xk,µ)). Fo da a we ha e he ollowing de ini ion. Le Pn,k ={p= (i1, . . . , ik)|1≤i1<··· < ik≤n}(9) be he se o all o de ed k- uples ou o {1, . . . , n},1≤k≤n. De ini ion 4. The Oja median Omed o a k-dimensional sample X= (x1. . . xn)>o size n>kis de ined as Omed(X) = a gmin x∈Rk  X (i1,...,ik)∈Pn,k V(xi1,...,xik,x)   .(10) This means ha he Oja median o a k-dimensional sample is any poin x∈Rk o which he sum o simplex olumes o e all combina ions o possible kda a poin s is minimal. No e ha Omed(X)equals Omed(FX), whe e FXis he empi ical dis ibu ion on x1. . . xn. A unique e sion o he Oja median, deno ed omed(X), is ob ained by selec ing he poin o g a i y o Omed(X). 2.2. P ope ies o he Oja median As o he mul i a ia e ex ensions o he median, he Oja median is no unique. In he bi a ia e case, we ha e he ollowing esul . Theo em 1. I nis e en and he da a poin s x1,...,xn∈R2a e in gene al posi ion, hen he Oja median is unique. Fo de ails see Niinimaa (1995). The au ho also iden i ies a necessa y and su icien condi ion o he bi a ia e Oja median o be unique i nis odd. The e appea s o be no esul o highe dimensions, bu Oja (1999) conjec u es ha he Oja median is unique o e en (odd) sample sizes i he dimension kis e en (odd). Figu e 2 isualizes he Oja median in se e al small- sample da a si ua ions. Theo em 2. The Oja median o a sample is a con ex se . See Oja and Niinimaa (1985) o de ails. Theo em 2is illus a ed in Figu e 3. Con ou lines o he objec i e unc ion (10) a e plo ed o wo small da a clouds. The objec i e unc ion is con ex o , bo h, e en and odd sample sizes. Theo em 3. The Oja median is a ine equi a ian . Hence he Oja median is a p ope loca ion s a is ic in he sense o (1), i.e., omed(T(X)) = T(omed(X)). The nex esul can be ound, e.g., in A cones, Chen, and Gine (1994), Shen (2008). Jou nal o S a is ical So wa e 7 • • • Q  • Q  • • • • Q  • • • • • Q  • • • • • • Q  • • • • • • • Q  • • • • • • • Figu e 2: Example plo s o he bi a ia e case.           • • • • •           • • • • • • Figu e 3: Con ou plo o he bi a ia e case. Theo em 4. Unde mild egula i y condi ions (including he exis ence o fi s momen s) o an i.i.d. sample X=(x1...xn) om he dis ibu ion F, we ha e √n(omed(X)−omed(F)) →dNk(0,A−1B(A−1)), whe e Bis he Oja sign co a iance ma ix (OSCM) defined la e in Sec ion 2.5 a Fand Ais he expec ed co a iance ma ix be ween he Oja signs (osgn, see Sec ion 2.3) and he op imal loca ion sco e o F. 8OjaNP: Compu ing he Oja Median in R Median A ine equi a iance B eakdown poin Ma ginal median No 1/2 Tukey median Yes 1/(k+ 1) Spa ial median No 1/2 Oja median Yes 0 In luence unc ion Asymp o ic dis ibu ion Ma ginal medians Niinimaa and Oja (1995)Babu and Rao (1988) Tukey median Romanazzi (2001)Bai and He (1999) Spa ial median Niinimaa and Oja (1995)Mö önen, No dhausen, and Oja (2010) Oja median Niinimaa and Oja (1995)Shen (2008) Table 1: Main p ope ies o di e en mul i a ia e medians. Conce ning obus ness he Oja median has he ollowing p ope ies. Theo em 5. Le Fha e a ini e i s momen . Then he Oja median has a bounded in luence unc ion. The in luence unc ion is o example gi en in Niinimaa and Oja (1995). The Oja median has an asymp o ic b eakdown poin o 0. Niinimaa, Oja, and Tableman (1990) show he ollowing: Theo em 6. The ini e-sample b eakdown-poin o he bi a ia e Oja median is 2/(n+ 2). Table 1summa izes he main p ope ies o he Oja median and o he common mul i a ia e medians discussed he e. Fo ano he ecen discussion o he di e en medians see also Oja (2013). 2.3. Oja signs and anks Closely ela ed o he median is he concep o signs and anks. In his sec ion we in oduce he mul i a ia e Oja sign and Oja ank and ela e hem o o he mul i a ia e signs and anks, co esponding o he ma ginal and he spa ial median. Again, o mo i a e he subsequen de i a ions we ake a b ie look a he uni a ia e case. Suppose we ha e a uni a ia e da a se X= (x1. . . xn)>,n∈N. We call sgnX(x) = sgn(x−med(X)), x ∈R,(11) he sign o xw. . . he da a sample X, whe e sgn is he uni a ia e sign unc ion (sgn(x) = x |x| i x6= 0 and ze o o he wise), and med(X)is he uni a ia e median o he sample X. The e a e se e al possibili ies o sui ably assigning anks o he da a poin s. By nkX(x) = 1 n n X i=1 sgn(x−xi), x ∈R,(12) we de ine no malized cen al anks, which may ake on 2n+ 1 possible alues anging om −1 o 1. In he ollowing we call nkX(x)simply he ank o xw. . . X. Jou nal o S a is ical So wa e 9 The median app op ia ely cen e s he da a, i.e., he signs o he da a poin s, cen e ed by he median, sum up o ze o: n X i=1 sgnX(xi) = n X i=1 sgn(xi−med(X)) = 0.(13) The sample mean does he same o he da a poin s hemsel es. In o he wo ds we may say ha he median has cen al ank ze o, nkX(med(X)) = −1 n n X i=1 sgn(xi−med(X)) = 0 ,(14) and, in his espec , is he mos cen al poin . Iden i ies (13) and (14) (which a e di e en o mula ions o he ac ha hal o he da a lies abo e and below he median) p o ide he essen ial link be ween signs and anks and he median and a e a mo i a ing p inciple behind he mul i a ia e sign and ank unc ions we will in oduce nex . No e ha a k- a ia e sign unc ion should be a ec o ha can poin in any di ec ion o he k-dimensional space. The same holds o a mul i a ia e ank unc ion based on signs. An ob ious ex ension o (11) o he mul i a ia e se ing is i s componen wise applica ion, leading o he ma ginal sign unc ion. We call msgnX(x) = msgn(x−mmed(X)) he ma ginal sign o x∈Rkw. . . he k- a ia e da a sample X= (x1. . . xn)>, whe e x= (x1. . . xk)>, msgn(x) = (sgn(x1). . . sgn(xk))>, and mmed(X)is he ma ginal median o X. An equally s aigh o wa d gene aliza ion is he spa ial sign o xw. . . X: ssgnX(x) = ssgn(x−smed(X)),x∈Rk, whe e ssgn(x) =    1 kxkxi x6=0, 0i x=0, and smed(X)is he spa ial median o X. The co esponding ank unc ions, he ma ginal ank m nkXand he spa ial ank s nkX, a e ob ained by eplacing sgn in (12) by msgn and ssgn, espec i ely. The Oja sign is de ined as ollows. Fo 0≤k≤n, le Nn,k =n kand Pn,k as in (9). We call osgnX(x;m) = 1 Nn,k−1X (i1,...,ik−1)∈Pn,k−1∇xde (xi1−m,...,xik−1−m,x−m)(15) =1 Nn,k−1X (i1,...,ik−1)∈Pn,k−1∇x de 1 1 . . . 1 1 m xi1. . . xik−1x! he Oja sign o he poin x∈Rkw. . . he da a sample Xand he cen e loca ion mand osgnX(x) = osgnX(x;omed(X)) (16) 16 OjaNP: Compu ing he Oja Median in R is he e o iew he signs, signed anks and anks as sco es, which eplace he obse a ions in he classical mul i a ia e p ocedu es. In p inciple, obus coun e pa s o any mul i a ia e me hod can be de i ed his way. We demons a e he e he mul i a ia e one-sample and C- sample loca ion es s. Fo ha pu pose, deno e o a sample poin xi he co esponding sco e s(xi;m), whe e mis an op ional loca ion w. . . o which he sco e is compu ed. The one-sample es s Assume X= (x1,...,xn)is a sample o size n om a k- a ia e symme ic dis ibu ion Fwi h symme y cen e µ. We a e in e es ed in es ing he null hypo hesis H0:µ=µ0agains H1:µ6=µ0. Deno e ¯ s=1 nPn i=1 s(xi,µ0)as he a e age o he sco e alues unde he null hypo hesis and Σs=1 nPn i=1 s(xi,µ0)s(xi,µ0)>. The es s a is ic is hen Q=n¯ s>Σ−1 s¯ s. Using Oja signs o Oja signed anks as sco es, his yields a s aigh o wa d ex ension o Ho elling’s classical one-sample T2- es . The es is in a ian unde a ine ans o ma ions and asymp o ically dis ibu ion- ee and has a limi ing χ2 kdis ibu ion. Tes decisions can also be based on pe mu a ion p inciples by andomly changing he signs o he sco es. The es s a e desc ibed in de ail in He manspe ge , Nyblom, and Oja (1994) and He manspe ge , Mö önen, and Oja (1997). Simila es s can also be na u ally cons uc ed using ma ginal o spa ial signs and signed anks. See Pu i and Sen (1971) and Oja (2010) o de ails. The C-sample es s Le Xc= (xc,1,...,xc,nc),c= 1, . . . , C, co espond o k- a ia e samples coming om C≥2 g oups ha ing dis ibu ions Fc ha di e only in loca ion pa ame e s µc,c= 1, . . . , C. The null hypo hesis is µ1=. . . =µC, i.e., he Cg oups ha e he same loca ion. Deno e X= (X1,...,XC)as he combined sample and n=PC i=1 ni. Then ¯ sc=1 ncPnc j=1 s(xc,j), c= 1, . . . , C, is he a e age sco e alue o g oup ccompu ed w. . . o he loca ion o he com- bined sample. Simila ly, Σs=1 nPn i=1 s(xi)s(xi)>is compu ed o he combined g oups. The es s a is ic is ob ained as Q= C X c=1 nc¯ s> cΣ−1 s¯ sc. When Oja signs and Oja anks a e used as sco es, C-sample es s o mul i a ia e loca- ion a e ob ained ha a e asymp o ically dis ibu ion- ee and a ine in a ian . The limi ing dis ibu ion o he es s a is ic is χ2 k(C−1), bu p alues can be ob ained by pe mu ing obse - a ions be ween he g oups. The wo es s a e desc ibed in He manspe ge and Oja (1994); He manspe ge , Mö önnen, and Oja (1998). Simila es s based on o he concep s o signs and anks a e desc ibed also in Pu i and Sen (1971) and Oja (2010). 3. Desc ip ion o he algo i hms The package OjaNP con ains ou di e en algo i hms o calcula e he Oja median. Two exac algo i hms and wo app oxima e algo i hms. The i s exac algo i hm was de eloped Jou nal o S a is ical So wa e 17 in Ronkainen, Oja, and O ponen (2003) as well as one o he app oxima e algo i hms. The second exac algo i hm (Mosle and Poko ylo 2015) is based on he i s one: I accele a es he compu a ion conside ably by in oducing bounds o he egion o sea ch. The nume i- cal calcula ion is a non- i ial p oblem which consumes eno mous calcula ion esou ces and hence, he exac algo i hms a e limi ed o small da a si ua ions only and, as a consequence, app oxima e algo i hms a e needed. These o e pa ame e s o egula e he speed s. accu acy ade-o , and he use has o decide om case o case which algo i hm o choose wi h which uning pa ame e s. In Sec ion 4we will gi e an o e iew o e he se e al op ions and hei e ec on o he calcula ion p ecision and ime. Be o e ha , we a e going o desc ibe he ou algo i hms. 3.1. Exac algo i hm Ronkainen e al. (2003) implemen ed he ideas om Niinimaa, Oja, and Nyblom (1992) and gene alized hem in o highe dimensions based on he esul desc ibed in He manspe ge , Mö önen, and Oja (1999), whe eby he e ices o he Oja median se a e always loca ed on in e sec ions o hype planes ha a e spanned by da a poin s. Ronkainen e al. (2003) cons uc ed a Las Vegas algo i hm as ollows. (This is a simpli ied e sion; a mo e de ailed desc ip ion can be ound in he o iginal pape .) 1. Le Hbe he se o all (k−1)-dimensional hype planes spanned by he poin s in X. 2. Take he da a poin xc∈Xcloses o he mean as an ini ial candida e poin . 3. Sample k−1hype planes ou o Hsuch ha he candida e poin is on hei in e sec- ion L. 4. Calcula e he Oja dep h o each in e sec ion poin be ween Land he hype planes in H. 5. Take he poin x∗ cwi h he highes Oja dep h as nex candida e poin o he Oja median. 6. Repea s eps 3 o 5 un il no imp o emen in he objec i e unc ion is possible (o la es a e n epe i ions). 7. The esul o he exac Oja median is he las candida e poin x∗ c. Ronkainen e al. (2003) ocused on compu a ional s abili y a he han e iciency. In case a candida e poin is a da a poin , he e a e k−1possible in e sec ion hype planes L. Ins ead o only ollowing he one de e mined by he g adien o he objec i e unc ion, he algo i hm ies all possible ones. This algo i hm inds jus one o he e ices o he median se . While sea ching o he median, he algo i hm may pass h ough se e al e ices o he median se , al hough i is no gua an eed ha i isi s all o hem. The eason is ha on s ep 5 only he i s o possibly wo poin s ha ing highes Oja dep h is aken as x∗ c. Howe e , in case o a non-unique median, he e exis wo such poin s lying on an edge o he median se . To deli e all e ices o he median se , he algo i hm can be modi ied as ollows: I has o s o e bo h poin s as e ices and, in addi ion, check all lines passing h ough hem. 18 OjaNP: Compu ing he Oja Median in R The algo i hm is implemen ed in C++ and was ini ially published as s and-alone so wa e on he pe sonal webpage o Tommi Ronkainen bu canno be accessed anymo e in ha o m. The implemen a ion was modi ied such ha i can be used di ec ly om R. 3.2. Exac bounded algo i hm Based on he exac algo i hm o Ronkainen e al. (2003), Mosle and Poko ylo (2015) de- eloped a as e exac algo i hm. This algo i hm uses he cen e ed ank unc ions o build bounded egions which con ain he median. The nega i e ank unc ion −o nkX(x)is a ec- o ha poin s in a di ec ion o ascen o he dep h unc ion. I de ines a hype plane h ough x, on he posi i e side o which he Oja median is ound. The hal spaces de ined by he nega i e ank unc ion a e used o build a bounded egion ha con ains he median. In his algo i hm, hese hal spaces a e selec ed in an i e a i e way and he u he sea ch is es ic ed o hei in e sec ion. The hype planes bo de ing such a sea ch egion will be called bounding hype planes o simply bounds. The s eps o he algo i hm a e as ollows. (A mo e de ailed desc ip ion can be ound in he o iginal pape ): 1. Le Hbe he se o all hype planes spanned by he poin s in X. 2. C ea e he ini ial ec angula bounded egion B, limi ed by hype planes ha a e pe - pendicula o he coo dina e axes and go h ough he maximal and minimal coo dina es o he da a poin s on hese axes. 3. I e a i ely educe he bounded egion Bby adding hype planes ha go h ough a p ope ly chosen cen al poin o he egion and ha e hei no mal ec o s equal o he co esponding nega i e ank unc ion. Speci ically, he mean alue o he bounds’ in e sec ion poin s is selec ed as a cen al poin in ou implemen a ion. The bounds o Ba e cu o by newly added hype planes. 4. The egion is educed un il he desi ed inal olume o he bounded egion is eached. 5. Add he bounds om B o H. •A he i s i e a ion: Take a andom ini ial line Lon he bo de o B. •A u he i e a ions: Sample k−1hype planes ou o Hin ha way, ha he candida e poin is on hei in e sec ion line L. 6. Calcula e he Oja dep h on each in e sec ion poin be ween Land hype planes in H ha lies in he bounded egion. 7. Take he poin x∗ cwi h he highes Oja dep h as nex candida e poin o he Oja median. 8. Repea s eps 6 o 8 un il no imp o emen in he objec i e unc ion is possible (o la es a e n epe i ions). 9. The esul o he exac Oja median is he las candida e poin x∗ c. Jou nal o S a is ical So wa e 19 0 5 10 15 20 25 30 0 50 100 150 200 250 Remaining Volume Time T_To al T_bounds T_coun Figu e 7: Dependence o calcula ion ime on he size o he bounded egion; ime needed o bounding (Tbounds), o minimizing (Tcoun ), and o al ime (T o al). Fo compa ison: o al ime o he i s exac algo i hm is abou 340 seconds. The bounded egions educe he complexi y o he sea ching p ocedu e by educing he numbe o hype planes ha c oss he sea ching lines as well as he numbe o hei in e sec ions o be conside ed in he minimiza ion p ocedu e. The algo i hm is d i en by he desi ed inal olume o he bounded egion, which is he olume o he minimal ec angle con aining he egion and ha ing edges pa allel o he coo dina e axes. As his pa ame e is educed, he ime needed o build he bounded egions (Tbounds) in- c eases, while he minimiza ion ime (Tcoun ) dec eases along wi h he numbe o hype planes and hei in e sec ions; see Figu e 7. The o al compu ing ime (T o al) dec eases apidly wi h he olume, bu hen slowly g ows again. Beyond some poin he p ocedu e becomes less e icien . Fo compa ison, he o iginal algo i hm needs a o al ime T o al o ca. 340 seconds in his example. I appea s ha he as es compu a ion is ob ained i bounds a e imposed un il he olume o he bounded egion anges a ound 10−8o he o iginal olume. No e ha he bounds may cu o some o he e ices o he median se . Mo eo e , i he cen al poin o he bounded egion lies in he median se on s ep 3, i s nega i e ank unc ion is ze o, and his poin is di ec ly e u ned as a median, as on Figu e 9. Due o limi a ions in compu ing memo y and long calcula ion ime, he exac algo i hm and i s bounded e sion a e only able o calcula e he Oja median o small da a se s in low dimensions. Fo example, he calcula ion o he median in a da a se o size 100 ×5needs 12 GB RAM. The e o e, app oxima e algo i hms a e needed. Ob iously, he bounded algo i hm can be s opped a any i e a ion and some mean alue o he las bounded egion be aken as an app oxima ion o he Oja median. Howe e , unlike he app oxima e algo i hms p esen ed below, his app oach equi es he calcula ion o all hype planes. Due o i s high compu a ional equi emen s i is less sui ed as an app oxima e algo i hm o big da a se s in high dimensions. Fo calcula ion speed easons, also his algo i hm is implemen ed in C++. 20 OjaNP: Compu ing he Oja Median in R 3.3. G id-based algo i hm The hi d algo i hm, which calcula es an app oxima ion o he Oja median, was also p oposed in Ronkainen e al. (2003). Technically i is a Mon e Ca lo algo i hm. The algo i hm lays a uni o m g id o e he da a se . A each g id poin a es is pe o med whe he he poin is a possible candida e. The amoun o candida e poin s is educed as long as only one g id poin is le . This poin is a e wa ds he cen e o a smalle bu dense g id, whe e again each g id poin is es ed. The algo i hm s ops when he dis ance be ween wo g id poin s ge s smalle han a p ede ined pa ame e . A second uning pa ame e is he signi icance le el o he poin es s. The s eps o he algo i hm a e: 1. C ea e a g id Gwi h equidis an kno dis ance h, co e ing he whole da a se . 2. Choose andomly a se o hype planes, build he es s a is ic and es each o he g id kno s in Gwhe he i is an Oja median. 3. Remo e hose g id kno s which ha e been es ed no o be an Oja median. 4. I he e is mo e han one kno le , sample addi ional hype planes and epea he es o he emaining kno s. 5. Repea hese s eps un il only one g id kno is le o e . I he las es emo es all emaining ones, ake he las se . 6. Build a new g id a ound he las emaining old g id kno wi h equidis an kno dis ance h/2. 7. Repea all hese s eps un il he g id dis ance eaches a p ede ined h eshold. 8. The las poin is aken as he Oja median. Fo u he de ails, especially abou he es ing p ocedu e, we e e o he o iginal pape Ronkainen e al. (2003). I may happen ha he e is con inually mo e han one poin le on s ep 5. In his case sampling o he addi ional hype planes may no help and he algo i hm hangs. We es ic he algo i hm o 5000 i e a ions on s ep 5, a e which he g id poin wi h he bes es s a is ic is passed o s ep 6 and he numbe o i e a ions is educed o 100. We epea un il he g id h eshold is eached and e u n he g id poin wi h he bes es s a is ic as an Oja median app oxima ion. The g id-based algo i hm is pa o he ini ially s and-alone ool ha con ains also he im- plemen a ion o he i s exac algo i hm. I is as well w i en in C++ o speed up he compu a ional bu den. 3.4. E olu iona y algo i hm The ou h algo i hm o calcula e he Oja median is an e olu iona y algo i hm, which is based on mu a ions o he la es candida e poin s. I was de eloped by he Depa men o Compu e Science, E icien Algo i hms and Complexi y Theo y a he TU Do mund, bu has no been published be o e. The algo i hm wo ks as ollows: 1. Se he le el o ini ial mu a ion a iance σ2 0. Jou nal o S a is ical So wa e 21 2. Take 10 andomly chosen obse a ions om X. 3. E alua e he objec i e unc ion o all hese poin s and ake he minimum as s a ing candida e poin η. 4. Choose k+ 1 andom numbe s x1, . . . , xk, l om a N(0, σ2 0)dis ibu ion and calcula e he k- a ia e mu a ion ec o ν=|l| qx2 1+···+x2 k (x1, . . . , xk)>. The mu a ion ec o νhas a no mally dis ibu ed leng h wi h gi en a iance σ2 0and uni o mly dis ibu ed di ec ion. 5. Calcula e mmu a ion poin s ηi=η+νi o i= 1, . . . , m om he las candida e poin η. 6. Calcula e he a io how o en he objec i e unc ion is bigge a he mu a ions han a η. 7. I > 0.2 hen σ2 0·κelse σ2 0·1 κ o some κ > 1. 8. Choose as a new candida e poin he mu a ion wi h he smalles objec i e unc ion alue. 9. Repea s eps 4 o 8 un il he a iance o he nex mu a ion d ops unde a p ede ined alue s. 10. I he algo i hm has no e mina ed a e n s eps, s op he calcula ion. S ep 7 con ols he dynamic o he mu a ion. I a mo e han 20% o he mu a ions he objec i e unc ion has a smalle alue han a he las candida e poin , he algo i hm inc eases he a iabili y o he mu a ion; hence he sea ch a ea is enla ged. S ep 10 ensu es ha he algo i hm e mina es in any case. As he o he implemen a ions also his algo i hm is implemen ed in C++. 3.5. O he algo i hms o he Oja median in R The e a e o he implemen a ions o algo i hms o he Oja median a ailable in R, bu hey a e mos ly es ic ed o wo dimensions. The unc ion med in he package dep h (Genes , Masse, and Plan e 2019) uses he Fo an code o Niinimaa e al. (1992) and is es ic ed o he bi a ia e case. Ano he me hod o compu e he Oja median was sugges ed by Roge Koenke on R-help on 2003-08-16 (see h ps://hypa ia.ma h.e hz.ch/pipe mail/ -help/2003-Augus /037702. h ml using he quan eg package; Koenke 2019): R> oja.median <- unc ion(x) { + n <- dim(x)[1] + A <- ma ix( ep(1:n, n), n) 22 OjaNP: Compu ing he Oja Median in R + i <- A[col(A) < ow(A)] + j <- A[n + 1. - col(A) > ow(A)] + xx <- cbind(x[i, ], x[j, ]) + y <- xx[, 1] * xx[, 4] - xx[, 2] * xx[, 3] + z1 <- (xx[, 4] - xx[, 2]) + z2 <- -(xx[, 3] - xx[, 1]) + e u n(quan eg:: q(y ~ cbind(z1, z2) - 1)$coe ) + } 4. The Rpackage OjaNP The main pu pose o he OjaNP package is o p o ide use s wi h he possibili y o compu e he Oja median. The package includes, howe e , also o he use ul unc ions. The main unc ions o he package a e isualized in Figu e 8. Mos o he unc ion names a e sel -explana o y. Fo de ails abou hem we e e o he co esponding help pages. In he ollowing we will i s explain he unc ion ojaMedian and i s op ions in de ail. Then we demons a e he use o some o he unc ions wi h a small bu illus a i e da a se , which is also con ained in he package. ojaMedian ojaSign ojaSignRank ojaRank ojaSCM ojaRCM oja1sampleTes ojaCsampleTes Figu e 8: The main unc ions in package OjaNP. Jou nal o S a is ical So wa e 23 • • • • • • • ; < ••••• • • • • • • • ••• • • • • • • • • • • • • • • • • • • • • • • • • • • • ••••••• • • • • • • • • • • • • • • • • • • • • • • • • • • • ••••• • • • • • • • • • • • ••• • • • •• •••• • • • • • • • • • • • • • •• • •• • • • • • •• • •• • • • •••• •• • •• • • • •• • •• • • • • •• • •• •• •• •••• •• • • • ••• • • • • • • • •• • •• • • • •• •• • • ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• • ; < • • • • • • • • •• • • •• • • •• • • •• •• •• • • •• •• ••• •• •• • •• •• •• •• • • •• • • • • • • • • • • • • • • •• • • ••••••• • •••• •• •• •• • •• • • • • • • • •• •• • • ••••• • • • • • • • • • • • • • •• • • • • •• • • • • • • • • • • • •• •• • • • • • • • • • • • • • • • • •• • • • • • • • • • • • •• • • ••••• • • • • • • • • • • • • •• • • • • • • • • ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• Figu e 9: Example plo o all ou algo i hms: exac algo i hms ( ed), e olu iona y algo i hm (blue), g id algo i hm (g een). The con ex median se is ma ked wi h yellow. 4.1. The compu a ion o he Oja median in OjaNP The main unc ion o OjaNP is ojaMedian(X, alg = "e olu iona y", sp = 1, na.ac ion = na. ail, con ol = ojaMedianCon ol(...), ...) The use can choose ia he alg op ion be ween ou algo i hms o calcula e he Oja median. Fu he mo e, we ha e an op ion o calcula e he Oja median epea edly and a e age hese esul s in o de o ecei e less a ying esul s. The amoun o epe i ions can be con olled wi h he sp pa ame e . In wha ollows we a e going o explain he diffe en pa ame e s which con ol he flow o he diffe en algo i hms in de ail and gi e insigh s how o choose he pa ame e s in a gi en da a si ua ion. The de aul algo i hm o he ojaMedian unc ion is he e olu iona y algo i hm. The e olu iona y algo i hm elaxes he affine equi a iance p ope y o he Oja median. In o de o es o e i we fi s pe o m a sca e ma ix ans o ma ion o ob ain an in a ian coo dina e sys em (implemen ed in ICS;No dhausen, Oja, and Tyle 2008), apply he algo- i hm o he ans o med da a and e- ans o m a e wa ds. Tha way we es o e he affine equi a iance o his implemen a ion. Figu e 9shows he exempla y ou come o he ou implemen ed algo i hms in simple da a si ua ions o he unique (le ) and non-unique ( igh ) case. We ha e chosen simple da a si ua ions wi h 6 and 7 da a poin s, un he diffe en algo i hms 500 imes and plo ed he ou come in o he figu e. In he le pa o Figu e 9we ha e a da a se ha has a unique Oja median. This one is co ec ly de e mined by he exac implemen a ions ( ed), whe eas bo h app oxima e algo- i hms ha e a sys ema ic beha io which does no diffe s ongly om he non-unique case in he igh side o he g aphic. The e olu iona y algo i hm (blue) de e mines he Oja median always along lines o in e sec ion wi h he esul o a bo de ed a ea. The igh -hand side o Figu e 9exhibi s da a ha ha e a non-unique Oja median. He e he wo exac algo i hms find a e ex ( ed) o he median se , while he e olu iona y algo i hm (blue) yields any poin o he bo de o he median se , ha is he a ea wi h he lowes Oja dep h (yellow). The g id algo i hm, howe e , e mina es in his case usually wi hin he con ex median se . 24 OjaNP: Compu ing he Oja Median in R • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ; < • • • • • •• •• • • • • ••• • • • •• • •• • • • • •• •• • • • •• • •• • •• •• • • •• • • • • • • • •• • •• •• • • •• • • • • • •• • •• • • • • •• • • • • • •• •• •• • •• • •• • ••• •• • • • •• • • • • • • •• •• ••• • • • •• • •• • • • • • • • •• • •• •• • •• • • •• • • • •• • ••• •• • • • • • • • • • • • • •• • • •• • • • • • •• • • •• • • • • •• •• • • •• • • •• • • •• • •• • • • •• •• • •• •• • •• • • • • •• • • • • • • • •• •• • • • •• • •• • • • • •• • •• • • • •• • • •• • •• •• • • • • • •• •• • • •• • • •• • • • •• •• • • • • • • • •• • • • •• • •• • •• •• • •• • •• • • • • • •• • • • •• •• • • •• • •• • • • • •• • • • • • •• • • •• • • • • • • • •• • •• • • • • • •• • • •• •• • • •• • • • • • • ••• • • • • •• •• •• • • •• •• •• • • •• •• • • •• • • •• • • • •• • • •• •• • •• •• • •• • •• • • • •• • • ••• •• • •• ••• • •• • ••• • • • • •• •• ••• • • • •••• • •• • • ••••••• • • • ••••••••• • ••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••••• • • • ••••• • • • • • • • • • • • • • • • ••••• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ••••• • • • • • • • ••• • • • • • • • • • ••• •••••• • • • • • ••• • ••••••• • • • • • • • • • ••• • • •• •• • • • • • • • ••••• • ••••••••• • ••• • • • • • • • • • • • • • • • • • • • • • • • ••••••• • • • • • ••• • ••• • ••• • ••• • • • • • • • • • • • • • • • • • • • • • ••• • • • • • • • • • • • • • ••••• • • • • • ••• • ••• • • • ••••••••••••• • • • ••• • ••••• • • • ••• •• •••• •• •• •••••••••••••••••••••••••••••••••••• • ••••••••••••••••••••••••••••••••• • •• •••••••• • •• • •• • • • • • •• • • • • • • •• •• • • •• • • • • • • • • • •• • • • • • • • • • • •• • • • •• • • • • •• •• •• • • •••• •• • • • •• •• • • • • • • • • • • •• • • • • • • • • • • • • • • • • ••• • • • • • • • •• • • •• •• • • • • • • • • • • • • • • • •• • • • • • • • • • • •• • • • •• • •• • •• • • • • • • •• • • • • •• •• • • • • • •• • • • • • • ••• •• • • • • • • • ; < • • • • • • •• • • • • • • • • • • • • • ••• • • •• • • • • • • • • • • • • •• • • • • • • • • • • •• • • • • •• • • • •• •• • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • •• • • • • • •• • •• • • • •• • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • •• • • • • • • • • • • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ••• • •• • • • • • • • • • • • ••• • • • • • • • • • • • • • • • •• • • •• • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • •• • • • • • • • • • • •• • • • • • • • • •• • • • •• • •• • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • •• • • •• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • •• • • • • • • • • • • • • • • •• • • • •• • • •• • • • • • • • • • • • • ••• • •• • • • • • • • • • ••• • • • • • • • • • •• • • • • • • • • ••• ••••• • ••••• • ••••• • • • •••••••• • • • • • • • • • • ••••••••••••••••• • • • • • ••••• • ••• • • • • • • • • • ••• • •••••••••••• • • • ••••••••••• • • • • • • • ••••• • ••••• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ••• • • • • • • • • • • • • • • • • • • • • • • • ••• • ••• • • • • ••• • • ••• • • • • • • • • • • ••• • • • • • • • • • • • • • •••••• • • • • ••• • • • • • • • • • • • • ••• • ••• • • • • • ••• • • • • • • • • ••• • ••••••• • • • • • • • ••• •••••••• • •••••••• • • ••• • •• • • • • •• • • • • • • • • • • • ••••• • ••• • ••• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ••• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 2MD([DFW (YR$OJ *ULG Figu e 10: Example plo o all ou algo i hms: exac algo i hms ( ed), e olu iona y algo- i hm (blue), g id algo i hm (g een). In a nex s ep we a e going o analyze he ou come o he algo i hms in mo e complex da a si ua ions. The fi s ypical da a si ua ion is a mul i a ia e no mal dis ibu ed da a cloud and we calcula e he Oja median wi h he exac ( ed), he g id (g een) and he e olu iona y algo i hm (blue). As we can see he e olu iona y algo i hm has he bigges a ia ion wi hin he esul s, bu we ha e o keep in mind ha he de aul se ing o ou unc ion is uned o calcula e as esul s. In he nex pa ag aph we will discuss how o ge mo e p ecise esul s in ade-off o calcula ion ime. Fo mos applica ions he as e , less accu a e se ings appea o be p e e able. The second da a se o in e es consis s o wo da a clouds, which a e a away om each o he . The mo i a ion o ha is o see whe he he algo i hms ake his in o accoun o i hey ge s uck in one cloud. As you can see in he igh pa o he figu e, ha all included algo i hms a e capable o calcula ing he Oja median o be in he cen e be ween bo h da a clouds. Le us now compa e he un ime o he wo app oxima e algo i hms depending on he dimen- sion and size o he da a in he bi a ia e case. We do no pe o m a un ime analysis o he exac algo i hms. Thei pe o mance depends s ongly on he compu e used (pa icula ly memo y), much mo e so han he app oxima e ones. On an a e age compu e , bi a ia e p oblems up o 1,000 obse a ions a e sol able in accep - able ime, bu o highe dimensions and sizes his decision has o be made om case o case. Fo example in he se en-dimensional case wi h ens o obse a ions i akes minu es o he exac algo i hm o find he solu ion. The bigges limi a ion o he exac algo i hm is he memo y equi ed o s o e all hype planes. E en i we would allow infini e calcula ion ime, he algo i hm would s ill no be able o calcula e he exac Oja median in mo e complex da a si ua ions because i canno p e-calcula e and access he o al amoun o hype planes, and hence we a e acing a co esponding add ess space p oblem. This also applies o he exac bounded algo i hm. Compa ed wi h he o iginal exac algo i hm, he bounded one finds he solu ion app oxima ely wo o fi e imes as e . In o de o analyze he un ime o diffe en dimensions we simula ed 10,000 mul i a ia e no mal dis ibu ed andom numbe s (wi h μ=0,Σ=I). The app oxima e g id algo i hm (solid g een line) is only able o calcula e he Oja median up o 5 dimensions in accep able ime o his amoun o da a; his is why we did no ake highe dimension si ua ions in o Jou nal o S a is ical So wa e 25  'LPHQVLRQVVL]HQ  7LPHLQ6HFRQGV           6L]HWLPHVA 7LPHLQ6HFRQGV •  •••• • •• • • •• • • • •• • • • • • • • • • •• ••• •• ••  • • •• • •  • • •• • • • •• • ••  • ••  • • • • • ••• •• • • • • • • • • • ••  • • • •  •  • • • • • • • • •  •••• • •• •• • •••• •• •••• • • •• •• • •• •  •• • • •  •• • • •  •• • • • •  • •  • • • • •  •  • • • •••••••• •• •••• • ••••• •• ••• ••• • ••• • • • •  ••• • ••  • •• •  • • • • • • •  • •• • • • •• • • • • • •  • • • • • •• •  • • • • • •  • • ••• • • • • •  • • • • • • • • • • •           (YR$OJ (YR$OJZRFKHFNV *ULG Figu e 11: Run imes o he app oxima e algo i hms: he app oxima e g id algo i hm (solid g een line), he e olu iona y algo i hm (solid blue line), he aw me hod wi hou ans o ma- ions o alida ion checks (do ed blue line). conside a ion. The e olu iona y algo i hm (solid blue) can calcula e in he same ime he Oja median o a 35-dimensional da a se , and e en highe dimensional p oblems a e sol able. Since he ICS s ep (and he e especially he da a alida ion checks) akes a lo o compu a- ional ime we implemen ed also a aw command o access he algo i hms di ec ly wi hou ans o ma ions o alida ion checks (do ed blue line). In he analysis o diffe en dimensions he aw algo i hm does no b ing huge ad an ages, bu in he un ime analysis conce ning he size o he da a in he bi a ia e case ( igh -hand side o Figu e 11)wecande ec ahuge ad an age o mo e han 105obse a ion. The aw algo i hm is e en able o calcula e he Oja median o sample size 5·107. Hence, ou ad ice in ime-c i ical si ua ions wi h high sample size is o use he aw me hod. I he affine equi a ian p ope y is s ill equi ed, we ad ise o pe o m be o ehand ICS sepa a ely wi hou pe o ming he included da a alida ion s eps. The e olu iona y algo i hm has many uning pa ame e s, some o which con ol i s accu acy. As we ha e seen in Figu e 10, he de aul se ings o hese uning pa ame e s a e p e- se o deli e as esul s. In ade-off o highe compu a ional ime, he use can adjus he se ings o ob ain a mo e p ecise algo i hm. The key pa ame e s a e useAllSubse s, nSubse sUsed,andsigmaLog10Dec. The la e is he main abo c i e ion o he algo i hm. I o ces he algo i hm o s op i he loga i hmized ini ial a iance diffe s mo e hen he alue o sigmaLog10Dec om he ac ual loga i hmized a iance. In o he wo ds, when he a iance o he mu a ion ec o is ge ing small enough, he algo i hm s ops. The se ings o useAllSubse s and nSubse sUsed con ol how many spanned hype planes should be aken in o accoun du ing he calcula ion o he Oja median. Since he o al amoun o possible hype planes could be huge (i is n k o nobse a ions in he k- a ia e case), he flag o useAllSubse s should be used ca e ully. I is mo e ad isable o con ol his wi h he a gumen nSubse sUsed. Raise his alue oge he wi h sigmaLog10Dec o mo e p ecise alues, lowe hem o as e esul s. The dynamics o he e olu iona y algo i hm a e con olled ia he pa ame e s sigmaIni , sigmaAda and adaFac o . All hese ake con ol o e he a iance adjus men s o he mu a- ion ec o . The pa ame e sigmaIni se s he ini ial a iance o he mu a ion, he se ings o sigmaAda con ol a e how many mu a ion s eps he mu a ion a iance is adjus ed and 32 OjaNP: Compu ing he Oja Median in R 5. Conclusions The e a e many di e en mul i a ia e medians. In his pape we explained how he di e en medians ex end di e en p ope ies o he uni a ia e median o he mul i a ia e case. The Oja median has e y con incing s a is ical p ope ies, bu is also among he compu a ionally mo e challenging ones. We desc ibed he Rpackage OjaNP, which p o ides ou di e en algo i hms o i s compu a ion. Along wi h he concep o he Oja median comes he no ion o Oja signs and anks and mul i a ia e sca e es ima o s based upon hem. The package p o ides also unc ions o hese use ul ools, which can hen be used o obus mul i a ia e in e en ial p ocedu es. As examples, we desc ibed and implemen ed he one-sample and he C-sample loca ion es based on Oja signs and anks and showed hei p ac ical use in simple and complex da a si ua ions. Acknowledgmen s The wo k o Klaus No dhausen was suppo ed by he Academy o Finland (g an 268703). Oleksii Poko ylo is suppo ed by he Cologne G adua e School o Managemen , Economics and Social Sciences. The wo k o Daniel Vogel was suppo ed by he DFG collabo a e esea ch g an SFB 823. The au ho s wish o acknowledge CSC – IT Cen e o Science, Finland, o compu a ional esou ces. Re e ences A cones MA, Chen Z, Gine E (1994). “Es ima o s Rela ed o U-P ocesses wi h Applica ions o Mul i a ia e Medians: Asymp o ic No mali y.” The Annals o S a is ics,22(3), 1460– 1477. doi:10.1214/aos/1176325637. Babu GJ, Rao CR (1988). “Join Asymp o ic Dis ibu ion o Ma ginal Quan iles and Quan ile Func ions in Samples om a Mul i a ia e Popula ion.” Jou nal o Mul i a ia e Analysis, 27(1), 15–23. doi:10.1016/0047-259x(88)90112-1. Bai ZD, He X (1999). “Asymp o ic Dis ibu ions o he Maximal Dep h Es ima o s o Reg ession and Mul i a ia e Loca ion.” The Annals o S a is ics,27(5), 1616–1637. doi: 10.1214/aos/1017939144. Chen Z (1995). “Robus ness o he Hal -Space Median.” Jou nal o S a is ical Planning and In e ence,46(2), 175–181. doi:10.1016/0378-3758(94)00105-5. Donoho D, Gasko M (1992). “B eakdown P ope ies o Loca ion Es ima es Based on Hal - Space Dep h and P ojec ed Ou lyingness.” The Annals o S a is ics,20(4), 1803–1827. doi:10.1214/aos/1176348890. Filzmose P, F i z H, Kalche K (2018). pcaPP: Robus PCA by P ojec ion Pu sui .Rpackage e sion 1.9-73, URL h ps://CRAN.R-p ojec .o g/package=pcaPP. Fische D, Mosle K, Mö önen J, No dhausen K, Poko ylo O, Vogel D (2020). OjaNP: Mul i a ia e Me hods Based on he Oja Median and Rela ed Concep s.Rpackage e sion 1.0-0, URL h ps://CRAN.R-p ojec .o g/package=OjaNP. Jou nal o S a is ical So wa e 33 Genes M, Masse JC, Plan e JF (2019). dep h: Dep h Func ions Tools o Mul i a ia e Analysis.Rpackage e sion 2.1-1.1, URL h ps://CRAN.R-p ojec .o g/package=dep h. Hay o d J (1902). “Wha Is he Cen e o an A ea o he Cen e o a Popula ion.” Jou nal o he Ame ican S a is ical Associa ion,8(58), 47–58. doi:10.2307/2276137. He manspe ge TP, McKean JW (2011). Robus Nonpa ame ic S a is ical Me hods. 2nd edi ion. CRC P ess, Boca Ra on. He manspe ge TP, Mö önen J, Oja H (1997). “A ine-In a ian Mul i a ia e One-Sample Signed-Rank Tes s.” Jou nal o he Ame ican S a is ical Associa ion,92(440), 1591–1600. doi:10.1080/01621459.1997.10473681. He manspe ge TP, Mö önen J, Oja H (1999). “The Geome y o he A ine In a ian Mul i a ia e Sign and Rank Me hods.” Jou nal o Nonpa ame ic S a is ics,11(1–3), 271– 285. doi:10.1080/10485259908832784. He manspe ge TP, Mö önnen J, Oja H (1998). “A ine In a ian Mul i a ia e Rank Tes s o Se e al Samples.” S a is ica Sinica,8, 785–800. He manspe ge TP, Nyblom J, Oja H (1994). “A ine In a ian Mul i a ia e One-Sample Sign Tes s.” Jou nal o he Royal S a is ical Socie y B,56(1), 221–234. doi:10.1111/j. 2517-6161.1994. b01973.x. He manspe ge TP, Oja H (1994). “A ine In a ian Mul i a ia e Mul isample Sign Tes s.” Jou nal o he Royal S a is ical Socie y B,56(1), 235–249. doi:10.1111/j.2517-6161. 1994. b01974.x. Ho elling H (1929). “S abili y in Compe i ion.” The Economic Jou nal,39(153), 41–57. doi:10.2307/2224214. Koenke R (2019). quan eg: Quan ile Reg ession.Rpackage e sion 5.54, URL h p: //CRAN.R-p ojec .o g/package=quan eg. Mosle K, Poko ylo O (2015). “Compu a ion o he Oja Median by Bounded Sea ch.” In K No dhausen, S Taskinen (eds.), Mode n Nonpa ame ic, Robus and Mul i a ia e Me h- ods, pp. 185–203. Sp inge -Ve lag. Mö önen J, No dhausen K, Oja H (2010). “Asymp o ic Theo y o he Spa ial Median.” In J An och, M H˘usko á, PK Sen (eds.), Nonpa ame ics and Robus ness in Mode n S a is ical In e ence and Time Se ies Analysis: A Fes sch i in Hono o P o esso Jana Ju ecko á, olume 7, pp. 182–193. Niinimaa A (1995). “Bi a ia e Gene aliza ions o he Median.” In EM Tii , T Kollo, H Niemi (eds.), Mul i a ia e S a is ics and Ma ices in S a is ics, pp. 163–180. VSP BV, Zeis . Niinimaa A, Oja H (1995). “On he In luence Func ions o Ce ain Bi a ia e Medians.” Jou nal o he Royal S a is ical Socie y B,57(3), 565–574. doi:10.1111/j.2517-6161. 1995. b02048.x. Niinimaa A, Oja H, Nyblom J (1992). “Algo i hm AS 277: The Oja Bi a ia e Median.” Jou nal o he Royal S a is ical Socie y C,41(3), 611–633. doi:10.2307/2348099. 34 OjaNP: Compu ing he Oja Median in R Niinimaa A, Oja H, Tableman M (1990). “The Fini e-Sample B eakdown Poin o he Oja Bi a ia e Median and o he Co esponding Hal -Samples Ve sion.” S a is ics & P obabili y Le e s,10(4), 325–328. doi:10.1016/0167-7152(90)90050-h. No dhausen K, Mö önen J, Oja H (2018a). MNM: Mul i a ia e Nonpa ame ic Me hods. An App oach Based on Spa ial Signs and Ranks.Rpackage e sion 1.0-3, URL h ps: //CRAN.R-p ojec .o g/package=MNM. No dhausen K, Oja H (2011). “Mul i a ia e L1Me hods: The Package MNM.” Jou nal o S a is ical So wa e,43(5), 1–28. doi:10.18637/jss. 043.i05. No dhausen K, Oja H (2018). “Robus Nonpa ame ic In e ence.” Annual Re iew o S a is ics and I s Applica ion,5(1), 473–500. doi:10.1146/annu e -s a is ics-031017-100247. No dhausen K, Oja H, Tyle DE (2008). “Tools o Explo ing Mul i a ia e Da a: The Package ICS.” Jou nal o S a is ical So wa e,28(6), 1–31. doi:10.18637/jss. 028.i06. No dhausen K, Si kiä S, Oja H, Tyle DE (2018b). ICSNP: Tools o Mul i a ia e Nonpa a- me ics.Rpackage e sion 1.1-1, URL h ps://CRAN.R-p ojec .o g/package=ICSNP. Oja H (1983). “Desc ip i e S a is ics o Mul i a ia e Dis ibu ions.” S a is ics & P obabili y Le e s,1(6), 327–332. doi:10.1016/0167-7152(83)90054-8. Oja H (1999). “A ine In a ian Mul i a ia e Sign and Rank Tes s.” Scandina ian Jou nal o S a is ics,26(3), 319–343. doi:10.1111/1467-9469.00152. Oja H (2010). Mul i a ia e Nonpa ame ic Me hods wi h R. An App oach Based on Spa ial Signs and Ranks. Sp inge -Ve lag, New Yo k. Oja H (2013). “Mul i a ia e Median.” In C Becke , R F ied, S Kuhn (eds.), Robus ness and Complex Da a S uc u es. Fes sch i in Honou o U sula Ga he , pp. 3–16. Sp inge - Ve lag, Be lin. Oja H, Niinimaa A (1985). “Asymp o ic P ope ies o he Gene alized Median in he Case o Mul i a ia e No mali y.” Jou nal o he Royal S a is ical Socie y B,47(2), 372–377. doi:10.1111/j.2517-6161.1985. b01366.x. Ollila E, C oux C, Oja H (2004). “In luence Func ion and Asymp o ic E iciency o he A ine Equi a ian Rank Co a iance Ma ix.” S a is ica Sinica,14(1), 297–316. Ollila E, Oja H, C oux C (2003). “The A ine Equi a ian Sign Co a iance Ma ix: Asymp o ic Beha io and E iciencies.” Jou nal o Mul i a ia e Analysis,87(2), 328–355. doi:10.1016/ s0047-259x(03)00045-9. Pu i ML, Sen PK (1971). Nonpa ame ic Me hods in Mul i a ia e Analysis. John Wiley & Sons, New Yo k. RCo e Team (2019). R: A Language and En i onmen o S a is ical Compu ing.RFounda- ion o S a is ical Compu ing, Vienna, Aus ia. URL h ps://www.R-p ojec .o g/. Romanazzi M (2001). “In luence Func ion o Hal space Dep h.” Jou nal o Mul i a ia e Analysis,77(1), 138–161. doi:10.1006/jm a.2000.1929. Jou nal o S a is ical So wa e 35 Ronkainen T, Oja H, O ponen P (2003). “Compu a ion o he Mul i a ia e Oja Median.” In R Du e , P Filzmose , U Ga he , PJ Rousseeuw (eds.), De elopmen s in Robus S a is ics: P oceedings o he In e na ional Con e ence on Robus S a is ics (ICORS’01, S i Vo au, Aus ia, July 2001), pp. 344–359. Sp inge -Ve lag, Be lin Heidelbe g. Shen G (2008). “Asymp o ics o Oja Median Es ima e.” S a is ics & P obabili y Le e s, 78(14), 2137–2141. doi:10.1016/j.spl.2008.02.004. Sie e C, Pa me C, Hocking T, Chambe lain S, Ram K, Co ellec M, Despouy P (2019). plo ly: C ea e In e ac i e Web G aphics ia plo ly.js.Rpackage e sion 4.9.1, URL h ps: //CRAN.R-p ojec .o g/package=plo ly. Small CG (1990). “A Su ey o Mul idimensional Medians.” In e na ional S a is ical Re iew, 58(3), 263–277. doi:10.2307/1403809. S ein P (1966). “A No e on he Volume o a Simplex.” The Ame ican Ma hema ical Mon hly, 73(3), 299–301. doi:10.2307/2315353. Tukey JW (1975). “Ma hema ics and he Pic u ing o Da a.” In P oceedings o he In e na- ional Cong ess o Ma hema icians, olume 2, pp. 523–531. Vancou e . Visu i S, Koi unen V, Oja H (2000). “Sign and Rank Co a iance Ma ices.” Jou nal o S a- is ical Planning and In e ence,91(2), 557–575. doi:10.1016/s0378-3758(00)00199-3. Visu i S, Ollila E, Koi unen V, Mö önen J, Oja H (2003). “A ine Equi a ian Mul i a ia e Rank Me hods.” Jou nal o S a is ical Planning and In e ence,114(1–2), 161–185. doi: 10.1016/s0378-3758(02)00469-x. Vogel D, F ied R (2008). “Es ima ing Pa ial Co ela ions Using he Oja Sign Co a iance Ma ix.” In P B i o (ed.), COMPSTAT 2008 – P oceedings in Compu a ional S a is ics, olume II, pp. 721–729. Physica-Ve lag, Heidelbe g. Vogel D, F ied R (2011). “Ellip ical G aphical Modelling.” Biome ika,98(4), 935–951. doi:10.1093/biome /as 037. Vogel D, Köllmann C, F ied R (2008). “Pa ial Co ela ion Es ima es Based on Signs.” In J Heikkonen (ed.), P oceedings o he 1s Wo kshop on In o ma ion Theo e ic Me hods in Science and Enginee ing. TICSP Se ies # 43. Webe A (1909). Übe den S ando de Indus ien. Moh , Tübingen. Webe A (1929). Theo y o he Loca ion o Indus ies. The Uni e si y o Chicago P ess, Chicago. 36 OjaNP: Compu ing he Oja Median in R A ilia ion: Daniel Fische Na u al Resou ces Ins i u e Finland (Luke) P oduc ion Sys ems Jokioinen, Finland and School o Heal h Sciences Uni e si y o Tampe e Tampe e, Finland E-mail: [email p o ec ed] Jou nal o S a is ical So wa e h p://www.js a so .o g/ published by he Founda ion o Open Access S a is ics h p://www. oas a .o g/ Feb ua y 2020, Volume 92, Issue 8 Submi ed: 2016-05-06 doi:10.18637/jss. 092.i08 Accep ed: 2018-09-06