Sparse Sign Sketching

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

Sparse Sign matrix is defined as

\[ \mathbf{S} = \sqrt{\frac{n}{d}} [\vec{s}_1 \quad \vec{s}_2 \quad ... \quad \vec{s}_n\]

where the columns \( \vec{s}_k \) are i.i.d. random vectors and are constructed by drawning d i.i.d. random signs and placing them in d uniformly random coordinates. They have similar performance to the Gaussian embedding, but only requires O(dn) space in memory and can be applied O(dn) time to a vector. While the main disadvantage is that it uses sparse arithmetic.

Template Parameters:

• T – Data type of the sketching matrix.

• L – Location of the data.

Public Functions

SparseSignSketch() = default

Creates a new sketching operator.

inline SparseSignSketch(const SparseSignSketchOptions &options)

Creates a new sketching operator according to options.

Parameters:

options – [in] sketching parameters

virtual ~SparseSignSketch() = default

Destructor.

inline void set_params(const SparseSignSketchOptions &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 SparseSignSketchOptions

Options for the SRTTSketch.

Public Members

index_t input_size

The number of rows of the input.

index_t sketch_size

Sketch size.

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.

index_t nz_per_col = 8

Set the number of nonzeros per column.