TEXT SIZE

search for



CrossRef (0)
Independence and maximal volume of d-dimensional random convex hull
Communications for Statistical Applications and Methods 2018;25:79-89
Published online January 31, 2018
© 2018 Korean Statistical Society.

Won Sona, Seongoh Parka, and Johan Lim1,a

aDepartment of Statistics, Seoul National University, Korea
Correspondence to: 1Corresponding author: Department of Statistics, Seoul National University, 1 Gwanak-ro, Gwanak-gu, Seoul 08826, Korea. E-mail: johanlim@snu.ac.kr
Received October 16, 2017; Revised December 19, 2017; Accepted December 20, 2017.
 Abstract

In this paper, we study the maximal property of the volume of the convex hull of d-dimensional independent random vectors. We show that the volume of the random convex hull from a multivariate location-scale family indexed by ∑ is stochastically maximized in simple stochastic order when ∑ is diagonal. The claim can be applied to a broad class of multivariate distributions that include skewed/unskewed multivariate t-distributions. We numerically investigate the proven stochastic relationship between the dependent and independent random convex hulls with the Gaussian random convex hull. The numerical results confirm our theoretical findings and the maximal property of the volume of the independent random convex hull.

Keywords : convex hull, independence, multivariate location-scale family, simple stochastic order, stochastic geometry
1. Introduction

Random convex hull, the convex hull of independent and identically distributed random points, have been studied for decades after the seminal work by Rényi and Sulanke (1963, 1964). In particular, researchers in stochastic geometry focus on the functionals of random convex hull (where the two most important functionals are the volume and number of faces) and investigate their finite and asymptotic properties.

The random convex hull is also employed in many multivariate statistical procedures. For example, Barnett (1976) defines an ordering of the multivariate data based on the notion of convex hull peeling depth. In Cook (1979), the random convex hull generated by the data points is used to identify the influential observations in linear regression. It is also used to find an optimal classifier in machine learning literature (Fawcett and Niculescu-Mizil, 2007; Lim and Won, 2012; Son et al., 2015). Ng et al. (2014) recently developed an efficient algorithm to simulate a random convex hull on a plane, and applied it to testing the independence of a d-dimensional random vector. They consider the use of the area (volume) of the convex hull for testing independence. However, no statistical justification is given for the use of the volume of the convex hull.

In this paper, we are interested in the maximal property of the volume of the convex hull of d-dimensional random vectors under independence. This paper argues that “the volume of the random convex hull of d-dimensional vectors Xi=(Xi1,Xi2,,Xid)T, i = 1, 2, …, n, is maximized in simple stochastic order (defined later) when Xi1,Xi2,,Xid are independent (or uncorrelated) to each other.” We show the claim is true for a broad class of multivariate distributions indexed by covariance matrix ∑ which includes skewed/unskewed multivariate t-distributions.

The remainder of the paper is organized as follows. In Section 2, we introduce general notations to be used in the paper. In addition, we show the invariance of the volume of the random convex hull with respect to rotational and axis-scalable transformations. We also introduce multivariate location-scale (MLS) family indexed by ∑, denoted by MLS(∑), which is invariant to the two transformations above. In Section 3, we prove the maximal property of the random convex hull under independence when the random vectors are from a distribution in MLS(∑). We then discuss the Gaussian random convex hull as an illustrative example and provide numerical illustrations of the results in the section. Finally, in Section 4, we conclude the paper with a discussion on the extension of the results to serially correlated data.

2. Preliminaries

2.1. Notation

Suppose we consider n data points in ℛd with d ≥ 1. The convex hull of the data points x1, x2, …, xn is defined as

chull(x1,x2,,xn):={i=1nαixi|i=1nαi=1,αi0,i=1,2,,n}.

A vertex of a convex set S ⊂ ℛd is a point x which cannot be written as a convex combination of the points in S {x}. The vertexes of the convex hull chull(x1, x2, …, xn) are elements of the set {x1, …, xn} and forms the vertexes of the convex hull denoted by V = {v1, v2, …, vK} (for some Kn). Finally, we find that chull(x1, x2, …, xn) equals to the polytope with vertexes v1, v2, …, vK which is denoted as pt(v1, v2, …, vK).

2.2. Multivariate location-scale family indexed by ∑

In this section, we introduce the MLS family that we assume for the distribution of random vectors in the paper.

The MLS family is one of the important parametric families and many important distributions are included in location-scale family. The family {P(μ,∑) : μ ∈ ℛd, ∑ ∈ ℳd} is defined to be a location-scale family on ℛd if

P(μ,Σ)(B)=G(Σ-12(B-μ)),         BBd,

where G(·) is an arbitrary given probability measure on the d-dimensional Borel field, ∑−1/2(Bμ) = {∑−1/2(xμ) : xB ⊂ ℛd}, and ℳd is a collection of d × d symmetric positive definite matrices (Shao, 2003).

Some examples of the MLS family are as follows. Elliptically symmetric distributions (or simply elliptical distributions) belong to a location-scale family (Ollila et al., 2003). A d-dimensional random vector X is said to have an elliptical distribution, denoted by X ~ ECd(μ, ∑, ξ), if it has a stochastic representation

X=μ+ξΣ12U,

where U is a random vector uniformly distributed on the unit sphere in ℛd, ξ ≥ 0 is a scalar random variable independent of U, and ∑1/2 is a deterministic symmetric matrix such that ∑1/2(∑1/2)T = ∑. There are many subclasses of elliptical distributions. Multivariate normal distributions, multivariate t-distributions, logistic distributions and multivariate Cauchy distributions are well-known examples of them (Fang et al., 1990). While the underlying population distributions are free of the assumption of symmetry, some distributions are also included in the MLS family. Multivariate Pareto of the second type (Asimit et al., 2010), a generalized multivariate gamma distributions (Carpenter and Diawara, 2007), and multivariate skew normal distributions and multivariate skew t-distributions (Azzalini and Capitanio, 2003) are examples of asymmetric distributions which can be classified as the MLS family. Some further extensions can also be found from Zhao and Kim (2016).

In this paper, we assume μ = 0 without loss of generality, and index the MLS family with the covariance matrix ∑. In sequel, we simply write the MLS family indexed by ∑ as MLS(∑) omitting the distribution notation of ξ of (2.3). Further, we let λjs for j = 1, 2, …, d be the eigenvalues of the covariance matrix ∑.

2.3. Vertex invariance to rotation and scale transformation

Let us consider n independent random samples Xi=(Xi1,Xi2,,Xid)T, i = 1, 2, …, n, which are identically from the d-dimensional multivariate distribution with mean 0 and covariance matrix ∑. Let v.chull(X1, X2, …, Xn) be the volume of chull(X1, X2, …, Xn).

The following lemma shows that the vertex set of chull(X1, X2, …, Xn) is invariant to both rotation and scale (according to the axis) transformations of {Xi, i = 1, 2, …, n}.

Lemma 1

Let P be a d-dimensional orthonormal matrix and Q be the diagonal matrix with diagonal elements q1, q2, …, qd. If V = {v1, v2, …, vK} is the set of the vertexes of chull(X1, X2, …, Xn), then (i) the vertexes of chull(PX1, PX2, …, PXn) is PV = {Pv1, Pv2, …, PvK} and (ii) the vertex set of chull(QX1, QX2, …, QXn) is QV = {Qv1, Qv2, …, QvK}.

Proof

The proof of (ii) is very similar to that of (i). Thus, we only prove (i) at here.

We first show that Pvk is a vertex of chull(PX1, PX2, …, PXn). Suppose, without loss of generality, Pvk = PX1 and assume it is not a vertex. Then, it can be written as a convex combination of PX2, PX3, …, PXn as

PX1=i=2nαiPXi,         i=2nαi=1,αi0.

By multiplying PT in both sides of the above, we have

νk=X1=i=2nαiXi,         i=2nαi=1,αi0,

which implies vk is not a vertex of chull(X1, X2, …, Xn). This introduces a contradiction.

We now show that any point in chull(PX1, PX2, …, PXn) has a convex representation of PV = {Pv1, Pv2, …, PvK}. Suppose y is a vertex of the convex hull but not in PV. Since it is within a convex hull, it can be written as

y=i=1nαiPXi,         αi0,i=1nαi=1.

Again, by multiplying PT both sides,

PTy=i=1nαiXi=k=1Kβkνk,         αi0,i=1nαi=1   and   βk0,k=1Kβk=1,

where the second equation is from that V = {v1, v2, …, vK} is the vertex set of chull(X1, X2, …, Xn). In the above, the last equation

PTy=k=1Kβkνk,         βk0,k=1Kβk=1,

is equivalent to

y=k=1KβkPνk,         βk0,k=1Kβk=1,

which contradicts to that y is a vertex not in PV.

3. Maximal volume of random convex hull of samples from MLS(∑)

3.1. Main result

We now present our main results of the paper which show the volume of the convex hull of a MLS(∑) is stochastically maximized when true covariance matrix ∑ is diagonal, equivalently, X1, X2, …, Xd are uncorrelated to each other. If the data are from a multivariate normal distribution, the volume is maximized when the d-variables are independent. The stochastic order between two variables X and Z is defined as: Z is (simply) stochastically larger than X, denoted by XstZ if and only if P(Za) ≤ P(Xa) for every a ∈ ℛ.

Theorem 1

SupposeX1, X2, …, Xn are independently from a distribution from a MLS with covariance matrix, MLS(∑), andZ1, Z2, …, Zn are independently from MLS(diag(∑)), where diag(∑) is the diagonal matrix whose diagonal elements are same with those of. Then, for every n and a positive definite covariance matrix, we have

v.chull(X1,X2,,Xn)stv.chull(Z1,Z2,,Zn).
Proof

Suppose V = {v1, v2, …, vK} is the set of vertexes of chull(X1, X2, …, Xn) and let the singular value decomposition of ∑ be PT ΛP with an orthonormal matrix P and Λ = diag(λ1, λ2,, λd).

v.chull(X1,X2,,Xn)=I(xchull(X1,X2,,Xn))dx=I(ychull(PX1,PX2,,PXn))·det(PT)dy=I(ypt(Pν1,Pν2,,PνK))·1dy,

which is from the rotation transformation y = PTx (equivalently, Py = x) and the invariance from Lemma 1. In (3.2), pt(Pv1, Pv2, …, PvK) equals to chull(PX1, PX2, …, PXn), where Yi = PXi are independently and identically distributed (iid) as MLS(Λ). Thus,

(3.2)=I(ychull(Y1,Y2,Yn))dy=v.chull(Y1,Y2,Yn).

We now show that v.chull(Y1, Y2, …, Yn) is stochastically smaller than v.chull(Z1, Z2, …, Zn). This is simply by applying the axis-wise scale transformation to both chull(Y1, Y2, …, Yn) and chull (Z1, Z2, …, Zn). First, for chull(Y1, Y2, …, Yn), we consider the transformation matrix QY = Λ−1/2 and have

v.chull(Y1,Y2,,Yn)=I(ychull(Y1,Y2,,Yn))dy=I(uchull(QYY1,QYY2,,QYYn))·det(QY-1)du=(j=1dλj)12v.chull(U1.y,U2.y,,Un.y),

where Ui.y are iid from MLS(Id) with Id is the d-dimensional identity matrix. In showing (3.3), we use the invariance property proven in (ii) of Lemma 1 as in (3.2). The similar steps are applied to chull(Z1, Z2, …, Zn) with the scale transformation QZ = {diag(∑)}−1/2, and show that

v.chull(Z1,Z2,,Zn)=(j=1dσjj)12v.chull(U1.z,U2.z,,Un.z),

where σj j is the jth diagonal element of ∑ and Ui.z are iid from MLS(Id).

Finally, we conclude the proof using the Hadamard’s inequality (Cover and Gamal, 1983), which tells, for the covariance matrix ∑,

(j=1dλj)=det(Σ)(j=1dσjj).
3.2. Gaussian random convex hull

The Gaussian random convex hull, the random convex hull for d-dimensional Gaussian random vectors, is studied by many researchers. Suppose Z1, Z2, …, Zn are iid from the d-dimensional standard normal distribution. It is shown by Affentranger (1991) that

E{v.chull(Z1,Z2,,Zn)}=κd(2log n)d2(1+o(1))={πd2Γ(d2+1)}(2log n)d2(1+o(1)),

where κd is the volume of the d-dimensional unit ball. It is also shown by Hug and Reitzner (2005) that, for d ≥ 1,

var{v.chull(Z1,Z2,,Zn)}=O((log n)d-32).

However, Hug (2013) points out that the explicit finite sample distribution function is still unknown. Instead, some of its asymptotic are known. For example, Bárány and Vu (2007) prove the central limit theorem for the volume of the Gaussian random convex hull.

Theorem 1 in Section 3 further shows that, for the general ∑, the volume has a constant multiplicative factor (j=1dλj)1/2 which is canceled out from numerator and denominator of its standardized form. The standardized statistic

tv.chull=v.chull(X1,X2,,Xn)-E(v.chull(X1,X2,,Xn))var(v.chull(X1,X2,,Xn))

is invariant to the scale transformation and has the same distribution with

tv.chull=v.chull(Z1,Z2,,Zn)-E(v.chull(Z1,Z2,,Zn))var(v.chull(Z1,Z2,,Zn))

where E(v.chull(Z1, Z2, …, Zn)) and var(v.chull(Z1, Z2, …, Zn)) are those in (3.6) and (3.7), respectively.

3.3. Numerical illustration

We now numerically illustrates the findings in the previous subsection. The identity (3.3) tells that

v.chull(X1,X2,,Xn)=(j=1dλj)12v.chull(Z1,Z2,,Zn),

where Xis are from the multivariate normal distribution with mean 0 and variance ∑, Zis are iid d-dimensional standard normal vector, and λj, j = 1, 2, …, d, are the eigenvalues of ∑. Thus,

Δ=log v.chull(X1,X2,,Xn)-12log(j=1dλj)

has the same distribution with

log v.chull(Z1,Z2,,Zn),

and is invariant to the choice of ρ for fixed d and n. We numerically investigate this identity.

We generate samples from d-dimensional multivariate t-distribution with degrees of freedom ν = 3, 5, 10,∞(∞ corresponds to the multivariate normal distribution), μ = 0d, and two types of ∑ defined below with the dimension d = 2, 4. Two covariance matrices we consider are: (i) the compound symmetry (CS) matrix, notated as CS(ρ), is defined as

Σcs=(1-ρ)Id+ρ1d1dT

and its log-determinant is log det(CS(ρ)) = log{1 + (d − 1)ρ} + (d − 1) log(1 − ρ), (ii) the first order auto-regressive (AR) model, notated as AR1(ρ), is defined as

Σar=(σij=ρi-j,i,j=1,2,,(d-1)),

and its log-determinant is log det(AR1(ρ)) = (d − 1) log(1 − ρ2). The sample size is set as n = 50, 100, 300, 500. We simulate B = 1000 data sets and, in each data, we compute the area of the convex hull. To compute the area of the convex hull, we use the “convhulln” function in the R-package “geometry”, which implements the Quickhull algorithm (Barber et al., 1996).

The box plots of Δ=log v.chull(X1,X2,,Xn)-(1/2)log(j=1dλj) versus ρ for fixed ν, n are presented in Figures 14 for each combination of d = 2, 4 and ∑ = ∑cs, ∑ar. The figures show that the distribution of Δ is invariant to the choice of ρ for given ν and n in every combination of d = 2, 4 and ∑ = ∑cs, ∑ar. In each figure, the four box plots in each panel has the same distribution as the distribution of log v.chull(Z1, Z2, …, Zn). The mean of log v.chull(Z1, Z2, …, Zn) therefore varies according to the changes of ν and n; it tends to increase as either ν decreases or n increases.

4. Conclusion

In this paper, the maximal property of the volume of the convex hull of d-dimensional independent random vectors is investigated. In stochastic sense, the volume of the convex hull is maximized when the covariance matrix ∑ of the underlying probability distribution is diagonal. This results is true for the distribution from the multivariate location-scale family that includes skewed/unskewed multivariate t-distribution and elliptical distribution. Thus, the volume of the convex hull can be used for testing the independence of a d-dimensional vector as in Ng et al. (2014).

Possible future research direction is to extend this conclusion to the random convex hull from dependent samples including time series data. In time series data, the lagged plot, the plot (yt, yt−1, …, ytd+1), …, (ytd+1, ytd, …, yt−2d), plays an important role in exploring the data. In particular, the convex hull of the data points in the lagged plot is a key tool to find outliers and influential points. However, its theoretical property is rarely understood and further study on it is demanded.

Figures
Fig. 1. d = 2 and 닊 = 닊ar: Box plots of for different choices of , , and n. AR = auto-regressive.
Fig. 2. d = 4 and 닊 = 닊ar: Box plots of for different choices of , 館 and n. AR = auto-regressive.
Fig. 3. d = 2 and 닊 = 닊cs: Box plots of for different choices of , 館 and n. CS = compound symmetry.
Fig. 4. d = 4 and 닊 = 닊cs: Box plots of for different choices of , 館 and n. CS = compound symmetry.
References
  1. Affentranger, F (1991). The convex hull of random points with spherically symmetric distributions. Rendiconti del Seminario Matematico Universit횪 e Politecnico di Torino. 49, 359-383.
  2. Asimit, AV, Furman, E, and Vernic, R (2010). On a multivariate Pareto distribution. Insurance: Mathematics and Economics. 46, 308-316.
  3. Azzalini, A, and Capitanio, A (2003). Distributions generated by perturbation of symmetry with emphasis on a multivariate skew t-distribution. Journal of the Royal Statistical Society. Series B (Statistical Methodology). 65, 367-389.
    CrossRef
  4. B찼r찼ny, I, and Vu, V (2007). Central limit theorems for Gaussian polytopes. The Annals of Probability. 35, 1593-1621.
    CrossRef
  5. Barber, CB, Dobkin, DP, and Huhdanpaa, H (1996). The Quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software (TOMS). 22, 469-483.
    CrossRef
  6. Barnett, V (1976). The ordering of multivariate data. Journal of the Royal Statistical Society. Series A (General). 139, 318-355.
    CrossRef
  7. Carpenter, M, and Diawara, N (2007). A multivariate gamma distribution and its characterizations. American Journal of Mathematical and Management Sciences. 27, 499-507.
    CrossRef
  8. Cook, RD (1979). Influential observations in linear regression. Journal of the American Statistical Association. 74, 169-174.
    CrossRef
  9. Cover, T, and Gamal, AE (1983). An information - theoretic proof of Hadamard셲 inequality (Corresp). IEEE Transactions on Information Theory. 29, 930-931.
    CrossRef
  10. Fang, KT, Kotz, S, and Ng, KW (1990). Symmetric Multivariate and Related Distributions. Boston: MA Springer US
    CrossRef
  11. Fawcett, T, and Niculescu-Mizil, A (2007). PAV and the ROC convex hull. Machine Learning. 68, 97-106.
    CrossRef
  12. Hug, D (2013). Random polytopes. Stochastic Geometry, Spatial Statistics and Random Fields, Lecture Notes in Mathematics, Spodarev, E, ed. Berlin-Heidelberg: Springer-Verlag, pp. 205-238
    CrossRef
  13. Hug, D, and Reitzner, M (2005). Gaussian polytopes: variances and limit theorems. Advances in Applied Probability. 37, 297-320.
    CrossRef
  14. Lim, J, and Won, JH (2012). ROC convex hull and nonparametric maximum likelihood estimation. Machine Learning. 88, 433-444.
    CrossRef
  15. Ng, CT, Lim, J, Lee, KE, Yu, D, and Choi, S (2014). A fast algorithm to sample the number of vertexes and the area of the random convex hull on the unit square. Computational Statistics. 29, 1187-1205.
    CrossRef
  16. Ollila, E, Oja, H, and Croux, C (2003). The affine equivariant sign covariance matrix: asymptotic behavior and efficiencies. Journal of Multivariate Analysis. 87, 328-355.
    CrossRef
  17. R챕nyi, A, and Sulanke, R (1963). 횥ber die konvexe H체lle von n zuf채llig gew채hlten Punkten. Zeitschrift F체r Wahrscheinlichkeitstheorie und Verwandte Gebiete. 2, 75-84.
    CrossRef
  18. R챕nyi, A, and Sulanke, R (1964). 횥ber die konvexe H체lle von n zuf채llig gew채hlten Punkten. Zeitschrift F체r Wahrscheinlichkeitstheorie Und Verwandte Gebiete. 3, 138-147.
    CrossRef
  19. Shao, J (2003). Mathematical Statistics. New York: Springer
    CrossRef
  20. Son, W, Ng, CT, and Lim, J (2015). A new integral representation of the coverage probability of a random convex hull. Communications of Statistical Applications and Methods. 22, 69-80.
    CrossRef
  21. Zhao, J, and Kim, HM (2016). Power t distribution. Communications for Statistical Applications and Methods. 23, 321-334.
    CrossRef