Summary

Implementation of a new induced matrix distribution using the approximate leverage scores of the matrix.

Method

Let row_distribution = true and $A \in \mathbb{R}^{n \times d}$. Let $\Pi_1 \in \mathbb{R}^{r_1 \times n}$ be a $\epsilon$-Fast Johnson-Lindenstrauss Transform, and $\Pi_2 \in \mathbb{R}^{d \times r_2}$ be an $\epsilon$-Johnson-Lindenstrauss Transform. In the reference, $\Pi_1$ is formed by the subsampled randomized hadamard transform and an example distribution for $\Pi_2$ is introduced in section 2.2.

Let the SVD of $\Pi_1A = U \Sigma V^\intercal$ and let $R^{-1} = V \Sigma^{-1}$. Then, define

$$\Omega = AR^{-1}\Pi_2,$$

which is the matrix that will be used to construct the distribution. In particular, given $\Omega$ the probability weight assigned to the $i^{th}$ row of $A$ is

$$||\Omega[i, :]||_2^2/||\Omega||_F^2.$$

If row_distribution = false, the same computation is carried out on $A^\intercal$.

Changes

The method is implemented under linear_samplers/induced_distributions, and is composed of two methods.

1. _approximate_leverage_scores takes as input a matrix A, and two sketching methods, and returns $\Omega$.
2. approximate_leverage_scores_distribution takes as input A, two sketching methods, and a boolean flag, and returns a distribution using the approximate leverage scores. approximate_leverage_scores_distribution calls _approximate_leverage_scores.
3. Testing files and documentation update

Closes #63