Rand-SD

 

 

Outcomes

Quick start

Prerequisites

To reproduce our results, you will need

• a Git installation to clone the repository;
• a recent version of Python to run the experiments;
• and a LaTeX distribution to build the thesis, slides, and poster.

Note

The commands git, python, pdflatex, lualatex, bibtex, and makeglossaries have to be discoverable by your terminal. To verify this, type [command] --version in your terminal.

Setup

Clone this repository using

git clone https://github.com/FMatti/Rand-SD
cd Rand-SD

Install all the requirements with

python -m pip install --upgrade pip
python -m install -r requirements.txt

Reproduce the whole project with the following command

python -m setup.py -a

Note

Reproducing the whole project might take up to three hours!

Theoretical background

We concern ourselves with the approximation of the smoothened spectral density

$$ \phi_{\sigma}(t) = \sum_{i=1}^n g_{\sigma}(t - \lambda_i) = \mathrm{Tr}(g_{\sigma}(t\boldsymbol{I} - \boldsymbol{A})) $$

of a large symmeric matrix $\boldsymbol{A} \in \mathbb{R}^{n \times n}$.

Chebyshev expansion

In all methods, we first compute the Chebyshev expansion

$$ g_{\sigma}(t\boldsymbol{I} - \boldsymbol{A}) \approx g_{\sigma}^{(m)}(t\boldsymbol{I} - \boldsymbol{A}) = \sum_{l=0}^{m} \mu_l(t) T_l(\boldsymbol{A}). $$

Delta-Gauss-Chebyshev

We directly estimate the trace using the Hutchinson's trace estimator with a standard Gaussian random matrix $\boldsymbol{\Psi} \in \mathbb{R}^{n \times n_{\Psi}}$ to obtain

$$ \phi_{\sigma}(t) \approx \widetilde \phi_{\sigma}^{(m)}(t) = \frac{1}{n_{\Psi}} \sum_{l=0}^{m} \mu_l(t) \mathrm{Tr}(\boldsymbol{\Psi}^{\top} T_l(\boldsymbol{A}) \boldsymbol{\Psi}). $$

Nyström-Chebyshev

We compute the Nyström approximation with a standard Gaussian sketching matrix $\boldsymbol{\Omega} \in \mathbb{R}^{n \times n_{\Omega}}$

$$ g_{\sigma}(t\boldsymbol{I}- \boldsymbol{A}) \approx \widehat g_{\sigma}^{(m)}(t\boldsymbol{I}- \boldsymbol{A}) = (g_{\sigma}^{(m)}(t\boldsymbol{I}- \boldsymbol{A}) \boldsymbol{\Omega})(\boldsymbol{\Omega}^{\top} g_{\sigma}^{(m)}(t\boldsymbol{I}- \boldsymbol{A}) \boldsymbol{\Omega})(g_{\sigma}^{(m)}(t\boldsymbol{I}- \boldsymbol{A}) \boldsymbol{\Omega})^{\top} $$

and compute its trace

$$ \phi_{\sigma}(t) \approx \widehat \phi_{\sigma}^{(m)}(t) = \mathrm{Tr}(\widehat{g}_{\sigma}^{(m)}(t\boldsymbol{I}- \boldsymbol{A})). $$

Nyström-Chebyshev++

We compute the Nyström approximation and apply the Hutchinson's to the residual of the approximation to get the trace

$$ \phi_{\sigma}(t) \approx \breve \phi_{\sigma}^{(m)}(t) = \mathrm{Tr}(\widehat g_{\sigma}^{(m)}(t\boldsymbol{I} - \boldsymbol{A})) + \frac{1}{n_{\Psi}} \mathrm{Tr}(\boldsymbol{\Psi}^{\top} (g_{\sigma}^{(m)}(t\boldsymbol{I}- \boldsymbol{A}) - \widehat g_{\sigma}^{(m)}(t\boldsymbol{I} - \boldsymbol{A})) \boldsymbol{\Psi}). $$

Project structure

Rand-SD
│   README.md           (file you are reading right now)
|   requirements.txt    (python package requirements file)
|   setup.py            (script for easy setup of project)
|
└───examples            (folder with example jupyter notebooks for the project)
└───poster              (LaTeX files which are used to generate the poster)
└───setup               (scripts which help setup and reproduce project)
└───slides              (LaTeX files which are used to generate the slides)
└───src                 (the Python modules which were written for the project)
└───thesis              (LaTeX files which are used to generate the thesis)

Contact

In case of questions and unclarities, feel free to contact us through one of the following channels: