Sparse linear discriminant analysis by thresholding for high dimensional data

Jun Shao; Yazhen Wang; Xinwei Deng; Sijian Wang

Source-linked AI summary

Sparse linear discriminant analysis by thresholding for high dimensional data

Jun Shao, Yazhen Wang, Xinwei Deng, Sijian Wang

arXiv:1105.3561v1May 18, 2011math.ST

TL;DR

High-dimensional classification is difficult when the feature dimension exceeds the training sample size, and standard LDA may perform poorly. The paper proposes thresholding-based sparse LDA, establishing asymptotic optimality under sparsity and dimension-growth conditions. Numerical studies include leukemia data with 7,129 genes and 72 patients, where SLDA improves on LDA.

Problem
Classification must estimate a rule from training data when the feature distribution is unknown, while standard LDA may perform poorly when variables greatly outnumber samples.
Method
The paper proposes sparse LDA using thresholding estimators for mean effects and covariance structure within the linear discriminant rule.
Results
SLDA is asymptotically optimal under stated sparsity and dimension-growth conditions; in the leukemia analysis, it reduces LDA’s misclassification rate by nearly 70%.
Takeaways & Limitations
Sparse estimation can support high-dimensional classification while retaining effects mediated through correlations among variables.
Takeaways & Limitations
The nonnormal extension does not establish the same optimality result directly; the paper instead studies distributions satisfying a specified form or condition.

Abstract

from arXiv · show

In many social, economical, biological and medical studies, one objective is to classify a subject into one of several classes based on a set of variables observed from the subject. Because the probability distribution of the variables is usually unknown, the rule of classification is constructed using a training sample. The well-known linear discriminant analysis (LDA) works well for the situation where the number of variables used for classification is much smaller than the training sample size. Because of the advance in technologies, modern statistical studies often face classification problems with the number of variables much larger than the sample size, and the LDA may perform poorly. We explore when and why the LDA has poor performance and propose a sparse LDA that is asymptotically optimal under some sparsity conditions on the unknown parameters. For illustration of application, we discuss an example of classifying human cancer into two classes of leukemia based on a set of 7,129 genes and a training sample of size 72. A simulation is also conducted to check the performance of the proposed method.

1. Introduction.

Classification must learn a rule from training data when the feature distribution is unknown, a challenge intensified when variables greatly outnumber samples. The paper develops sparse LDA to address high-dimensional classification while retaining correlation information.

Problem: Unknown feature distributions require classification rules to be constructed from training samples rather than directly using the optimal rule.The objective is to approach the optimal rule’s misclassification rate using observed training data.
Problem: When p greatly exceeds n, high-dimensional classification becomes more difficult because uncertainty increases while the training sample cannot grow as quickly as the feature dimension.The paper identifies this as the large-p-small-n or ultra-high dimension problem.
Application: 7,129 genes and 72 patients define the paper’s leukemia example, illustrating classification in an ultra-high-dimensional biomedical setting.The example concerns distinguishing acute myeloid leukemia from acute lymphoblastic leukemia.
LDA limitations: LDA remains asymptotically optimal when p grows more slowly than √n, but can become as poor as random guessing when p exceeds n.The paper uses these contrasting regimes to motivate a sparse alternative.
Proposed approach: The proposed sparse LDA thresholds mean effects and covariance estimates, allowing more than n nonzero estimates rather than selecting fewer than n variables.This preserves correlation-mediated classification effects that feature selection or independence-based methods may miss.

2. The optimal rule and linear discriminant analysis.

The paper defines optimal classification under a two-class normal model and evaluates LDA through conditional misclassification rates. It shows that LDA can fail as dimension grows, including when covariance is known, motivating sparsity in both mean differences and covariance estimation.

Model and optimal rule: Under the two-class normal model, the optimal rule classifies using δ′Σ^-1(x−μ̄), while misclassification averages the two class-specific error probabilities.The model assumes a common positive-definite covariance matrix.
Performance criterion: Conditional misclassification rate averages classification errors over a new observation given the training sample, providing the paper’s main asymptotic performance criterion.The unconditional rate is its expectation over training samples.
LDA construction: LDA uses sample mean differences, the pooled sample midpoint, and an inverse or generalized inverse sample covariance matrix in its discriminant rule.The generalized inverse is used when the ordinary inverse does not exist, such as when p > n.
LDA behavior: When p > n and p/n diverges, LDA’s unconditional misclassification rate converges to 1/2, making it asymptotically worst.The value 1/2 corresponds to random guessing.
Implication: Asymptotically optimal classification in the high-dimensional regime therefore requires sparsity conditions on both the covariance matrix Σ and mean difference δ.The paper presents this requirement after showing that even known parameters may not make dense LDA optimal.

3. Sparse linear discriminant analysis.

The paper constructs a sparse LDA by thresholding estimates of the covariance matrix and mean difference, and establishes conditions under which its asymptotic performance is optimal or sub-optimal. These conditions depend on dimensionality, covariance and mean sparsity, signal strength, and threshold selection.

Sparse linear discriminant analysis: Covariance sparsity is measured by Ch,p, with Ch,p much smaller than p indicating many zero or small covariance entries.When h = 0, C0,p is the maximum number of nonzero entries in a covariance row; examples include Ch,p = O(1) and O(log p).
Sparse linear discriminant analysis: Mean-difference sparsity is measured by Dg,p, and bounded Dg,p implies bounded ∆p for g ∈[0,1).The paper also notes that ∆p^2 is no larger in order than Dg,p.
Sparse linear discriminant analysis: The SLDA thresholds covariance and mean-difference estimates before applying the LDA rule.The covariance estimator thresholds sample covariance entries, while the mean-difference estimator retains components exceeding a threshold.
Sparse linear discriminant analysis: When ∆p is bounded and the stated regularity and sparsity conditions hold, the SLDA is asymptotically optimal.The result is obtained under conditions involving Ch,p, Dg,p, qn, and the divergence rate of p.
Sparse linear discriminant analysis: When ∆p →∞, the SLDA is asymptotically sub-optimal, but it becomes asymptotically optimal if bn∆p^2 →0.The paper gives these as separate sufficient regimes for diverging signal strength.
Sparse linear discriminant analysis: The threshold constants M1 and M2 can be selected by leave-one-out cross-validation that minimizes an estimated SLDA misclassification rate.The resulting cross-validation estimate can also estimate the SLDA misclassification rate.

4. Extensions.

The paper extends sparse LDA beyond the two-class normal setting to nonnormal distributions and three or more classes, while identifying conditions and unresolved technical limits.

Nonnormal distributions: For elliptical distributions, the known-parameter LDA remains optimal, motivating analysis of whether SLDA approaches this benchmark when parameters are unknown.The paper includes multivariate t and double-exponential distributions as special cases of the elliptical form.
Nonnormal distributions: Relaxing normality requires revisiting covariance consistency, auxiliary lemmas, the optimal-rate expression, and a key lemma used in the SLDA proof.The paper identifies these four normality-dependent components explicitly.
Nonnormal distributions: Under suitable tail or projection conditions, several normal-theory results extend, with n^-1 log p replaced by n^-1p4/ν under the second condition.The projection condition uses a symmetric distribution function Ψ independent of the unit vector l and covers elliptical and scale-mixture distributions.
Nonnormal distributions: Theorem 4 establishes an extension when the stated conditions hold and the threshold-related quantities a_n and b_n converge to zero.The theorem defines b_n according to the applicable condition and requires a_n →0 and b_n →0.
Three or more classes: For K ≥3 classes, SLDA replaces each pairwise mean difference and covariance estimate with their thresholded versions, using one common threshold for computational simplicity.The multiclass construction is based on pairwise differences δ_kl and corresponding thresholding estimators.
Three or more classes: Multiclass asymptotic optimality follows under the stated convergence conditions when pairwise optimal misclassification probabilities do not converge to zero; vanishing rates remain future work.The authors state that convergence-rate proofs require an extension of a lemma for multivariate normal distributions, alongside further empirical study.

5. Numerical studies.

Numerical studies evaluate SLDA on leukemia gene-expression data and simulations, showing sparse thresholding can improve classification relative to LDA and SCRDA.

ALL and AML classification uses 7,129 genes from 72 patients, with 47 ALL and 25 AML cases.
The first 1,000 ordered components of the estimated mean difference contribute nearly 98% of the cumulative proportion.
Only 0.45% of the 25,407,756 off-diagonal covariance values range from 0.35 to 9.7 after ignoring a factor of 10^8; the rest are below 0.35.
Cross-validation selects M1 = 107 and M2 = 300, yielding 2,492 nonzero mean-difference components and 227,083 nonzero covariance elements.
The leukemia leave-one-out error is 0.0972 for LDA, while SLDA reduces it by nearly 70%; FAIR ranges from 5% to 7% and is larger than SLDA.
In simulation, SLDA's unconditional misclassification rate is 0.069 versus 0.152 for LDA, 0.137 for SCRDA, and 0.03 for the optimal rule.
Under a t-distribution with 3 degrees of freedom, simulated unconditional misclassification rates are 0.059 for SLDA, 0.194 for SCRDA, and 0.399 for LDA.

6. Proofs.

The proofs establish how LDA behaves as dimension grows and support sparse discriminant analysis through probabilistic control of estimated quantities.

Theorem 1: The proof controls the maximum entrywise covariance-estimation error using a probabilistic bound from Bickel and Levina (2008).
Theorem 2: If p/(p/n) →0, the relevant quantity converges to 0 and the LDA conditional misclassification rate converges to 1/2.
Theorem 2: When p/(p/n) →0 and the signal diverges, LDA's conditional error converges to a constant between 0 and 1/2, while its ratio to the optimal rate diverges.
Theorem 2: When p/n →∞, LDA's conditional misclassification rate converges to 0 while its ratio to the optimal rate diverges to ∞.
Theorem 3: The SLDA analysis relates sparse mean estimation and covariance estimation through quadratic-form approximations involving the thresholded quantities.

C1 C12 C′

This proof segment bounds cross-block contributions and uses eigenvalue assumptions to control the sparse discriminant analysis quadratic forms.

The matrices Σ1, ˜Σ1, C1, and ˜C1 are q_n × q_n matrices, with q_n defined in Lemma 2(ii).
A cross-block term is rewritten as ˇδ′1 ˜C1ξ1 − ˇδ′1 ˜Σ−1_1 ˜Σ12 ˜C2ξ0.
Cauchy–Schwarz bounds the squared cross term by OP(q_n/n)(˜δ′˜Σ−1˜δ).
Under condition (2), eigenvalues of submatrices of Σ and Σ−1 are bounded by c0, enabling repeated matrix-norm bounds.
The proof concludes that the relevant quadratic-form approximation holds, and the remaining theorem parts follow as in Theorem 1 with s_n replaced by b_n.