CaltechTHESIS
  A Caltech Library Service

Compressing Positive Semidefinite Operators with Sparse/Localized Bases

Citation

Zhang, Pengchuan (2017) Compressing Positive Semidefinite Operators with Sparse/Localized Bases. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z91N7Z5J. http://resolver.caltech.edu/CaltechTHESIS:05312017-000636495

Abstract

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 (nN), 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.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:sparse operator compression, intrinsic sparse mode decomposition, multiscale finite element method, numerical homogenization
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Awards:The W.P. Carey & Co. Inc. Prize in Applied Mathematics, 2017.
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Hou, Thomas Y.
Thesis Committee:
  • Hou, Thomas Y. (chair)
  • Owhadi, Houman
  • Stuart, Andrew
  • Beck, James L.
Defense Date:17 May 2017
Funders:
Funding AgencyGrant Number
NSFDMS 1318377
NSFDMS 1613861
Record Number:CaltechTHESIS:05312017-000636495
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:05312017-000636495
DOI:10.7907/Z91N7Z5J
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1137/16M107760XDOIArticle adapted for Ch. 5
http://dx.doi.org/10.1137/16M1077611DOIArticle adapted for Sec. 1.4
ORCID:
AuthorORCID
Zhang, Pengchuan0000-0003-1155-9507
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:10228
Collection:CaltechTHESIS
Deposited By: Pengchuan Zhang
Deposited On:02 Jun 2017 19:25
Last Modified:16 Jun 2017 23:06

Thesis Files

[img]
Preview
PDF - Final Version
See Usage Policy.

6Mb

Repository Staff Only: item control page