Mutual neighbors and diagonal loading-based sparse locally linear embedding

ABSTRACT

In this study, a new Locally Linear Embedding (LLE) algorithm is proposed. Common LLE includes three steps. First, neighbors of each data point are determined. Second, each data point is linearly modeled using its neighbors and a similarity graph matrix is constructed. Third, embedded data are extracted using the graph matrix. In this study, for each data point mutual neighborhood conception and loading its covariance matrix diagonally are used to calculate the linear modeling coefficients. Two data points will be named mutual neighbors, if each of them is in the neighborhood of the other. Diagonal loading of the neighboring covariance matrix is applied to avoid its singularity and also to diminish the effect of noise in the reconstruction coefficients. Simulation results demonstrate the performance of applying mutual neighborhood conception and diagonal loading and their combination. Also, the results of applying the mutual neighborhood on Laplacian Eigenmap (LEM) demonstrate the good performance of the proposed neighbor selection method. Our proposed method improves recognition rate on Persian handwritten digits and face image databases.

Introduction

Many real data such as all types of images, speech signals and many other digital signals have high dimensionality to present. Investigation of these types of data is complicated and time-consuming. Therefore, dimensionality of these types of data needs to be reduced. Some applications of dimension reduction technique include data compression, decrease curse of dimensionality, de-noising and visualization.

In fact, most of data have an inherent dimensionality very lower than they are presented. It means data can be presented in a lower dimension space without losing major information. Figure 1 shows examples of three-dimensional data manifold that the inherent dimensionality of them is equal to two.

Figure 1. Examples of a three-dimensional manifold. Three-dimensional data (b) sampled from (a). (c) is two-dimensional data of sampled manifold (b).

Dimension reduction is a mapping from high-dimension data into inherent low-dimension data in such a way that neighbors of each data and pair distance of them are preserved. Suppose a data set where with data points are represented in a space with dimensionality. Dimension reduction methods attempt to extract the embedded low-dimensional data set Y = where and .

Related works

Dimension reduction methods

Dimension reduction methods can be categorized as unsupervised and supervised algorithms.

Most supervised methods are applied to classification. Therefore, dimension reduction process of these methods is based on earning the maximum ratio of between classes scattering to the within class scattering using supervision information. The most famous of supervised dimension reduction methods is Linear Decomposition Analysis (LDA) (Fukunaga 1990). There are many methods such as Kernel LDA (KLDA) (Mika et al. 1999), Margin Maximizing Discriminant Analysis (MMDA) (Kocsor, Kovács, and Szepesvári 2004), Learning with Side Information (LSI) (Xing et al. 2002), Relevant Component Analysis (RCA) (Shental et al. 2002), Information Theoretic Metric Learning (ITML) (Davis et al. 2007), Neighborhood Component Analysis (NCA) (Goldberger et al. 2004) and Average Neighborhood Margin Maximization (ANMM) (Wang and Zhang 2007). All aforementioned methods can be categorized as linear/nonlinear and local/global methods.

On the other hand, in many dimension reduction methods i.e. manifold learning methods, there is not any supervision on data. Also, unsupervised dimension reduction methods can be divided into linear and nonlinear methods. Principle Component Analysis (PCA) is the most famous linear method (Jolliffe 2002).

Many manifold learning methods have been proposed based on the different algorithms and objective functions, such as Kernel PCA (KPCA) (Schölkopf and Smola 2002), Locally Linear Embedding (LLE) (Roweis and Saul 2000), Laplacian Eigenmaps (LEM) (Belkin 2001), Maximum Variance Unfolding (MVU) (Weinberger, Sha, and Saul 2004), multidimensional scaling (MDS) (Cox and Cox 2000), Isomap (Tenenbaum, De Silva, and Langford 2000), Hessian LLE (HLLE) (Donoho and Grimes 2003), Local Tangent Space Analysis (LTSA) (Zhang and Zha 2004), manifold charting (Brand 2002) and Locally Linear Coordination (LLC) (Teh 2002). All of these methods attempt to preserve local/global structure of data in the low-dimensional space as the same as in the input space. Some supervised version of the mentioned methods have been proposed such as Supervised Locally Linear Embedding Projection (SLLEP) (Li and Zhang 2011) and Discriminant Kernel Locally Linear Embedding (DKLLE) (Zhao and Zhang 2012). Table 1 shows categorizations of all the aforementioned methods.

Table 1. List of dimension reduction methods and their categorization.

Method	Linear	Nonlinear	Supervised	Unsupervised	Local	Global
LDA	*		*			*
KLDA		*	*			*
MMDA	*		*			*
LSI	*		*			*
RCA	*		*			*
ITML	*		*			*
NCA	*		*		*
ANMM	*		*		*
PCA	*			*		*
KPCA		*		*		*
LLE		*		*	*
LEM		*		*	*
MVU		*		*		*
MDS		*		*		*
Isomap		*		*		*
HLLE		*		*	*
LTSA		*		*	*
LLC		*		*	*	*

Dimension reduction would play a main role in many applications such as face recognition, action/behavior recognition, Optical Characteristic Recognition (OCR) etc. Since our main contribution is for OCR, we will give a short survey of researches conducted in this field.

OCR

In this study, we are interested in the offline Persian handwritten digits/characters recognition. OCR is a technique that converts the digital image and PDF format documents to searchable and editable documents. Machines enable to automatically recognize and separate check banks, bank statements, postal code, license plate etc. by OCR technique. OCR techniques are categorized into online and offline.

Many OCR methods have been proposed. In Sharma (2012) a new OCR method based on using support vector machine and neural network was proposed. In Álvarez, Fernández, and Sánchez (2012) and Ghaleb, George, and Mohammed (2013), two stroke-based methods were proposed. In Pradeep, Srinivasan, and Himavathi (2014), the performance of hybrid features for feed forward neural network-based English handwritten character recognition system was investigated. In Kacem, Aouïti, and Belaïd (2012), handwritten Arabic personal names have been recognized by structural feature extraction such as loops, stems legs and diacritics. In Yu and Jiao (2012), a new handwritten digit recognition method based on the distance kernel PCA was presented. In Singh and Lal (2014), digits have been recognized using a single layer neural network with PCA. In this method, features have been extracted by PCA to reduce the computing complexity and time-consuming. The introduced handwritten Persian/Arabic character recognition in (Shayegan and Chan 2012) is based on a new approach of feature selection. In this method, features have been selected based on one- and two-dimensional spectrum diagrams of the standard deviation and the minimum to maximum distributions.

All the aforementioned OCR methods are based on the feature extraction and feature selection. Most of the feature extraction and selection methods are heuristic and their performances are limited to a special database. Therefore, existence of a reliable OCR method, which is independent of database, is necessary. Manifold learning-based OCR can satisfy these conditions.

Paper contributions

The main motivation of this study is introducing of a new nonlinear unsupervised dimension reduction method to extract the inherent low-dimensional data from the high-dimensional data with preserving the input data structure.

Most of the mentioned dimension reductions methods are based on the construction of a neighborhood graph matrix. In LLE, after determining of neighbors for each data points, a matrix is constructed by the linear reconstruction coefficients of each data point based on its neighbors. Then the embedded structure has been extracted by these coefficients. In LEM, the same as LLE, a graph matrix is constructed based on the Laplacian equation and then the achieved weight matrix is applied on the cost function of LEM method. In Locality Preserving Projection (LPP), which is a linear approximation of LEM, the same as LEM, a graph matrix is constructed. In MDS and Stochastic Neighbor Embedding (SNE), firstly a distance matrix is calculated based on the distance of data points from each other. Then the embedded data are extracted by this matrix.

The supremacy of all the aforementioned methods depends on their graph matrices which can determine their manifold structure. In this study, we propose a new neighbors selection method. Then, these new neighbors construct a new graph matrix that can characterize the manifold structure more efficiently. Our proposed neighbors’ selection method is based on the mutual neighborhood concept. Details of the proposed method will be described in section III.

Another innovation is related to the method of calculating the graph matrix in LLE technique. In LLE, reconstruction coefficients of each data point have been calculated based on a closed-form solution. Then these coefficients are used for constructing the graph matrix of LLE. In our proposed method, we apply the diagonal loading technique in calculating the reconstruction coefficients of each data point.

We would apply our proposed dimension reduction method on both ORL face image (Samaria and Harter 1994) and isolated Persian handwritten digit databases (Mozaffari et al. 2006; Ziaratban, Faez, and Faradji 2007). Simulation results demonstrate the performance of applying the mutual neighborhood conception and diagonal loading alone and together.

Rest of the paper is organized as follows. LLE is described in section II. Details of our proposed modifications on LLE are presented in section III. Experimental results are given section IV. Finally, section V concludes the paper.

LLE

LLE is a locally nonlinear manifold learning method. In this method, the structure of data manifold is preserved by extracting high dimensionality local structure of each data point and trying to transfer these local structures into the low dimensionality representation. In LLE, each data point is modeled by its linear reconstruction coefficients based on its neighbors. In fact, the global structure of data is preserved by the combination of these local structure features.

LLE method extracts the embedded low dimension data in three steps: (1) neighbors of each data point are detected, (2) each data point in high dimensionality space is approximated based on the linear combination of its neighbors, and (3) the low-dimensional embedded manifold is extracted using the obtained coefficients of the linear combinations. Figure 2 shows these three steps.

Figure 2. Three steps of LLE algorithm (Roweis and Saul 2000).

Finding neighbors

Neighborhood definition and neighbors’ selection are the main parts of manifold learning methods. Proper selection of neighbors helps to better modeling of the local structure of a data manifold. Usually, neighbors of each data point are determined by one of two methods: k-nearest neighbors (k-NN) and ε-ball methods. Euclidian distance is a traditional distance metric. Also, some modifications of Euclidian distance and the other distance metrics such as geodesic distance can be applied.

Calculation of linear reconstruction coefficients

After finding each data point’s neighbors, the data point is modeled linearly by its neighbors. The achieved coefficients matrix, W, from this model which characterizes the local structure of the data manifold in high dimensionality can be determined as follows:

(1)

where is the index set of the neighbors of data point and s show the linear reconstruction coefficients of data point. These coefficients can be calculated in a closed form solution for each data point as follows:

Therefore, is calculated by Eq. (2) as:

(2)

where is the covariance matrix of’s neighbors, that they are centered to, and is a vector all of ones. If is not a member of neighborhood of, has to be set zero. Also, condition of is satisfied by dividing every on. After calculation of linear reconstruction coefficients of all data points, matrix is produced.

This matrix represents the local structure features of the data manifold. These coefficients are invariant to scaling and rotation because of Euclidean form of the cost function (Roweis and Saul 2000). Also, the calculated coefficients are invariant to translation since. Therefore, these coefficients can properly extract and preserve the local features of data manifold. Consequently, establishment of all these local structures preserves the global structure of data manifold.

Finding coordinates of the embedded data manifold

After local structure explanation of high-dimensional data, low-dimensional representation of data is generated using the calculated linear constraint coefficients and minimization of the cost function of Eq. (3):

(3)

The aforementioned minimization problem can be solved as an Eigen problem (Roweis and Saul 2000). Therefore, the cost function can be rewritten as follows:

(4)

where

Finally, d eigenvectors corresponding to d smallest nonzero eigenvalues of are d-dimensional representation of data.

LLE is used in many applications. In Wu et al. (2016), a voice conversion (VC) technique based on LLE was proposed. In this VC system spectral conversion part is based on the integration of LLE with a conventional exemplar-based spectral conversion. In Kang et al. (2017), LLE was applied on assessing the state of a rolling bearing. In this application, after frequency and time domain feature extraction, the dimensionality of the extracted features was reduced by LLE. In Ziemann and Messinger (2015), an adaptive LLE scheme was used for hyper spectral target detection. In this method, the target is separated from the background by graph theory modeling and then transferring by LLE into a low-dimensional coordinates. In Chen et al. (2016), a manifold preserving edit propagation method was presented based on the k-NN and LLE technique where each pixel is represented by LLE in feature space.

Proposed method: mutual neighborhood with diagonal loading

In this study, two novelties are proposed to improve the performance of LLE. First, a new notion of neighborhood is defined. Second, diagonal loading technique is applied to calculate the linear reconstruction coefficients of each data point based on its neighbors.

Mutual neighborhood

In LLE technique and the most of the other methods of manifold learning, first neighbors of data points are determined and then the remaining steps are done based on these neighbors. In LLE, after finding neighbors, each data point is modeled by its neighbors (Eq. (1)). The obtained coefficients of the models characterize the local structural of data manifold and then the embedded data manifold is extracted based on preserving these local structures (Eq. (4)). Determining the true neighbors leads to model of each data point that can better characterize the local structure. Therefore, finding the real and true neighbors of each data point is very important and critical.

k-NN is a common method for finding neighbors. This method selects k nearest data points as neighbors based on Euclidian distance metric for each data point. Usually, distribution of data points in manifold is not uniform. Also, noise disturbs the data distribution. Therefore, notice to selection of exactly k data points as neighbors, some data may be selected as neighbors while their distances are farther and very different from the other selected neighbors’ distance. It means these farther data points are not in true neighborhood. We propose a new algorithm to find neighbors, called mutual neighborhood, as follows:

Mutual neighborhood algorithm

In the proposed neighborhood definition, initially K neighbors of each data point are determined (, that is the index set of the k-NN of data point). Then K neighbors of each neighbors of, are detected. If is a neighbor of , will be selected as a true neighbor. We called them mutual neighbors. Otherwise, is removed from the list of the neighbors of . Also, all data points have to be connected by at least one neighbor until LLE is performed correctly. Therefore, in our proposed algorithm if all neighbors of are removed, the closest neighbor is selected as a true neighbor.

The proposed algorithm removes neighbors that are selected because of fixed number of neighbors and are not at a normal distance compared to the other neighbors. True selection of neighbors leads to have a better model from the local structure of data manifold and then it improves LLE performance. Figure 3 shows an example of our proposed neighborhood definition. Suppose we have 8 data points in two dimensions space and K of k-NN is 3. Table 2 shows neighbors of each data point based on mutual neighborhood definition and common k-NN.

Table 2. Comparison between mutual neighborhood method and k-nearest neighbors’ algorithm for data points in Figure 3.

Index of data point	k-nearest neighbors	Mutual neighbors
1	2, 3 and 4	2 and 3
2	1, 3 and 4	1, 3 and 4
3	1, 2 and 4	1, 2 and 4
4	2, 3 and 5	2, 3 and 5
5	2, 3 and 4	4
6	1, 7 and 8	7 and 8
7	2, 6 and 8	6 and 8
8	2, 6 and 7	6 and 7

Figure 3. An example of application of the proposed neighborhood definition for two-dimensional date points.

Based on the k-NN and mutual neighborhood conception, data points 1, 3 and 4 are selected as neighbors of data points 2. But selected neighbors for data point 7 are different. Based on the k-NN, data points 6, 8 and 2 are the three nearest neighbors of data points 7. But, based on mutual neighborhood conception, just data point 6 and 8 are selected as neighbors of data point 7, because data point 7 has not been selected as neighbors of data point 2.

Diagonal loading in LLE

In Ma and Goh (2003), diagonal loading technique was proposed to improve the performance of adaptive beamforming for case of small sample. In LLE, the linear reconstruction coefficients are calculated as a closed solution for each data point (Eq. (2)) based on a covariance matrix scheme. Noise and small number of samples cause to not having an accurate estimation of covariance matrix. We applied the diagonal loading technique to calculate these linear reconstruction coefficients. Therefore, Eq. (2) is rewritten as follows:

(5)

where is identity matrix and is the value of diagonal loading. In this study, the value of will be determined empirically.

Simulation results given in section IV demonstrate that mutual neighborhood conception, diagonal loading technique and their combination improve the performance of LLE based on the recognition rate of classification.

Formulation of our proposed method

Mutual neighborhood conception can be formulated as follows. After finding neighbors of each data point based on the k-NN’s algorithm, the cost function of the mutual neighbors LLE (MN-LLE) can be defined as follows:

(6)

Same as LLE, s are equal zero except s that s are members of neighbors set. Also, calculation of the linear reconstruction coefficients of each data point is related to the reconstruction coefficients of its neighbors because of. If was equal to zero, has to be removed from neighbors set. Also, is caused to each data point is at least connected to one neighbor. Therefore, mutual neighborhood conception is satisfied by this definition. Also, by definition of the mutual neighbors (MN) of as ,MN-LEM cost function can be defined as:

(7)

Diagonal loading technique can be modeled as follows. Comparing Eqs. (2) and (5), Eq. (5) is the optimum solution of the below minimization problem:

Therefore, our proposed method can be formulated as follows:

(8)

In comparison with Eq. (6), Eq. (8) involves adding a penalty term to the minimization problem in Eq. (6) in order to keep the coefficients away from reaching large values. Consequently, mutual neighborhood conception induces a sparser neighborhood graph matrix than the common graph matrix. In fact, Matrix of is sparser than the common LLE method; i.e. . Based on the definition of the mutual neighborhood conception, it is an obvious result.

Minimization problem given in Eq. (8) can be solved by the same way as LLE. First, mutual neighbors of each data point are determined and neighborhood graph matrix is constructed. Then matrix is calculated. Finally, the embedded data are extracted by solving an Eigen problem, the same as LLE.

Simulation and results

Simulation results are based on three databases: ORL face image database (Samaria and Harter 1994), isolated Persian handwritten digits (IPHD) database (Ziaratban, Faez, and Faradji 2007) and IFHCDB Persian handwritten database (Mozaffari et al. 2006).

In our experiments, high-dimensional data manifold is constructed by rearrangement of pixel intensity levels of each object image with sizes m and n to a vector . Performance of our proposed method is investigated based on recognition rate of classification. Each database is randomly divided into three parts: training, validation and test sets. The value of diagonal loading parameter, , is adjusted using validation set to provide the maximum recognition rate. Then the determined is applied to calculate the recognition rate for the test set. k-NN-based classifier is used in this study. In applied KNN classifier, if there are multiple classes most common among its k-NN for a test data point, it is assigned to one of them with the minimum average of Euclidian distance. The value of k of KNN classifier is set to 3 in our simulations.

In this study, the effects of the combination of mutual neighborhood algorithm and diagonal loading technique (MN-DL-LLE) and also their separate (MN-LLE and DL-LLE) performance are investigated. For completing the investigation, the results are compared with another local manifold learning method, LEM. Also, mutual neighborhood conception is applied on LEM (MN-LEM). In MN-LEM, after determining the mutual neighbors of , the coefficients between and its mutual neighbors are calculated as follows:

(9)

where t is the heat kernel parameter of Laplacian function. Then, the low-dimensional embedded data manifold () is extracted using the following equation:

(10)

where is a diagonal matrix with . In our experiments, is set to 1 if is neighbor of for LEM and MN-LEM.

ORL face image database

ORL image database includes 400 face images of size 112 × 92 at different time, lighting and facial expressions. There are 40 persons with 10 images for everyone. Some sample images are shown in Figure 4.

Figure 4. The upper row shows face images of five different persons of ORL database and the lower row shows face images of one person with different lighting and facial expressions.

A set of different images for each person is randomly divided into three subsets, namely, four train images, three validation images and three test images. In this database, leave one out method is used for evaluating the performance of the proposed method. The experiments are done in different low dimensionalities () and the number of the neighbors is 7 (). The results are given in Table 3.

Table 3. The recognition rates of LLE, MN-LLE, DL-LLE, MN-DL-LLE, LEM and MN-LEM for ORL database in different dimensionalities.

	Recognition rates on ORL database
Dimension of the low dimensionality (d)	LLE	MN-LLE	DL-LLE	MN-DL-LLE	LEM	MN-LEM
6	81.67	86.67	81.67	89.17	80	83.33
9	82.5	89.17	85	90.83	80	85
12	81.67	90	85.83	90.83	83.33	92.5
15	84.17	92.5	85.83	92.5	81.67	89.17

The results show that mutual neighborhood conception properly improves the performance of LLE and LEM methods. Also, diagonal loading technique affects LLE well. Table 4 shows the values of the diagonal loading parameter of DL-LLE and MN-DL-LLE methods. These values are determined based on the train and validation datasets to provide the maximum recognition rate in different dimensionalities.

Table 4. The values of diagonal loading parameters of DL-LLE and MN-DL-LLE for ORL database in different dimensionalities.

The values of diagonal loading parameters for ORL database
Dimension of the low dimensionality (d)	DL-LLE	MN-DL-LLE
6	0	−16.9555
9	−2.6040	−16.9555
12	−11.9106	1.2135
15	−8.4967	0

IPHD

This database includes 2240 isolated Persian handwritten digit images from 1–9 except 2. There are 280 samples for each digit. Figure 5 shows some sample images of this database.

Figure 5. The upper row shows different shapes of number four in Persian handwritten and the lower row shows number 1–9 in Persian handwritten except number 2.

Samples of each class are randomly divided into three subsets, namely, 140 train images, 70 validation images and 70 test images. Validation images are used to determine the value of the diagonal loading parameter. The number of the neighbors is 10 and the recognition rates are calculated in the low dimensionalities of 6,9,12 and 15. Table 5 shows the obtained results.

Table 5. The recognition rates of LLE, MN-LLE, DL-LLE, MN-DL-LLE, LEM and MN-LEM for IPHD database in different dimensionalities.

	Recognition rates on IPHD database
Dimension of the low dimensionality (d)	LLE	MN-LLE	DL-LLE	MN-DL-LLE	LEM	MN-LEM
6	83.21	86.61	83.57	86.79	81.07	86.07
9	84.11	86.42	84.29	87.5	81.25	87.14
12	84.29	87.5	85.71	86.96	81.96	86.43
15	84.29	87.32	84.82	87.32	81.43	87.32

The results demonstrate the good performance of the proposed MN-DL-LLE and MN-LEM methods. Mutual neighborhood provides more effective local structure information and increases the performance of local manifold learning methods. The values of the diagonal loading parameter are given in Table 6. Again, diagonal loading enhances the results.

Table 6. The values of diagonal loading parameters of DL-LLE and MN-DL-LLE for IPHD database in different dimensionalities.

The values of diagonal loading parameters for IPHD database
Dimension of the low dimensionality (d)	DL-LLE	MN-DL-LLE
6	3.8999	−2.5491
9	−0.8696	3.6049
12	−4.0055	13.1212
15	−7.9978	0.4

Isolated Farsi/Arabic handwritten character database (IFHCDB)

IFHCDB includes 52380 and 17740 isolated Persian handwritten characters and digits, respectively. The images are gray scale and 300 dpi. The number of samples in different classes is not the same. Some samples of IFHCDB digits are given in Figure 6.

Figure 6. The upper row shows different shapes of number 5 and the lower row shows number 0–9 in Persian handwritten.

The digits are used to investigate the performance of our proposed method. In each class, the number of samples of train, validation and test are 150, 50 and 50, respectively. The samples are randomly selected. Table 7 shows the results. Again the results demonstrate the good performance of the proposed method.

Table 7. The recognition rates of LLE, MN-LLE, DL-LLE, MN-DL-LLE, LEM and MN-LEM for the digits of IFHCDB database in different dimensionalities.

	Recognition rates on the digits of IFHCDB database
Dimension of the low dimensionality (d)	LLE	MN-LLE	DL-LLE	MN-DL-LLE	LEM	MN-LEM
6	53	66.4	56.4	68.6	54.4	64.2
9	54.4	67.4	64	69	56.8	66.8
12	59.4	70.6	65.6	70.4	58	67.2
15	63.6	71.2	67.4	71.4	56.8	68.8

The values of the diagonal loading for IFHCDB database are given in Table 8.

Table 8. The values of diagonal loading parameters of DL-LLE and MN-DL-LLE for the digits of IFHCDB database in different dimensionalities.

The values of diagonal loading parameters for IPHD database
Dimension of the low dimensionality (d)	DL-LLE	MN-DL-LLE
6	0.8221	7.5244
9	1.0615	1.0321
12	9.0456	6.9059
15	1.7340	3.3317

Sparsity of the proposed representation

As we know, mutual neighborhood conception induces a sparser neighborhood graph matrix than the common graph matrix. The amounts of the sparsity of the neighborhood graph matrix in MN-DL-LLE and LLE are tabulated in Table 9 for different number of neighbors. As Table 9 shows, the proposed method leads to sparse representation of manifold structure. Also, the sparsity of the neighborhood graph matrices of MN-LLE and MN-LEM are the same as MN-DL-LLE.

Table 9. Comparison between nonzero elements of neighborhood graph matrices of LLE and MN-DL-LLE.

			Zero norm of neighborhood graph matrix ()
Initial number of the neighbors (K)	ORL database		IPHD database		IFHCDB database
	LLE	MN-DL-LLE	LLE	MN-DL-LLE	LLE	MN-DL-LLE
7	1120	684	7840	4358	10500	4548
8	1280	778	8960	5057	12000	5103
9	1440	860	10080	5751	13500	5710
10	1600	968	11200	6397	15000	6282
12	1920	1164	13440	7873	18000	7550
15	2400	1430	16800	9885	22500	9262

Conclusions

In local manifold learning methods, the construction of the neighborhood graph matrix is a main step that is related to the selection of the neighbors of each data point and the coefficients between each data point and its neighbors. In this paper, a new unsupervised nonlinear local manifold learning method was proposed. The proposed method is based on the mutual neighborhood conception and diagonal loading for linear reconstruction weight of each data point in LLE algorithm. The values of the diagonal loading parameter are determined by validation dataset corresponding to the best recognition rate. Also, the results of applying the mutual neighborhood conception on LEM demonstrate the proper performance of our proposed neighbor selection method. Simulations were carried out for ORL, IPHD and IFHCDB databases. The obtained results show the effectiveness of the proposed method. In all experiments, the proposed MN-DL-LLE algorithm has the best recognition rate. In all experiments for the ORL, IPHD and IFHCDB databases, recognition rates of MN-DL-LLE are approximately 8%, 3% and 10% better than LLE, respectively. Moreover, the neighborhood graph matrix based on the mutual neighborhood conception is very sparser than the neighborhood graph matrices of LLE or LEM. The results show that the proposed sparse neighborhood graph, which is constructed based on the mutual neighborhood conception and diagonal loading, can be better extracted the local information of the manifold. Therefore, in local manifold learning methods, the right choice of the neighbors and then a true definition of the connection coefficients between each data point and its neighbors can more effectively improve the performance.