F10 (Rnla)

Randomized Numerical Linear Algebra

This chapter covers linear algebra routines that make use of random projections to reduce problem dimension. This area is referred to as RNLA (Randomized Numerical Linear Algebra). The routines can be split into the following categories:

- building blocks that are intended to be used as components in RNLA algorithms written by you;
- RNLA algorithms for matrix factorization.

It is envisaged that users of the higher-level routines, such as matrix factorization, will have some background in linear algebra. A common use case would be that you have tried solving your problem using a deterministic linear algebra routine, e.g., an LAPACK routine from Chapter F08, and are in need of a routine that is more computationally efficient.

Users of the building block routines would be expected to have some familiarity with the RNLA literature, i.e., a higher level of expertise.

RNLA algorithms use random projections in order to reduce problem dimension. If $A$ is an $m$ by $n$ matrix, the random projection of $A$ is either,

where $A$ is a real $m$ by $n$ matrix and $\Omega $ is an $n$ by $k$ matrix, or

where $\Omega $ is an $k$ by $m$ matrix.

$$Y=A\Omega $$ |

$$Y=\Omega A$$ |

Random projections can be classified as slow or fast. Slow random projections have the same computational cost as a standard matrix multiplication, i.e., $\mathit{O}\left(mnk\right)$ operations. Fast random projections have a lower computational cost, typically $\mathit{O}\left(mn\mathrm{log}\left(k\right)\right)$ operations. This is achieved by use of structured transformations such as the Discrete Cosine Transform (DCT).

Random projections can be real-valued (e.g., a randomized DCT) or complex-valued (e.g., a randomized Fast Fourier Transform (FFT)).

Currently the chapter contains one random projection routine that is fast and real-valued, f10daf.

The Singular Value Decomposition (SVD) is written as

where $\Sigma $ is an $m$ by $n$ matrix which is zero except for its $\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(m,n\right)$ diagonal elements, $U$ is an $m$ by $m$ orthogonal matrix, and $V$ is an $n$ by $n$ orthogonal matrix. The diagonal elements of $\Sigma $ are the singular values of $A$; they are real and non-negative, and are returned in descending order. The first $\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(m,n\right)$ columns of $U$ and $V$ are the left and right singular vectors of $A$, respectively.

$$A=U\Sigma {V}^{\mathrm{T}}\text{,}$$ |

If the numerical rank of $A$ is $r<\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(m,n\right)$ then $\Sigma $ has $r$ nonzero elements, and only $r$ columns of $U$ and $V$ are well-defined. In this case we can reduce $\Sigma $ to an $r$ by $r$ matrix, $U$ to an $m$ by $r$ matrix, and ${V}^{\mathrm{T}}$ to an $r$ by $n$ matrix.

RNLA algorithms can be used to compute the SVD more efficiently than deterministic alternatives such as f08kbf. Two scenarios where randomized SVD outperforms deterministic SVD are (i) low rank problems where randomized SVD can obtain machine precision results in less time than deterministic SVD, (ii) problems where only a low rank approximation of the matrix is needed.

One strategy used by some RNLA algorithms is to obtain, in the $m>n$ case, the rows of the matrix $A$ that span the projection space of ${A}^{\mathrm{T}}$; this is known as row extraction.

Building blocks, |

random projection with DCT (real) | f10daf |

Matrix factorization, |

SVD via row extraction (real) | f10caf |

The routines in this chapter contain an input argument called **state**. This argument is used to generate random variables. When **state** is initialized by a call to g05kff the random numbers are repeatable. When **state** is initialized by a call to g05kgf the random numbers are non-repeatable. Further details on random number generators in the NAG Library can be found in Chapter G05.

The routines in this chapter contain an input argument **k** that determines the size of the random projection. For example if the random projection is done by post-multiplication, **k** is the number of columns in $Y=A\Omega $.

Increasing **k** increases both the accuracy and the computational cost of RNLA routines. For example, if the numerical rank of a matrix, $A$, is $r<\mathrm{min}\phantom{\rule{0.125em}{0ex}}\left(m,n\right)$, it is possible to obtain an SVD that is accurate to within machine precision by setting **k** slightly bigger (e.g. 5) than $r$. For problems where a low rank approximation to $A$ is sufficient, **k** can be set to the required rank.

None.

None.

None.