A Caltech Library Service

Positive Definite Matrices: Compression, Decomposition, Eigensolver, and Concentration


Huang, De (2020) Positive Definite Matrices: Compression, Decomposition, Eigensolver, and Concentration. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/g2nt-yy27.


For many decades, the study of positive-definite (PD) matrices has been one of the most popular subjects among a wide range of scientific researches. A huge mass of successful models on PD matrices has been proposed and developed in the fields of mathematics, physics, biology, etc., leading to a celebrated richness of theories and algorithms. In this thesis, we draw our attention to a general class of PD matrices that can be decomposed as the sum of a sequence of positive-semidefinite matrices. For this class of PD matrices, we will develop theories and algorithms on operator compression, multilevel decomposition, eigenpair computation, and spectrum concentration. We divide these contents into three main parts.

In the first part, we propose an adaptive fast solver for the preceding class of PD matrices which includes the well-known graph Laplacians. We achieve this by establishing an adaptive operator compression scheme and a multiresolution matrix factorization algorithm which have nearly optimal performance on both complexity and well-posedness. To develop our methods, we introduce a novel notion of energy decomposition for PD matrices and two important local measurement quantities, which provide theoretical guarantee and computational guidance for the construction of an appropriate partition and a nested adaptive basis.

In the second part, we propose a new iterative method to hierarchically compute a relatively large number of leftmost eigenpairs of a sparse PD matrix under the multiresolution matrix compression framework. We exploit the well-conditioned property of every decomposition components by integrating the multiresolution framework into the Implicitly Restarted Lanczos method. We achieve this combination by proposing an extension-refinement iterative scheme, in which the intrinsic idea is to decompose the target spectrum into several segments such that the corresponding eigenproblem in each segment is well-conditioned.

In the third part, we derive concentration inequalities on partial sums of eigenvalues of random PD matrices by introducing the notion of k-trace. For this purpose, we establish a generalized Lieb's concavity theorem, which extends the original Lieb's concavity theorem from the normal trace to k-traces. Our argument employs a variety of matrix techniques and concepts, including exterior algebra, mixed discriminant, and operator interpolation.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Positive-definite matrices, operator compression, multiresolution decomposition, linear solver, eigensolver, matrix concentration, Lieb's concavity theorem
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Hou, Thomas Y.
Thesis Committee:
  • Owhadi, Houman (chair)
  • Stuart, Andrew M.
  • Schroeder, Peter
  • Hou, Thomas Y.
Defense Date:14 May 2020
Non-Caltech Author Email:huangde0123 (AT)
Funding AgencyGrant Number
Record Number:CaltechTHESIS:05222020-162227420
Persistent URL:
Related URLs:
URLURL TypeDescription adapted for Chapter 2 and Chapter 3. adapted for Chapter 4. adapted for Chapter 5. adapted for Chapter 5.
Huang, De0000-0003-4023-9895
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:13715
Deposited By: De Huang
Deposited On:01 Jun 2020 22:14
Last Modified:09 Jun 2020 18:34

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page