Geometric Analysis On High-Dimensional Data:Theories, Algorithms And Applications

In recent years, the repaid developments of Internet, biological medicine and social com-puting and the massive amount of digital data being produced by problems in these areas have inspired a increasing interest in high dimensional data processing, especially exploring the in-trinsic geometric structure of the data set. In this thesis, we focus on the problem of high dimensional data processing from the viewpoint of geometry. Our contributions can be roughly divided into three main categories:fast algorithms for conventional models, new theories for unsupervised and supervised learning problems and novel framework for designing PDEs for vision applications. The main works can be summarized as follows:(1) We provided a new method, named l1filtering, for Principal Component Pursuit (PCP). Instead of solving standard PCP on the whole data matrix, our proposed method consists of two steps:recovering the seed matrix and solving l1minimization. Besides the guarantee for the exactly recovery, there is only linear cost at each iteration in l1filtering. Thus significantly reduces the difficulty for applying PCP on large scale problems.(2) By improving the conventional Alternating Direction Method (ADM), we provided a new algorithm, named Linearized ADM with Adaptive Penalty (LADMAP), for solving the separable convex programming with linear constraint and proved its global convergence. LADMAP can successfully avoid introducing auxiliary variables for the optimization pro-cess, hence saving memory and waiving the expensive matrix inversions to update the auxiliary variables. We also applied LADMAP for solving the Low-Rank Representation (LRR) model. By incorporating SVD representation into the algorithm, the computational complexity for solving LRR model can be reduced from O(n3) to O(n2).(3) By analyzing the limitations from the mechanism viewpoint for LRR, we provided a new model, named Fixed-Rank Representation (FRR), for unsupervised visual learning. For subspace clustering, we proved that under some suitable conditions, even with insufficient sampling data, FRR can still exactly reveal the memberships for multiple subspaces. We also extended the mechanism of FRR for unsupervised feature extraction and analyzed the intrinsic connection with Principal Component Analysis (PCA). In this way, we demon-strated that both subspace clustering and feature extraction can be well solved in the FRR framework. (4) By using Lorentzian manifold to model the discriminant structure of the data set, we provided a new method, named Lorentzian Discriminant Projection (LDP), for supervised dimensionality reduction. This new method can successfully model both the local within-class similarity and the global geometric structure for the data set by learning a specific Lorentzian metric tensor. To process data with different structure arising in computer vision area, we also proposed kernel, tensor and smooth regularized extensions for LDP.(5) Partial differential equations (PDEs) have been successful for solving many problems in computer vision. However, the existing PDEs are all crafted by people with skill, based on some limited and intuitive considerations. As a result, the designed PDEs may not be able to handle complex situations in real applications. We showed that the design of PDEs could be made easier by borrowing the learning strategy from machine learning society. The PDE system in our framework is learnt from some input/output pairs of training images via an optimal control technique. The effectiveness of this framework for image restoration is demonstrated with two exemplary applications:image denoising and inpainting.