FastNMF: Efficient NMF Algorithm for Reducing Feature Dimension

FastNMF: Efficient NMF Algorithm for Reducing Feature Dimension

Le Li (Tsinghua University, China), Le Li (Tsinghua University, China), Yu-Jin Zhang (Tsinghua University, China) and Yu-Jin Zhang (Tsinghua University, China)
Copyright: © 2011 |Pages: 27
DOI: 10.4018/978-1-61520-991-0.ch008

Abstract

Non-negative matrix factorization (NMF) is a more and more popular method for non-negative dimensionality reduction and feature extraction of non-negative data, especially face images. Currently no NMF algorithm holds not only satisfactory efficiency for dimensionality reduction and feature extraction of face images but also high ease of use. To improve the applicability of NMF, this chapter proposes a new monotonic, fixed-point algorithm called FastNMF by implementing least squares error-based non-negative factorization essentially according to the basic properties of parabola functions. The minimization problem corresponding to an operation in FastNMF can be analytically solved just by this operation, which is far beyond existing NMF algorithms’ power, and therefore FastNMF holds much higher efficiency, which is validated by a set of experimental results. For the simplicity of design philosophy, FastNMF is still one of NMF algorithms that are the easiest to use and the most comprehensible. Besides, theoretical analysis and experimental results also show that FastNMF tends to extract facial features with better representation ability than popular multiplicative update-based algorithms.
Chapter Preview
Top

Introduction

An essential and important problem in signal processing, pattern recognition, computer vision and image engineering is how to find a suitable representation of multivariate data, which typically make latent structure in the data clear and often reduce the dimensionality of the data so that further computation or classification can be effectively and efficiently implemented.

Principal component analysis (Jolliffe, 2002), projection pursuit (Jones, 1987), factor analysis (Reyment, 1996), redundancy reduction (Deco, 1995), and independent component analysis (Hyvärinen, 2001) are some popular data representation methods. Although they are essentially differentiated, they all produce negative descriptive components (that is to say, subtractive representations are allowable) and linearly implement dimensionality reduction. Different from them, a new method called non-negative matrix factorization (NMF) is proposed by Lee and Seung in Nature (Lee, 1999). It makes all representation components non-negative (in other words, only purely additive representations are allowable) and nonlinearly implements dimensionality reduction.

Psychological and physiological evidence for NMF is that perception of the whole is based on perception of its parts (Palmer, 1977; Wachsmuth, 1994; Logothetis, 1996), which is compatible with the intuitive notion of combining parts to form a whole(Lee, 1999), and hence it grasps the essence of intelligent or biological data representation in some degree. Besides, NMF usually produces a sparse representation for input data, which has been shown to be a useful middle ground between a completely distributed representation and a unary representation (Field, 1994).

As a effective method of non-negative dimensionality reduction and feature extraction of non-negative data, NMF has been applied in several research fields, including text analysis(Lee, 1999), document clustering (Shahnaz, 2006), digital watermarking (Liu, 2006; Ouhsain, 2009), face analysis (Chen, 2001; Lee, 1999; Guillamet, 2002; Wang, 2006a), image retrieval (Liang, 2006), image de-convolution (Kopriva, 2006), language modeling (Stouten, 2007; Stouten, 2008), sound source classification (Cho, 2003), musical signal analysis (Benetos, 2006; Holzapfel, 2008), blind source separation (Cichocki, 2006a), network security (Guan, 2009), gene (Frigyesi, 2008) and cell (Kim, 2007) analysis and many others. Among them, face analysis is one of the earliest and most widely researched applications, and besides, non-negative dimensionality reduction and feature extraction of face images has been one of the basic experiments to show the performance of NMF algorithms (Chen, 2003;Lee, 1999; Wild, 2004).

Complete Chapter List

Search this Book:
Reset