dimensionality reduction, weighted graph, Laplacian matrix, eigenvalue problem

The focus of our research is the dimensionality reduction problem which can be described as follows: the input data are characterized by a large amount of parameters. The aim of this problem is to find a map that transforms the data into a form in which they are described by substantially fewer parameters and in which the resulting loss of information is in a way minimal. In other words, the points representing the input data are given and their images are to be found according to a specified criterion.One of the most employed methods for dimensionality reduction is the Principal Component Analysis.Our approach is different from the standard approach of the data analysis. We are trying to get a more stable results of the dimensionality reduction problem and hence we decide to change the notion of closeness. We require that the images of the close input points are close as well.As a first step, we embed the input data into a weighted connected graph represented by the incidence matrix where the elements characterize the closeness between the input points. Then we proceed with the Laplacian matrix and solve the generalized eigenvalue problem. It is known that an eigenvector corresponding to the minimal eigenvalue of this problem minimizes the quadratic form specified by the Laplacian matrix. And it is ensured that the initial requirement on the closeness is satisfied. The Laplacian matrix is positive semi-definite and this case is more difficult than that of positive definite matrices.In our work we are focused on mathematical justification of all heuristic claims that are encountered in the reference literature. The main theory is the theory of matrices and their particular forms. We also proved important facts about eigenvectors of positive semi-definite matrices. This research has a large potential in many practical applications, such as in the clustering and in the image segmentation problem which we plan to anylyze further on.