F10 Chapter Introduction : NAG Library, Mark 27

F10 (Rnla)

Chapter Introduction FL CL

NAG FL Interface
F10 (Rnla)
Randomized Numerical Linear Algebra

1 Scope of the Chapter

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.

2 Background to the Problems

2.1 Building Blocks

RNLA algorithms use random projections in order to reduce problem dimension. If

A

is an

m \times n

matrix, the random projection of

A

is either,

Y = A Ω

where

A

is a real

m \times n

matrix and

Ω

is an

n \times k

matrix, or

Y = Ω A

where

Ω

is an

k \times m

matrix.

Random projections can be classified as slow or fast. Slow random projections have the same computational cost as a standard matrix multiplication, i.e.,

O (m n k)

operations. Fast random projections have a lower computational cost, typically

O (m n \log (k))

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.

2.2 Matrix factorization

f10caf is provided for factorizing a general rectangular

m \times n

matrix

A

The Singular Value Decomposition (SVD) is written as

A = U Σ V^{T},

where

Σ

is an

m \times n

matrix which is zero except for its

\min (m, n)

diagonal elements,

U

is an

m \times m

orthogonal matrix, and

V

is an

n \times n

orthogonal matrix. The diagonal elements of

Σ

are the singular values of

A

; they are real and non-negative, and are returned in descending order. The first

\min (m, n)

columns of

U

and

V

are the left and right singular vectors of

A

, respectively.

If the numerical rank of

A

r < \min (m, n)

then

Σ

has

r

nonzero elements, and only

r

columns of

U

and

V

are well-defined. In this case we can reduce

Σ

to an

r \times r

matrix,

U

to an

m \times r

matrix, and

V^{T}

to an

r \times 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^{T}

; this is known as row extraction.

3 Recommendations on Choice and Use of Available Routines

Building blocks,

random projection with DCT (real)

f10daf

Matrix factorization,

SVD via row extraction (real)

f10caf

3.1 Initializing seed for random number generators

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.

3.2 Choosing an appropriate value for the size of the random projection

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 Ω

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 < \min (m, n)

, 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.

NAG FL Interface
F10 (Rnla)
Randomized Numerical Linear Algebra

▸▿ Contents

1 Scope of the Chapter

2 Background to the Problems

2.1 Building Blocks

2.2 Matrix factorization

3 Recommendations on Choice and Use of Available Routines

3.1 Initializing seed for random number generators

3.2 Choosing an appropriate value for the size of the random projection

4 Auxiliary Routines Associated with Library Routine Arguments

5 Withdrawn or Deprecated Routines

6 References

NAG FL InterfaceF10 (Rnla)Randomized Numerical Linear Algebra

▸▿ Contents

1 Scope of the Chapter

2 Background to the Problems

2.1 Building Blocks

2.2 Matrix factorization

3 Recommendations on Choice and Use of Available Routines

3.1 Initializing seed for random number generators

3.2 Choosing an appropriate value for the size of the random projection

4 Auxiliary Routines Associated with Library Routine Arguments

5 Withdrawn or Deprecated Routines

6 References

NAG FL Interface
F10 (Rnla)
Randomized Numerical Linear Algebra