SRTT Sketching

template<Number T, DataLocation L = Host>
class SRTTSketch

Subsampled Trigonometric Transform (SRTT), where the sketching operator \( \mathbf{S} \) is defined as

\[ \mathbf{S} = \mathbf{R} \mathbf{\Theta} \mathbf{E} \mathbf{\Pi}\]

where \( \mathbf{R} \) is a random restriction (i.e., it randomly selects rows of the matrix), \( \mathbf{E} \) is a random sign flip matrix (i.e., \( e_{ii} = \text{UNIFORM}(\pm 1) \)) and \( \mathbf{\Pi} \) is a random permutation matrix (optional). Note that none of these matrices are built explicitly, instead they are applied directly to the target vector or matrix.

The matrix \( \mathbf{\Theta}\) represents one of the following unitary trigonometric transforms:

• Discrete Fourier Transform (DFT): when T is a complex number.

• Discrete Cosine Transform (DCT): kDCT<1,2,3 or 4>.

• Discrete Hartley Transform (DHT): kHartley.

SRTTSketch will then call the FFTW library to compute \(\mathbf{\Theta} \vec{x}\) for some vector \( \mathbf{x} \).

Template Parameters:

• T – Data type of the sketching matrix.

• L – Location of the data. Must be Host.

Public Functions

SRTTSketch()

Creates a new sketching operator.

inline SRTTSketch(const SRTTSketchOptions &options)

Creates a new sketching operator according to options.

Parameters:

options – [in] sketching parameters

virtual ~SRTTSketch()

Destructor.

void set_params(const SRTTSketchOptions &options)

Sets the parameter of the sketching.

Parameters:

options – [in] sketching parameters

inline DCTResultVec operator()(VectorMap<T, L> v)

Calculates the random sketch of a vector v.

Parameters:

v – [in] input vector

Returns:

An abstract object representing the sketch

inline DCTResultMat operator()(MatrixMap<T, L> A)

Calculates the random sketch of a matrix A. The sketching is applied to each column of the matrix.

Parameters:

A – [in] input matrix

Returns:

An abstract object representing the sketch

struct SRTTSketchOptions

Options for the SRTTSketch.

Public Members

index_t input_size

The number of rows of the input.

index_t sketch_size

Sketch size.

SRTTType type = kDCT2

Type of DCT. When using complex values, this parameter is ignored.

uint128_t seed = random::DefaultGenerator::default_seed

Random seed for the random number generator.

uint128_t stream = random::DefaultGenerator::default_stream

Random stream for the random number generator.

bool permute_input = false

Indicate if the input will be permuted before applying the sketching.