Optimization Online


A New Computational Approach to Density Estimation with Semidefinite Programming

Tadayoshi Fushiki (fushiki***at***ism.ac.jp)
Shingo Horiuchi (hor***at***ansl.ntt.co.jp)
Takashi Tsuchiya (tsuchiya***at***sun312.ism.ac.jp)

Abstract: Density 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 distribution, 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. Akaike information criterion (AIC) is used to choose the best model. Through applications to several instances we demonstrate flexibility of the model and performance of the proposed procedure.

Keywords: density estimation, semidefinite programming, maximum likelihood estimation, AIC, statistics

Category 1: Applications -- Science and Engineering (Statistics )

Category 2: Applications -- Science and Engineering (Data-Mining )

Category 3: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Research Memorandum No. 898, The Institute of Statistical Mathematics, 4-6-7 Minami-Azabul, Minato-ku, Tokyo, 106-8569, Japan, Novermber 2003.

Download: [Postscript][PDF]

Entry Submitted: 11/29/2003
Entry Accepted: 11/30/2003
Entry Last Modified: 12/19/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society