High dimensional quadratic discriminant analysis: Optimality and phase transitions

Suppose (Xi∈Rp,yi) comes from a two-class Gaussian mixture model, where Xi∼N(μyi,Σyi) and yi∈{0,1}, 1≤i≤n. The goal is to estimate the class label Y for a new observation X. When the mean vector μyi and the covariance matrix Σyi depend on the class label yi, the quadratic discriminant analysis (QDA) algorithm leverages both the covariance and mean to achieve better classification results. However, QDA faces both theoretical and computational challenges in the high-dimensional setting that p»n. In this paper, we propose two high-dimensional QDA algorithms: QDAw and QDAfs. When the non-zeros in μ0−μ1 are weak and moderately dense, the QDAw algorithm with an unbiased factor in the classification rule works well. When the non-zeros in μ0−μ1 are sparse and moderately strong, the QDAfs algorithm with a thresholding step should be used. By modeling the sparsity and strength of non-zero entries in Σ0−1−Σ1−1 and μ0−μ1, the upper bounds of QDAw and QDAfs meet the lower bounds of the classification problem on the 4-dimensional parameter space, which proves the optimality of the algorithms. Our theory is supported by real data analysis results.