Worst case linear discriminant analysis as scalable semidefinite feasibility problems.

Area of Science:

• Machine Learning
• Optimization
• Pattern Recognition

Background:

• Traditional Linear Discriminant Analysis (LDA) is sensitive to noise and outliers.
• Worst-Case Linear Discriminant Analysis (WLDA) offers improved robustness by considering worst-case scenarios.
• The non-convex nature of WLDA poses significant optimization challenges.

Purpose of the Study:

• To develop an efficient and scalable optimization method for WLDA.
• To reformulate the WLDA problem into a sequence of solvable semidefinite feasibility problems.
• To improve classification performance and computational efficiency over existing methods.

Main Methods:

• Reformulation of WLDA into a sequence of semidefinite feasibility problems.
• Development of a novel scalable optimization algorithm using quasi-Newton methods and eigen-decomposition.
• Comparison with standard LDA and interior-point SDP solvers for WLDA.

Main Results:

• The proposed method achieves significantly better classification performance than standard LDA.
• The new optimization approach is orders of magnitude faster than standard interior-point SDP solvers.
• Substantial reduction in computational complexity from O(m^3 + md^3 + m^2d^2) to O(d^3) for SDPs (where m > d).

Conclusions:

• The efficient SDP approach provides a scalable and effective solution for WLDA.
• The proposed method enhances classification robustness and computational speed.
• This work offers a significant advancement in optimizing and applying WLDA for real-world problems.