A Caltech Library Service

Concentration Inequalities of Random Matrices and Solving Ptychography with a Convex Relaxation


Chen, Yuhua Richard (2017) Concentration Inequalities of Random Matrices and Solving Ptychography with a Convex Relaxation. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z9M906MF.


Random matrix theory has seen rapid development in recent years. In particular, researchers have developed many non-asymptotic matrix concentration inequalities that parallel powerful scalar concentration inequalities. In this thesis, we focus on three topics: 1) estimating sparse covariance matrix using matrix concentration inequalities, 2) constructing the matrix phi-entropy to derive matrix concentration inequalities, 3) developing scalable algorithms to solve the phase recovery problem of ptychography based on low-rank matrix factorization.

Estimation of covariance matrix is an important subject. In the setting of high dimensional statistics, the number of samples can be small in comparison to the dimension of the problem, thus estimating the complete covariance matrix is unfeasible. By assuming that the covariance matrix satisfies some sparsity assumptions, prior work has proved that it is feasible to estimate the sparse covariance matrix of Gaussian distribution using the masked sample covariance estimator. In this thesis, we use a new approach and apply non-asymptotic matrix concentration inequalities to obtain tight sample bounds for estimating the sparse covariance matrix of subgaussian distributions.

The entropy method is a powerful approach in developing scalar concentration inequalities. The key ingredient is the subadditivity property that scalar entropy function exhibits. In this thesis, we construct a new concept of matrix phi-entropy and prove that matrix phi-entropy also satisfies a subadditivity property similar to the scalar form. We apply this new concept of matrix phi-entropy to derive non-asymptotic matrix concentration inequalities.

Ptychography is a computational imaging technique which transforms low-resolution intensity-only images into a high-resolution complex recovery of the signal. Conventional algorithms are based on alternating projection, which lacks theoretical guarantees for their performance. In this thesis, we construct two new algorithms. The first algorithm relies on a convex formulation of the ptychography problem and on low-rank matrix recovery. This algorithm improves traditional approaches' performance but has high computational cost. The second algorithm achieves near-linear runtime and memory complexity by factorizing the objective matrix into its low-rank components and approximates the first algorithm's imaging quality.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:concentration inequalities; entropy method; moment inequalities; random matrix; subadditivity; tensorization; covariance estimation; ptychography; phase retrieval; coherent diffractive imaging
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Applied And Computational Mathematics
Minor Option:Social Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Tropp, Joel A.
Thesis Committee:
  • Hassibi, Babak (chair)
  • Hou, Thomas Y.
  • Owhadi, Houman
  • Yang, Changhuei
  • Tropp, Joel A.
Defense Date:5 July 2016
Record Number:CaltechTHESIS:09022016-135721172
Persistent URL:
Related URLs:
URLURL TypeDescription related for ch. 3 adapted for ch. 4 adapted for ch. 5
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:9911
Deposited By: Yuhua Chen
Deposited On:23 Sep 2016 22:51
Last Modified:04 Oct 2019 00:14

Thesis Files

PDF - Final Version
See Usage Policy.


Repository Staff Only: item control page