Title:  Singular Value Computation and Subspace Clustering

Abstract:  In this dissertation we discuss two problems. In the First part, we consider the problem of computing a few extreme singular values of a symmetric defnite generalized eigenvalue problem or a large and sparse matrix C. Most existing numerical methods are based on reformulating the singular value problem as an equivalent symmetric eigenvalue problem. The standard method of choice of computing a few extreme eigenvalues of a large symmetric matrix is the Lanczos or the implicitly restarted Lanczos method. These methods usually employ a shift-and-invert transformation to accelerate the speed of convergence, which is not practical for truly large problems. With this in mind, Golub and Ye proposes an inverse-free preconditioned Krylov subspace method, which uses preconditioning instead of shift-and-invert to accelerate the convergence. The inverse-free Krylov subspace method focuses on the computation of one extreme eigenvalue and a deflation technique is needed to compute additional eigenvalues. The Wielandt deflation has been considered and can be used in a straightforward manner. However, the Wielandt deflation alters the structure of the problem and may cause some difficulties in certain applications such as the singular value computations. So we First propose to consider a deformation by restriction method for the inverse-free Krylov subspace method. We generalize the original convergence theory for the inverse-free preconditioned Krylov subspace method to justify this deflation scheme. We next extend the inverse-free Krylov subspace method with deflation by restriction to the singular value problem. We consider preconditioning based on robust incomplete factorization to accelerate the convergence. Numerical examples are provided to demonstrate effciency and robustness of the new algorithm.

In the second part of this thesis, we consider the so-called subspace clustering problem, which aims for extracting a multi-subspace structure from a collection of points lying in a high-dimensional space. Recently, methods based on Self Expressive Property(SEP) such as Sparse Subspace Clustering(SSC) and Low Rank Representations( LRR) have been shown to enjoy superior performances than other methods. Self Expressive Property means the points can be expressed as linear combinations of themselves. However, methods with SEP may result in representations that are not amenable to clustering through graph partitioning. We propose a method where the points are expressed in terms of an orthonormal basis. The orthonormal basis is optimally chosen in the sense that the representation of all points is sparsest. Nnumerical results are given to illustrate the effectiveness and effciency of this method.