We present an efficient global optimization algorithm for exponential family principal component analysis (PCA) and associated low-rank matrix factorization problems. Exponential family PCA has been shown to improve the results of standard PCA on non-Gaussian data. Unfortunately, the widespread use of exponential family PCA has been hampered by the existence of only local optimization procedures. The prevailing assumption has been that the non-convexity of the problem prevents an efficient global optimization approach from being developed. Fortunately, this pessimism is unfounded. We present a reformulation of the underlying optimization problem that preserves the identity of the global solution while admitting an efficient optimization procedure. The algorithm we develop involves only a sub-gradient optimization of a convex objective plus associated eigenvector computations. (No general purpose semidefinite programming solver is required.) The lowrank constraint is exactly preserved, while the method can be kernelized through a consistent approximation to admit a fixed non-linearity. We demonstrate improved solution quality with the global solver, and also add to the evidence that exponential family PCA produces superior results to standard PCA on non-Gaussian data.

46th Annual Allerton Conference on Communication, Control, and Computing
School of Computer Science

Guo, Y, & Schuurmans, D. (Dale). (2008). Efficient global optimization for exponential family PCA and low-rank matrix factorization. In 46th Annual Allerton Conference on Communication, Control, and Computing (pp. 1100–1107). doi:10.1109/ALLERTON.2008.4797683