Random

Generating random numbers

In HighFM, the random numbers are generated in two steps. First, a RandomEngine (e.g., PCG ) creates a sequence of 64 pseudorandom bits. Generator then transforms these bits into a random number that follows a specific probability distribution (such as uniform and normal distributions).

HighFM implements three different pseudorandom generators:

Name

Type

Output (bits)

Period

Streams

PCG

LCG

64

\(2^{128}\)

\(2^{127}\)

SplitMix

Counter

64

\(2^{64}\)

\(2^{63}\)

Xoroshiro

LSFR

64

\(2^{256} - 1\)

1

API

Constructing a sketch operator

In the heart of the Randomized Linear algebra lies the sketching operator \(\mathbf{S} \in \mathbb{C}^{\ell \times n}\) with \(\ell \ll n\) that distorts the Euclidean norm \(\| \cdot \|_2\) in a controlled manner [1]. Formally, for a \(\gamma \in [0, 1)\) and a subspace \(\mathbb{F}^n \subset \mathbb{C}^n\), then \(\mathbf{S}\) is a linear map that satisfies

\[(1 - \gamma) \|\vec{x}\| \leq \|\mathbf{S}\vec{x}\| \leq (1 +\gamma) \|\vec{x}\|, \quad \forall \vec{x} \in \mathbb{F}^n\]

In this case, we say that \(\mathbf{S}\) is a embedding of \(\mathbb{F}^n\) with a distortion \(\gamma\). In pratice, the matrix \(\mathbf{S}\) is not explicitly available and we use random distributions to achieve the relation above with high probability. The idea is to use this sketching operator to reduce the dimensionality of the problem, improving its performance. See [1] for more details.

HighFM currently supports the following sketching operators:

References