bnmf_algs::details::SampleOnesNoReplaceComputer< Scalar > Class Template Reference

Computer type that will compute the next sample from a given matrix without replacement when its operator() is invoked. More...

#include <sampling.hpp>

Public Member Functions
	SampleOnesNoReplaceComputer (const matrix_t< Scalar > &X)
	Construct a new SampleOnesNoReplaceComputer. More...
void	operator() (size_t curr_step, std::pair< int, int > &prev_val)
	Function call operator that will compute the next sample without replacement in-place. More...

Detailed Description

template<typename Scalar>
class bnmf_algs::details::SampleOnesNoReplaceComputer< Scalar >

Computer type that will compute the next sample from a given matrix without replacement when its operator() is invoked.

SampleOnesNoReplaceComputer will generate the next std::pair<int, int> value from the previous value passed to its operator(). This operation is performed in-place.

When computing the next sample, a systematic sampling technique is used. Each entry of the input matrix, \(X_{ij}\), is sampled \(\lceil X_{ij} \rceil\) many times. This can be thought of as sampling each entry one-by-one. We call the implemented procedure systematic because, conceptually, samples from every \(X_{ij}\) are distributed on a timeline. Afterwards, all sample timelines are merged and the sample closest to our current timestep is chosen. This is easily implemented using a minimum heap ordered according to timestamp of each sample.

The above described procedure is conceptual. To decrease the space, and therefore time, complexity of the heap ordering procedures, timestamp of the next sample is computed just after the current sample is drawn. Therefore, the maximum number of elements in the heap is exactly \(xy\) where \(x\) and \(y\) are the dimensions of the input matrix. This number gradually decreases as matrix entries become less than or equal to 0 and get discarded from the heap.

Sample timestamps are drawn from Beta distribution, \(\mathcal{B}(\alpha, \beta)\). Here, \(\alpha = X_{ij} - t + 1\) and \(\beta = 1\) where \(t\) is the number of samples drawn from entry \(X_{ij}\).

Template Parameters

Scalar

Type of the matrix entries that will be sampled.

Constructor & Destructor Documentation

template<typename Scalar >

bnmf_algs::details::SampleOnesNoReplaceComputer< Scalar >::SampleOnesNoReplaceComputer ( const matrix_t< Scalar > &  X )

inlineexplicit

Construct a new SampleOnesNoReplaceComputer.

This method constructs the data structures that will be used during sampling procedure. In particular, a min heap of elements and their indices is constructed in time linear in the number of matrix entries.

Parameters

X	Matrix \(X\) that will be used during sampling.

Remarks

Time complexity is \(O(N)\) where \(N\) is the number of elements of X.

Member Function Documentation

template<typename Scalar >

void bnmf_algs::details::SampleOnesNoReplaceComputer< Scalar >::operator() ( size_t  curr_step, std::pair< int, int > &  prev_val  )

inline

Function call operator that will compute the next sample without replacement in-place.

After this function exits, the object referenced by prev_val will be modified to store the next sample. To read a general description of the sampling procedure, refer to class documentation.

Note that SampleOnesComputer object satisfies the bnmf_algs::util::Generator and bnmf_algs::util::ComputationIterator Computer interface. Hence, a sequence of samples may be generated efficiently by using this Computer with bnmf_algs::util::Generator or bnmf_algs::util::ComputationIterator.

Parameters

curr_step	Current step of the sampling computation.
prev_val	Previously sampled value to modify in-place.

Remarks

Time complexity is \(O(\log{N})\) where \(N\) is the number of nonzero entries of matrix parameter X that are not completely sampled yet.

---

The documentation for this class was generated from the following file:

• src/util/sampling.hpp