Graph Optimization Framework Based Dimensionality Reduction Approaches And Their Applications

Dimensionality reduction is a novel research direction, which integrates the knowl-edge from statistics and computer science. It mainly focuses on the problem of repre-senting the original high dimensional data in a low dimensional space and discovering itsintrinsic structure. In this thesis, we propose some systemic researches about dimension-ality reduction in theory, methodand application. More concretely, the maincontributionsinclude:1. This thesis proposes a novel graph optimization framework for dimensionalityreduction. It divides the problem of dimensionality reduction into three parts: from datato manifold, from manifold to graph and optimization on graph. Some theoretical analy-ses about why the high dimensional data are nearly lying on a low dimensional manifoldare provided. The relationship of structure descriptions between manifold and graph arediscussed. We also summarize the main optimization principles. Finally, within the pro-posed framework, some typical dimensionality reduction approaches are analyzed. Thisframework is not only the theoretical foundations of further researches about methods andapplications, but also beneficial to the understanding of dimensionality reduction.2. Within the graph optimization framework, we analyze the instability of local di-mensionality approaches. By adding the global information and kernel transformation,we propose the stable local dimensionality reduction framework. Some local methodsare also improved for illustration. Moreover, another method that is named as local lineartransformationembedding, isalsoproposed. Ituseslocallineartransformationtoimprovethe stability in solving the constraint least square problem. Comparing with their originalmethods, all methods are stable to both noises and parameters. Thus, it is more suitablefor real applications.3. According to the graph construction step of graph optimization framework, weprovide researches with different data types and prior knowledge. Three prominent semi-supervised dimensionality reduction approaches are proposed. Semi-supervised dimen-sionality reduction via harmonic functions could effectively enlarge the prior informationand improve the performance of dimensionality reduction approaches. Additionally, weare the first to study the problem of dimensionality reduction for multiple view data and propose an effective method to solve this problem. Finally, we first define a new type oflabel, i.e., negative label, and then present a semi-supervised learning approach to effec-tivelyusenegativelabels. Alltheresearchescannotonlyextenddimensionalityreductionto the field of semi-supervised learning, but also have high application potentials.4. Intheapplicationofimageclassificationandclustering,byconsideringthesmooth-ness and manifold structure of image data, the orthogonality of the subspace bases, wepropose three subspace learning models. For image classification, the smooth and orthog-onal subspace model takes fully considerations about the smoothness of image data andthe orthogonality of the subspace bases. For image clustering, considering the excellenceof trace ratio criterion and the smoothness of clustering index, we propose the trace ra-tio criterion model. Moreover, for the purpose of using nonlinear structure informationin learning subspace, we proposed a new technique which is called pattern shrinking anda new subspace learning model by pattern shrinking. These researches could not onlydeepen the research about subspace learning, but also provide useful guidance for realimage processing.5. For the problem of learning high dimensional correspondence, we provide twolearningbasedmodels,i.e.,learninghighdimensionalcorrespondencebasedonmaximumvarianceunfoldingandlocalapproximationmaximumvarianceunfoldingforhighdimen-sional correspondence learning. The first approach considers the excellence of maximumvariance unfolding and the second pays more attentions to the computational efficiency.It has also been used in cross system personalization. These models could also provideuseful guidance for real applications.In summary, this thesis provides several systemic researches about the problem ofdimensionality reduction.