naginterfaces.library.rnla.randproj_​dct_​real

naginterfaces.library.rnla.randproj_dct_real(trans, a, k, statecomm)[source]

randproj_dct_real computes a fast random projection of a real matrix using a Discrete Cosine Transform (DCT). The function can be used as a building block in Randomised Numerical Linear Algebra (RNLA) algorithms, such as decompositions, Singular Value Decompositions (SVDs), and (approximate) least squares solvers.

For full information please refer to the NAG Library document for f10da

https://www.nag.com/numeric/nl/nagdoc_29.3/flhtml/f10/f10daf.html

Parameters
transstr, length 1

Specifies whether the operation pre-multiplies or post-multiplies .

Random projection is done by post-multiplication, .

Random projection is done by pre-multiplication, .

afloat, array-like, shape

The matrix .

kint

, number of columns in the random projection, .

statecommdict, RNG communication object, modified in place

RNG communication structure.

This argument must have been initialized by a prior call to rand.init_repeat or rand.init_nonrepeat.

Returns
afloat, ndarray, shape

If , the random projection of .

If , the random projection of .

Raises
NagValueError
(errno )

On entry, .

Constraint: or .

(errno )

On entry, .

Constraint: .

(errno )

On entry, .

Constraint: .

(errno )

On entry, and .

Constraint: if , , if , .

(errno )

On entry, [‘state’] vector has been corrupted or not initialized.

Notes

A random projection is written as either

or

where is a real matrix, is an matrix in the first case, and a matrix in the second case. These cases are referred to as random projection by post-multiplication and random projection by pre-multiplication, respectively.

When a random projection by post-multiplication uses the DCT, it is written as

where is a diagonal matrix whose values are uniformly distributed on the set , is a DCT, and is a matrix that selects a subset of columns, uniformly at random.

When a random projection by pre-multiplication uses the DCT, it is written as

The operators and are as above and is a matrix that selects a subset of rows, again uniformly at random.

None of these matrix operators require a full matrix-matrix product to be computed. The computational complexity of applying this type of random projection is . More details of the DCT-based random projection can be found in Avron et al. (2010).

The DCT-based random projection is closely related to the Subsampled Random Fourier Transform (SRFT) presented in Section 4.6 of Halko et al. (2011).

References

Avron, H, Maymounkov, P and Toledo, S, 2010, Blendenpik: Supercharging LAPACK’s least-squares solver, SIAM J. Sci. Comput. (32(3)), 1217–1236

Halko, N, 2012, Randomized methods for computing low-rank approximations of matrices, PhD thesis

Halko, N, Martinsson, P G and Tropp, J A, 2011, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev. (53(2)), 217–288, https://epubs.siam.org/doi/abs/10.1137/090771806