naginterfaces.library.rnla.randproj_​dct_​real

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

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

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

https://support.nag.com/numeric/nl/nagdoc_30.3/flhtml/f10/f10daf.html

Parameters

transstr, length 1

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

$trans=\text{'N'}$

Random projection is done by post-multiplication, $Y=A\Omega$.

$trans=\text{'T'}$

Random projection is done by pre-multiplication, $Y=\Omega A$.

afloat, array-like, shape $(m,n)$

The $m\times n$ matrix $A$.

kint

$k$, number of columns in the random projection, $Y=A\Omega$.

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 $trans=\text{'N'}$, the $m\times k$ random projection of $A$.

If $trans=\text{'T'}$, the $k\times n$ random projection of $A$.

Raises

NagValueError

(errno $1$)

On entry, $trans=⟨value⟩$.

Constraint: $trans=\text{'N'}$ or $\text{'T'}$.

(errno $2$)

On entry, $m=⟨value⟩$.

Constraint: $m>0$.

(errno $3$)

On entry, $n=⟨value⟩$.

Constraint: $n>0$.

(errno $4$)

On entry, $k=⟨value⟩$ and $trans=⟨value⟩$.

Constraint: if $trans=\text{'N'}$, $0<k\le n$, if $trans=\text{'T'}$, $0<k\le m$.

(errno $6$)

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

Notes

A random projection is written as either

$$Y=A\Omega$$

or

$$Y=\Omega A\text{,}$$

where $A$ is a real $m\times n$ matrix, $\Omega$ is an $n\times k$ matrix in the first case, and a $k\times m$ 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

$$\Omega =DFC\text{,}$$

where $D$ is a diagonal matrix whose values are uniformly distributed on the set $\{-1,+1\}$, $F$ is a DCT, and $C$ 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

$$\Omega =RFD\text{.}$$

The operators $D$ and $F$ are as above and $R$ 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 $O\left(mn\log \left(k\right)\right)$. 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