IEEE Trans Image Process. 2015 Aug;24(8):2382-92. doi: 10.1109/TIP.2015.2401511. Epub 2015 Feb 6.
In this paper, we propose an efficient semidefinite programming (SDP) approach to worst case linear discriminant analysis (WLDA). Compared with the traditional LDA, WLDA considers the dimensionality reduction problem from the worst case viewpoint, which is in general more robust for classification. However, the original problem of WLDA is non-convex and difficult to optimize. In this paper, we reformulate the optimization problem of WLDA into a sequence of semidefinite feasibility problems. To efficiently solve the semidefinite feasibility problems, we design a new scalable optimization method with a quasi-Newton method and eigen-decomposition being the core components. The proposed method is orders of magnitude faster than standard interior-point SDP solvers. Experiments on a variety of classification problems demonstrate that our approach achieves better performance than standard LDA. Our method is also much faster and more scalable than standard interior-point SDP solvers-based WLDA. The computational complexity for an SDP with m constraints and matrices of size d by d is roughly reduced from O(m(3)+md(3)+m(2)d(2)) to O(d(3)) (m>d in our case).
本文提出了一种有效的半定规划（SDP）方法来解决最坏情况线性判别分析（WLDA）问题。与传统的 LDA 相比，WLDA 从最坏情况的角度考虑降维问题，通常更适合分类。然而，原始的 WLDA 问题是非凸的，难以优化。在本文中，我们将 WLDA 的优化问题重新表述为一系列半定可行性问题。为了有效地解决半定可行性问题，我们设计了一种新的可扩展优化方法，以拟牛顿法和特征分解为核心组件。与标准内点 SDP 求解器相比，我们的方法快了几个数量级。在各种分类问题上的实验表明，我们的方法比标准的 LDA 性能更好。与基于标准内点 SDP 求解器的 WLDA 相比，我们的方法也更快、更具可扩展性。对于一个具有 m 个约束和大小为 d 乘 d 的矩阵的 SDP，其计算复杂度从大约 O(m(3)+md(3)+m(2)d(2)) 降低到 O(d(3))（在我们的情况下 m>d）。
