No. 898

Title:

A New Computational Approach to Density Estimation with Semidefinite Programming

Author(s):

Tadayoshi, Fushiki (The Institute of Statistical Mathematics);
Shingo, Horiuchi (Access Network Service Systems Laboratories);
Takashi, Tsuchiya (The Institute of Statistical Mathematics)

Key words:

Abstract:

Denisity estimation is a classical and important problem in statistics. The aim of this paper is to develop a new computational approach to density estimation based on semidefinite programming (SDP), a new technology developed in optimization in the last decade. We express a density as the product of a nonnegative polynomial and a base density such as normal districution, exponential distribution and uniform distribution. The difficult nonnegativity constraint imposed on the polynomial is expressed as a semidefinite constraint. Under the condition that the base density is specified, the maximum likelihood estimation of the coefficients of the polynomial is formulated as a variant of SDP which can be solved in polynomial-time with the recently developed interior-point methods. Since the base density typically contains just one or two parameters, if the likelihood function is easily maximized with respect to the polynomial part by SDP, then it is possible to compute the global maximum of the likelihood function by further maximizing the partially-maximized likelihood function with respect to the base density parameter. The primal-dual interior-point algorithms are used to solve the variant of SDP. The proposed model is flexible enough to express such properties as unimodality and symmetry which would be reasonably imposed on the density function. AIC (Akaike information criterion) is used to choose the best model. Through applications to several instances we demonstrate flexibility of the model and performance of the proposed procedure.