C++ Sparse Random Walks

class SparseRandomWalk

Subclassed by SparseBallWalk, SparseBarrierWalk, SparseHitAndRun

Public Functions

inline SparseRandomWalk(double err = 1e-6)

initialization of Sparse Random Walk class

Parameters:

err – error constant

virtual MatrixXd generateCompleteWalk(const int num_steps, const VectorXd &init, const SparseMatrixXd &A, const VectorXd &b, int k, int burnin, int thin, int seed)

Generate values from the RandomWalk.

Parameters:

  • num_steps – number of steps wanted to take

  • init – initial starting point

  • A – polytope matrix

  • b – polytope vector

  • k – k values >= 0 constraint

  • burnin – number of steps to burn

  • thin – thinning parameter

  • seed – seed for reproducibility

Returns:

(niter - burnin)//thin by d (dimension of x) matrix

class SparseBallWalk : public SparseRandomWalk

Public Functions

inline SparseBallWalk(double r)

initialization of Sparse Ball Walk class

Parameters:

r – spread parameter

virtual MatrixXd generateCompleteWalk(const int niter, const VectorXd &init, const SparseMatrixXd &A, const VectorXd &b, int k, int burnin, int thin, int seed) override

generate values from the Ball walk (constrained)

Parameters:

  • niter – number of steps wanted to take

  • init – initial starting point

  • A – polytope matrix

  • b – polytope vector

  • k – k values >= 0 constraint

  • burnin – number of initial steps to cut

  • thin – thinning parameter

  • seed – seed for reproducibility

Returns:

(niter - burnin)//thin by d (dimension of x) matrix

class SparseHitAndRun : public SparseRandomWalk

Public Functions

inline SparseHitAndRun(double r, double err = 1e-6)

initialization of Sparse Hit and Run class

Parameters:

  • r – spread parameter

  • err – error constant

virtual MatrixXd generateCompleteWalk(const int niter, const VectorXd &init, const SparseMatrixXd &A, const VectorXd &b, int k, int burnin, int thin, int seed) override

generate values from the Hit and Run

Parameters:

  • niter – number of steps wanted to take

  • init – initial starting point

  • A – polytope matrix

  • b – polytope vector

  • k – k values >= 0 constraint

  • burnin – number of initial steps to cut

  • thin – thinning parameter

  • seed – seed for reproducibility

Returns:

(niter - burnin)//thin by d (dimension of x) matrix

class SparseBarrierWalk : public SparseRandomWalk

Subclassed by SparseDikinLSWalk, SparseDikinWalk, SparseJohnWalk, SparseVaidyaWalk

Public Functions

inline SparseBarrierWalk(double r, double err = 1e-6)

initialization of Sparse Barrier Walk class

Parameters:

  • r – spread parameter

  • err – error term parameter

virtual VectorXd generateWeight(const VectorXd &x, const SparseMatrixXd &A, int k)

generate weight for slack inverse

Parameters:

  • x – slack variable

  • A – polytope constraint

  • k – k values >= 0 constraint

Returns:

Vector

virtual MatrixXd generateCompleteWalk(const int niter, const VectorXd &init, const SparseMatrixXd &A, const VectorXd &b, int k, int burnin, int thin, int seed) override

generate values from the SparseBarrierWalk

Parameters:

  • niter – number of steps wanted to take

  • init – initial starting point

  • A – polytope matrix

  • b – polytope vector

  • k – k values >= 0 constraint

  • burnin – number of initial steps to cut

  • thin – thinning parameter

  • seed – seed for reproducibility

Returns:

(niter - burnin)//thin by d (dimension of x) matrix

virtual void setDistTerm(int d, int n)

set distribution constant

Parameters:

  • d – polytope matrix

  • n – polytope vector

class SparseDikinWalk : public SparseBarrierWalk

Public Functions

inline SparseDikinWalk(double r, double err = 1e-6)

initialization of Sparse Dikin Walk class

Parameters:

  • r – spread parameter

  • err – error constant

virtual VectorXd generateWeight(const VectorXd &x, const SparseMatrixXd &A, int k) override

generate weight (identity matrix)

Parameters:

  • x – slack variable

  • A – polytope constraint

  • k – k values >= 0 constraint

Returns:

Vector

class SparseVaidyaWalk : public SparseBarrierWalk

Public Functions

inline SparseVaidyaWalk(double r, double err = 1e-6)

constructor for Vaidya Walk class

Parameters:

  • r – spread parameter

  • err – error constant

virtual VectorXd generateWeight(const VectorXd &x, const SparseMatrixXd &A, int k) override

generate weight (leverage score calculation)

Parameters:

  • x – slack variable

  • A – polytope constraint

  • k – k values >= 0 constraint

Returns:

Vector

class SparseJohnWalk : public SparseBarrierWalk

Public Functions

inline SparseJohnWalk(double r, double lim = 1e-5, int max_iter = 1000, double err = 1e-5)

initialization of Sparse John Walk class

Parameters:

  • r – spread parameter

  • lim – limit in l-infinity norm

  • max_iter – maximum number of iterations in fixed iteration

  • err – error constant

virtual VectorXd generateWeight(const VectorXd &x, const SparseMatrixXd &A, int k) override

generate weight by solving fixed point iteration

Parameters:

  • x – slack variable

  • A – polytope constraint

  • k – k values >= 0 constraint

Returns:

Vector

class SparseDikinLSWalk : public SparseBarrierWalk

Public Functions

inline SparseDikinLSWalk(double r, double g_lim = 0.01, double step_size = 0.1, int max_iter = 1000, double err = 1e-6)

initialization of Sparse Lee Sidford Walk class

Parameters:

  • r – spread parameter

  • g_lim – gradient descent norm limit

  • step_size – size of gradient descent step

  • max_iter – maximum number of iterations in gradient descent

  • err – error constant

virtual VectorXd generateWeight(const VectorXd &x, const SparseMatrixXd &A, int k) override

generate weight by solving convex optimization task

Parameters:

  • x – slack variable

  • A – polytope constraint

  • k – k values >= 0 constraint

Returns:

Vector