Non-asymptotic Singular Value Analysis of Random Matrices with Computer Science Applications

Abstract

Non-asymptotic random matrix theory focuses on obtaining quantitative high-probability estimates for the spectral properties of random matrices with large but fixed sizes. Such results are important in computer science applications. Also, in these applications, classical models of random matrices, e.g., the i.i.d. entries models, are not sufficient, and more complicated new models, ones that involve deterministic shifts, submatrices, and dependence between entries, are needed. This work is devoted to the study of non-asymptotic properties of these structured random matrix models and their implications in computer science applications.

The first part of this thesis studies a shifted random matrix. More precisely, let $R$ be a $n$ by $n$ random matrix with i.i.d. subgaussian entries. Let $M$ be a $n$ by $n$ deterministic matrix with controlled norm. This dissertation gives a general estimate of the smallest singular value of the sum $R + M$, which improves upon an earlier result of Tao and Vu.

The second part of this thesis studies the existence of well conditioned $n$ by $n$ square submatrices in a large fat $n$ by $M$ matrix where $M$ is much larger than $n$, and its implications on the existence of Riesz bases in random frames. We establish a phase transition for the probability that a random frame contains a Riesz basis. Namely, we first show that a random frame in $R^n$ formed by $M$ vectors with independent identically distributed coordinate having a non-degenerate symmetric distribution contains many Riesz bases with high probability provided that $M ge exp(Cn)$. In the proof of this result, we use approximately Hadamard matrices as pattern matrices, where approximately Hadamard matrices are $n$ by $n$ matrices with $pm 1$ entries which acts on $R^n$ as a approximate scaled isometry. The existence of such matrices in any dimension $n$ is proved by combining number-theoretic and probabilistic tools. On the other hand, we prove that if the entries are subgaussian, then a random frame fails to contain a Riesz basis with probability close to $1$ whenever $M le exp(cn)$, where $c< C$ are constants depending on the distribution of the entries.

The third part of this dissertation studies the oblivious subspace embedding matrices, where a random $m$ by $n$ matrix $S$ is an oblivious subspace embedding (OSE) with parameters $varepsilon>0$, $deltain(0,1/3)$ and $dleq mleq n$, if for any $d$-dimensional subspace $Wsubseteq R^n$, begin{align*} Pbbig(,forall_{xin W} (1+varepsilon)^{-1}|x|leq |Sx|leq (1+varepsilon)|x|,big)geq 1-delta end{align*} Using recent advances in universality theory for random matrices, we show that, given any $theta > 0$, an $mtimes n$ random matrix $S$ with $mgeq (1+theta)d$ consisting of randomly sparsified $pm1/sqrt s$ entries and having $s= O(log^4(d))$ non-zeros per column, is an oblivious subspace embedding with $varepsilon = O_{theta}(1)$. Our result addresses the main open question posed by Nelson and Nguyen (FOCS 2013), who conjectured that sparse OSEs can achieve $m=O(d)$ embedding dimension, and it improves on $m=O(dlog(d))$ shown by Cohen (SODA 2016). We use this result to construct the first oblivious subspace embedding with $O(d)$ embedding dimension that can be applied faster than current matrix multiplication time. We further extend our results to construct even sparser non-oblivious embeddings, leading to the first subspace embedding with low distortion $varepsilon=o(1)$ and optimal embedding dimension $m=O(d/varepsilon^2)$ that can be applied in current matrix multiplication time, addressing a question posed by Cherapanamjeri, Silwal, Woodruff and Zhou (SODA 2023).