f10dac 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.
The function may be called by the names: f10dac or nag_rnla_randproj_dct_real.
3Description
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 $\{\mathrm{-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 $\mathit{O}\left(mn\mathrm{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).
4References
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
5Arguments
1: $\mathbf{trans}$ – Nag_TransTypeInput
On entry: specifies whether the operation pre-multiplies $A$ or post-multiplies $A$.
${\mathbf{trans}}=\mathrm{Nag\_NoTrans}$
Random projection is done by post-multiplication, $Y=A\Omega $.
${\mathbf{trans}}=\mathrm{Nag\_Trans}$
Random projection is done by pre-multiplication, $Y=\Omega A$.
Constraint:
${\mathbf{trans}}=\mathrm{Nag\_NoTrans}$ or $\mathrm{Nag\_Trans}$.
2: $\mathbf{m}$ – IntegerInput
On entry: $m$, the number of rows of the matrix $A$.
Constraint:
${\mathbf{m}}>0$.
3: $\mathbf{n}$ – IntegerInput
On entry: $n$, the number of columns of the matrix $A$.
Note: the dimension, $\mathit{dim}$, of this array is dictated by the requirements of associated functions that must have been previously called. This array MUST be the same array passed as argument state in the previous call to nag_rand_init_repeatable (g05kfc) or nag_rand_init_nonrepeatable (g05kgc).
On entry: contains information on the selected base generator and its current state.
On exit: contains updated information on the state of the generator.
8: $\mathbf{fail}$ – NagError *Input/Output
The NAG error argument (see Section 7 in the Introduction to the NAG Library CL Interface).
6Error Indicators and Warnings
NE_ALLOC_FAIL
Dynamic memory allocation failed.
See Section 3.1.2 in the Introduction to the NAG Library CL Interface for further information.
NE_BAD_PARAM
On entry, argument $\u27e8\mathit{\text{value}}\u27e9$ had an illegal value.
NE_INT
On entry, ${\mathbf{k}}=\u27e8\mathit{\text{value}}\u27e9$ and ${\mathbf{trans}}=\u27e8\mathit{\text{value}}\u27e9$. Constraint: if ${\mathbf{trans}}=\mathrm{Nag\_NoTrans}$, $0<{\mathbf{k}}\le {\mathbf{n}}$, if ${\mathbf{trans}}=\mathrm{Nag\_Trans}$, $0<{\mathbf{k}}\le {\mathbf{m}}$.
On entry, ${\mathbf{m}}=\u27e8\mathit{\text{value}}\u27e9$. Constraint: ${\mathbf{m}}>0$.
On entry, ${\mathbf{n}}=\u27e8\mathit{\text{value}}\u27e9$. Constraint: ${\mathbf{n}}>0$.
On entry, ${\mathbf{pda}}=\u27e8\mathit{\text{value}}\u27e9$. Constraint: ${\mathbf{pda}}\ge {\mathbf{m}}$.
On entry, state vector has been corrupted or not initialized.
NE_INTERNAL_ERROR
An internal error has occurred in this function. Check the function call and any array sizes. If the call is correct then please contact NAG for assistance.
See Section 7.5 in the Introduction to the NAG Library CL Interface for further information.
NE_NO_LICENCE
Your licence key may have expired or may not have been installed correctly.
See Section 8 in the Introduction to the NAG Library CL Interface for further information.
7Accuracy
The accuracy of algorithms that use f10dac depend on the extent to which the random projection, $Y$, captures the range (i.e., column space) of the matrix $A$. More formally, the following probabilistic error bound holds,
with failure probability at most $\mathit{O}\left({k}^{\mathrm{-1}}\right)$, and where ${\sigma}_{k+1}$ is the $(k+1)$th singular value and the norm on the left-hand side of the equation is the spectral norm.
The matrix $(I-{P}_{Y})$ is sometimes referred to as the orthogonal projector onto the complementary subspace, ${\mathrm{range}\left({P}_{Y}\right)}^{\perp}$.
f10dac is threaded by NAG for parallel execution in multithreaded implementations of the NAG Library.
Please consult the X06 Chapter Introduction for information on how to control and interrogate the OpenMP environment used within this function. Please also consult the Users' Note for your implementation for any additional implementation-specific information.
9Further Comments
f10dac uses the same DCT as c06rfc. The time taken by c06rfc is fastest if the only prime factors of the projected dimension are $2$, $3$ or $5$. In order to make the performance of f10dac less sensitive to the size of the projected dimension, the input, a, is padded with zeros up to the nearest power of $2$ or the nearest $1000$, whichever is smaller.
10Example
This example applies a random projection using the DCT to the $6\times 6$ matrix
It then computes a $6\times 5$ orthornormal matrix $Q$ and a probabilistic error bound, $E$ that quantifies how well the range of $Q$ approximates the range of $A$. The matrix $Q$ is calculated through a $QR$ factorization of the projection $Y=A\Omega $. The error bound is based on the following result from Section 4.3 of Halko et al. (2011). Given a sequence $\{{\omega}^{\left(i\right)}:i=1,2,\dots ,r\}$ of standard Gaussian vectors, where $r$ is some positive integer, then the measure, $E$, of the error in how well the projection captures the range of $A$ is given by
where $\Vert \xb7\Vert $ is the spectral norm when applied to a matrix and the Euclidean norm when applied to a vector.
The exact approximation error $\Vert (I-Q{Q}^{*})A\Vert $ is also computed for comparison.
This example is constructed so that the true rank of $A$ is $4$: the last $3$ rows are identical so the matrix only has $4$ linearly independent rows. This means that when $k\ge 4$ the accuracy of $Q$ will be close to machine precision.