Abstract
The trace quotient problem arises in many applications in pattern classification and computer vision, e.g., manifold learning, low-dimension embedding, etc. The task is to solve a optimization problem involving maximizing the ratio of two traces, i.e., max W Tr(f(W))/Tr(h(W)). This optimization problem itself is non-convex in general, hence it is hard to solve it directly. Conventionally, the trace quotient objective function is replaced by a much simpler quotient trace formula, i.e., \(\max_W {\bf Tr} ({h(W)}^{-1}{f(W)})\), which accommodates a much simpler solution. However, the result is no longer optimal for the original problem setting, and some desirable properties of the original problem are lost.
In this paper we proposed a new formulation for solving the trace quotient problem directly. We reformulate the original non-convex problem such that it can be solved by efficiently solving a sequence of semidefinite feasibility problems. The solution is therefore globally optimal. Besides global optimality, our algorithm naturally generates orthonormal projection matrix. Moreover it relaxes the restriction of linear discriminant analysis that the projection matrix’s rank can only be at most c − 1, where c is the number of classes. Our approach is more flexible. Experiments show the advantages of the proposed algorithm.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Yan, S., Tang, X.: Trace quotient problems revisited. In: Leonardis, A., Bischof, H., Pinz, A. (eds.) ECCV 2006. LNCS, vol. 3951, pp. 232–244. Springer, Heidelberg (2006)
Ye, J., Xiong, T.: Null space versus orthogonal linear discriminant analysis. In: Proc. Int. Conf. Mach. Learn., Pittsburgh, Pennsylvania, pp. 1073–1080 (2006)
Overton, M.L., Womersley, R.S.: On the sum of the largest eigenvalues of a symmetric matrix. SIAM J. Matrix Anal. Appl. 13(1), 41–45 (1992)
Overton, M.L., Womersley, R.S.: Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices. Math. Program 62, 321–357 (1993)
Borchers, B.: CSDP, a C library for semidefinite programming. Optim. Methods and Software 11, 613–623 (1999)
Sturm, J.F.: Using SeDuMi 1.02, a matlab toolbox for optimization over symmetric cones (updated for version 1.05). Optim. Methods and Software 11-12, 625–653 (1999)
Xing, E., Ng, A., Jordan, M., Russell, S.: Distance metric learning, with application to clustering with side-information. In: Proc. Adv. Neural Inf. Process. Syst., MIT Press, Cambridge (2002)
Weinberger, K.Q., Blitzer, J., Saul, L.K.: Distance metric learning for large margin nearest neighbor classification. In: Proc. Adv. Neural Inf. Process. Syst. (2005)
Globerson, A., Roweis, S.: Metric learning by collapsing classes. In: Proc. Adv. Neural Inf. Process. Syst. (2005)
Newman, D., Hettich, S., Blake, C., Merz, C.: UCI repository of machine learning databases (1998)
Simard, P., LeCun, Y., Denker, J.S.: Efficient pattern recognition using a new transformation distance. In: Proc. Adv. Neural Inf. Process. Syst., pp. 50–58. MIT Press, Cambridge (1993)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shen, C., Li, H., Brooks, M.J. (2007). A Convex Programming Approach to the Trace Quotient Problem. In: Yagi, Y., Kang, S.B., Kweon, I.S., Zha, H. (eds) Computer Vision – ACCV 2007. ACCV 2007. Lecture Notes in Computer Science, vol 4844. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-76390-1_23
Download citation
DOI: https://doi.org/10.1007/978-3-540-76390-1_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-76389-5
Online ISBN: 978-3-540-76390-1
eBook Packages: Computer ScienceComputer Science (R0)