Worst Case Linear Discriminant Analysis as Scalable Semidefinite Feasibility Problems

DOI10.1109/TIP.2015.2401511zbMATH Open1408.94372DBLPjournals/tip/LiSHS15OpenAlexW2024731863WikidataQ86714758 ScholiaQ86714758MaRDI QIDQ4612902FDOQ4612902

Authors: Hui Li, Chunhua Shen, Anton van den Hengel, Qinfeng Shi 

Publication date: 31 January 2019

Published in: IEEE Transactions on Image Processing (Search for Journal in Brave)

Abstract: 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 quasi-Newton methods and eigen-decomposition being the core components. The proposed method is orders of magnitude faster than standard interior-point based 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 $mathcalO(m^3+m{d}^3+m^2{d}^2)$ to $mathcalO(d^3)$ ($m>d$ in our case).

Full work available at URL: https://arxiv.org/abs/1411.7450

Mathematics Subject Classification ID

Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

This page was built for publication: Worst Case Linear Discriminant Analysis as Scalable Semidefinite Feasibility Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4612902)