Summary:

Given a positive semidefinite (PSD) operator, such as a PSD matrix, an elliptic operator with rough coefficients, a covariance operator of a random field, or the Hamiltonian of a quantum system, we would like to find its best finite rank approximation with a given rank. One way to achieve this objective is to project the operator to its eigenspace that corresponds to the smallest or largest eigenvalues, depending on the setting. The eigenfunctions are typically global, i.e. nonzero almost everywhere, but our interest is to find the sparsest or most localized bases for these subspaces. The sparse/localized basis functions lead to better physical interpretation and preserve some sparsity structure in the original operator. Moreover, sparse/localized basis functions also enable us to develop more efficient numerical algorithms to solve these problems. In this thesis, we present two methods for this purpose, namely the sparse operator compression (Sparse OC) and the intrinsic sparse mode decomposition (ISMD). The Sparse OC is a general strategy to construct finite rank approximations to PSD operators, for which the range space of the finite rank approximation is spanned by a set of sparse/localized basis functions. The basis functions are energy minimizing functions on local patches. When applied to approximate the solution operator of elliptic operators with rough coefficients and various homogeneous boundary conditions, the Sparse OC achieves the optimal convergence rate with nearly optimally localized basis functions. Our localized basis functions can be used as multiscale basis functions to solve elliptic equations with multiscale coefficients and provide the optimal convergence rate O(hk) for 2k'th order elliptic problems in the energy norm. From the perspective of operator compression, these localized basis functions provide an efficient and optimal way to approximate the principal eigen-space of the elliptic operators. From the perspective of the Sparse PCA, we can approximate a large set of covariance functions by a rank-n operator with a localized basis and with the optimal accuracy. While the Sparse OC works well on the solution operator of elliptic operators, we also propose the ISMD that works well on low rank or nearly low rank PSD operators. Given a rank-n PSD operator, say a N-by-N PSD matrix A (n Þ́ N), the ISMD decomposes it into n rank-one matrices Đni=1gigTi where the mode {gi}ni=1 are required to be as sparse as possible. Under the regular-sparse assumption (see Definition 1.3.2), we have proved that the ISMD gives the optimal patchwise sparse decomposition, and is stable to small perturbations in the matrix to be decomposed. We provide several applications in both the physical and data sciences to demonstrate the effectiveness of the proposed strategies.