Classification of sparse high-dimensional vectors

DOI Web Site Web Site 1 Citations
  • Yuri I. Ingster
    St. Petersburg State Electrotechnical University, 5 Prof. Popov Street, 197376 St. Petersburg, Russia
  • Christophe Pouet
    LATP, University of Provence, 39 rue F. Joliot-Curie, 13453 Marseille Cedex 13, France
  • Alexandre B. Tsybakov
    Laboratoire de Statistique, CREST, Timbre J340, 3 avenue Pierre Larousse, 92240 Malakoff Cedex, France

Description

<jats:p> We study the problem of classification of <jats:italic>d</jats:italic> -dimensional vectors into two classes (one of which is ‘pure noise’) based on a training sample of size <jats:italic>m</jats:italic> . The main specific feature is that the dimension <jats:italic>d</jats:italic> can be very large. We suppose that the difference between the distribution of the population and that of the noise is only in a shift, which is a sparse vector. For Gaussian noise, fixed sample size <jats:italic>m</jats:italic> , and dimension <jats:italic>d</jats:italic> that tends to infinity, we obtain the sharp classification boundary, i.e. the necessary and sufficient conditions for the possibility of successful classification. We propose classifiers attaining this boundary. We also give extensions of the result to the case where the sample size <jats:italic>m</jats:italic> depends on <jats:italic>d</jats:italic> and satisfies the condition <jats:inline-formula> <jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="RSTA20090156IM1.gif" /> </jats:inline-formula> , 0 ≤ γ < 1, and to the case of non-Gaussian noise satisfying the Cramér condition. </jats:p>

Journal

Citations (1)*help

See more

Keywords

Report a problem

Back to top