treeapprox_binsearch

installation:

build the mex file with

make treeapprox_binsearch_mexfile



syntax:

[support, lambda_low, lambda_high, num_iter] = treeapprox_binsearch(x, d, k_low, k_high, opts)

square x if you want a l2 guarantee
take abs of x if you want a l1 guarantee
d is the degree of the tree
the root of the tree is assumed to be at the first element in the row vector x
the children are at positions 2, 3, etc.

opts is optional. currently it has two fields:
- verbose
  for benchmarking, run with verbose = false
- max_num_iterations
- tree_layout
  either wavelet_tree or complete_tree . Use wavelet_tree in conjunction with wavelet coefficients from Matlab's wavedec / wavedec2 function. If you are using wavedec2, make sure to first rearrange the coefficients with rearrange_wavedec2 (also part of this repository).


======================================================
treeexact_fulltable

O(k * n) DP with O(k * n * d) memory


installation:

build the mex file with

make treeexact_fulltable_mexfile



syntax:

support = treeexact_fulltable(x, d, k)

square x if you want a l2 guarantee
take abs of x if you want a l1 guarantee

d is the degree of the tree

the root of the tree is assumed to be at the first element in the row vector x
the children are at positions 2, 3, etc.


======================================================
treeexact_smalltable

O(k * n * log n) DP with O(k * d * log n) memory


installation:

build the mex file with

make treeexact_smalltable_mexfile



syntax:

support = treeexact_smalltable(x, d, k)

square x if you want a l2 guarantee
take abs of x if you want a l1 guarantee

d is the degree of the tree

the root of the tree is assumed to be at the first element in the row vector x
the children are at positions 2, 3, etc.