A Direct Estimation Approach to Sparse Linear Discriminant Analysis

Tony Cai; Weidong Liu

Source-linked AI summary

A Direct Estimation Approach to Sparse Linear Discriminant Analysis

Tony Cai, Weidong Liu

arXiv:1107.3442v1Jul 18, 2011stat.MEmath.ST

TL;DR

High-dimensional sparse discriminant analysis is difficult because standard and separate-parameter approaches face unstable covariance estimation and can perform poorly. The paper directly estimates Ωδ with constrained ℓ1 minimization to form the linear programming discriminant (LPD) rule. LPD supports approximate sparsity, has computational advantages, and shows favorable theoretical and empirical performance.

Problem
High-dimensional classification challenges standard LDA and separate estimation because covariance estimates can be singular, biased, or unstable.
Method
The LPD rule directly estimates Ωδ through constrained ℓ1 minimization and implements the resulting classifier using linear programming.
Results
LPD significantly outperforms alternative methods in average misclassification rate and performs favorably on lung cancer and leukemia datasets.
Takeaways & Limitations
Approximate sparsity of Ωδ allows LPD to perform well even when Ω is not sparse or cannot be consistently estimated.
Takeaways & Limitations
The compared independence rule ignores correlations between variables and can be inefficient.

Abstract

from arXiv · show

This paper considers sparse linear discriminant analysis of high-dimensional data. In contrast to the existing methods which are based on separate estimation of the precision matrix $Ø$ and the difference $\de$ of the mean vectors, we introduce a simple and effective classifier by estimating the product $Ø\de$ directly through constrained $\ell_1$ minimization. The estimator can be implemented efficiently using linear programming and the resulting classifier is called the linear programming discriminant (LPD) rule. The LPD rule is shown to have desirable theoretical and numerical properties. It exploits the approximate sparsity of $Ø\de$ and as a consequence allows cases where it can still perform well even when $Ø$ and/or $\de$ cannot be estimated consistently. Asymptotic properties of the LPD rule are investigated and consistency and rate of convergence results are given. The LPD classifier has superior finite sample performance and significant computational advantages over the existing methods that require separate estimation of $Ø$ and $\de$. The LPD rule is also applied to analyze real datasets from lung cancer and leukemia studies. The classifier performs favorably in comparison to existing methods.

1 Introduction

High-dimensional classification makes standard LDA unreliable because covariance estimation becomes unstable or impossible. The paper introduces LPD, which directly estimates Ωδ and achieves favorable theoretical, computational, and empirical properties.

Existing sparse discriminant methods commonly estimate Ω and δ separately before plugging them into Fisher’s rule.
When p/(n1 + n2) →∞, standard LDA can be no better than random guessing because the sample covariance matrix is singular.
The Fisher discriminant depends on Ω and δ only through their product Ωδ, motivating direct estimation of that product.
The LPD rule estimates Ωδ through constrained ℓ1 minimization, uses linear programming, and is data-driven and easy to implement.Its computational advantage comes from estimating a p-dimensional vector rather than the inverse of a p×p covariance matrix.
LPD performs well when Ωδ is approximately sparse, even when Ω is not sparse or cannot be consistently estimated.This assumption is weaker and more flexible than requiring both Ω and δ to be sparse.
Simulations show superior finite-sample performance and significantly lower average misclassification rates than several alternative classifiers.Applications to lung cancer and leukemia datasets also show favorable comparisons with existing methods.

2 Classification via direct estimation of Ωδ

The paper proposes estimating β*=Ωδ directly with constrained ℓ1 minimization, yielding the linear programming discriminant (LPD) rule. This targets the quantity Fisher’s rule uses and requires weaker sparsity assumptions than separately estimating Ω and δ.

The LPD rule has theoretical, numerical, and computational advantages over methods that separately estimate Ω and δ.Separate estimation involves p^2/2 parameters for Ω and δ, compared with p parameters in their product.
Fisher’s rule depends on the precision matrix Ω and mean difference δ through their product Ωδ.
The proposed estimator exploits approximate sparsity of Ωδ rather than requiring both Ω and δ to be sparse.The paper states that Ωδ sparsity does not require Ω itself to be sparse and is a weaker, more flexible condition.
The constrained optimization can be formulated as a linear program, producing the classifier called the Linear Programming Discriminant (LPD).
β*=Ωδ is estimated by replacing Σ and δ in Σβ−δ=0 with their sample versions and seeking a sparse solution using ℓ1 minimization.The ℓ1 formulation is a convex relaxation of ℓ0 minimization and accounts for variability in the sample quantities.
Direct estimation can remain accurate even when Ω cannot be estimated consistently, because the method only requires Ωδ to be approximately sparse.

3 Asymptotic properties

The asymptotic analysis studies the LPD rule’s misclassification rate relative to the Bayes rate under high-dimensional assumptions. It establishes consistency and convergence results when Ωδ is sparse or approximately sparse, while identifying boundaries imposed by signal strength and comparability of settings.

If ∆p tends to zero, even the oracle rule is no better than random guessing.
The LPD rule is consistent when Ωδ is sparse under high-dimensional regularity conditions.The stated conditions include comparable sample sizes, bounded covariance eigenvalues, and a separation quantity ∆p bounded away from zero.
Direct estimation does not require a consistent spectral-norm estimate of Ω or Σ to achieve the asymptotically optimal misclassification rate.The paper contrasts this requirement with the consistent estimation of Ω required by Shao et al. (2011).
Approximate sparsity with many small entries is allowed under a sparsity condition on Ωδ.
A larger ∆p produces a worse convergence rate for the relative classification error Rn/R.The paper explains that large ∆p can make the Bayes error very small, making it harder for a data-driven rule to match.
Under a comparable setting with Σ=Ip×p, the LPD rule outperforms the SLDA rule in the stated asymptotic regime.The paper cautions that direct comparison requires matching assumptions, including sparsity of both Σ and Ω.

4 Extensions

The paper extends its theoretical results beyond Gaussian data to elliptical distributions satisfying specified tail and moment conditions. The extended results preserve consistency and convergence conclusions under these assumptions.

The non-Gaussian extension considers elliptical distributions with standardized, symmetric components and zero mean and unit variance.The paper notes that elliptical distributions and multivariate scale mixtures of normals satisfy the stated symmetry condition.
The extension imposes either sub-Gaussian-type or polynomial-type tail conditions.These are given as conditions (C3) and (C4), respectively.
Theorem 5 extends the consistency and convergence results by replacing normality with elliptical distributions satisfying (C3) or (C4).
Theorem 4’s result also remains valid under elliptical distributions satisfying the specified tail conditions.The paper does not restate the result in this section.

5 Numerical Investigation

The numerical investigation evaluates LPD through implementation details, simulations, support recovery, tuning selection, and lung cancer and leukemia applications. Across simulated and real datasets, LPD generally achieves favorable classification performance and directly estimates a sparse Ωδ.

5.1 Implementation of LPD: LPD is implemented by solving a constrained ℓ1 minimization problem that can be recast as a linear program.The optimization is convex and can be solved with primal-dual interior-point or other first-order methods.
5.1 Implementation of LPD: The direct estimation approach has substantially lower computational cost than estimating the precision matrix, with separate precision-matrix estimation costing p times more.This comparison is made for methods such as Yuan’s estimator and CLIME.
5.1 Implementation of LPD: The tuning parameter λ is selected empirically by cross-validation using subgroup-based validation sets.The final choice is the value maximizing the cross-validation score.
5.2 Simulation results: Under multivariate t5 sampling, classification errors increase for all methods, but LPD remains close to the oracle in Model 1 and significantly outperforms the other methods.The comparison includes OFAIR, NSC, SLD, Naive-LDA, and GLDA.
5.2 Simulation results: LPD recovers more than 8 nonzero Ωδ elements under normal sampling and more than 7 under t5 sampling on average, with low false-positive rates.The simulations use n1 = n2 = 200 training and test samples across three covariance models.

6 Discussions

The LPD rule directly estimates Ωδ for high-dimensional sparse discriminant analysis, exploiting its approximate sparsity rather than separately estimating Ω and δ. The discussion argues that this approach can remain effective when conventional parameter estimation fails, while accounting for correlations and all features.

The LPD rule directly estimates the product Ωδ through constrained l1-minimization for high-dimensional sparse linear discriminant analysis.Its classifier is implemented through linear programming.
Approximate sparsity of Ωδ relaxes the conventional requirement that both Ω and δ be sparse.The paper notes that Ωδ may be estimable more efficiently than Ω.
The LPD rule can perform well even when Ω is not consistently estimable, a setting in which some conventional classification methods fail.This is particularly relevant in ultra-high-dimensional problems where estimating the full precision matrix may be difficult or impossible.
Theoretical results require conditions on |Ωδ|1 rather than |Ωδ|0, and simulations report that nearly all elements of Ωδ are nonzero in Models 1 and 2.Thus, the analysis supports approximate rather than exact sparsity of the discriminant direction.
The procedure extends to unequal class priors and multi-group classification by estimating the pairwise products Ωδkl with analogous linear programs.For unequal priors, the class-prior probabilities can also be estimated from class sample proportions.
Ignoring correlations or discarding features can produce inefficient classifiers, even when zero features are known and important features are selected correctly.The paper attributes this to correlations making nominally unimportant features useful for classification.

7 Proofs

The proofs establish concentration and feasibility results used to derive the LPD rule’s asymptotic guarantees. They combine exponential inequalities, high-probability bounds, and theorem-specific arguments.

Lemma 1 supplies an exponential inequality for independent mean-zero random variables under boundedness conditions.
Lemma 2 shows that the true Ωδ belongs to the feasible set of the linear program with high probability.Under conditions (C2) and (C3), the probability is greater than 1 − O(p^-1).
The proof bounds partial sums and sample quantities using auxiliary variables, truncation, and concentration inequalities.The argument under condition (C4) uses a truncation technique analogous to the cited prior work.
Theorem proofs combine feasibility and concentration bounds to establish the stated asymptotic results for the estimator and risk.For example, one derivation concludes that Rn = (1 + o(1))R.