FRP: Fast Random Projections
We use Blaze for fast linear algebra, Sleef for fast trigonometric operations, Fast Fast-Hadamard Transform from FALCONN-LIB for the Fast Hadamard Transform, FFTW3 for the FFT, and boost for special functions and random number generators. Only required boost headers are provided as submodules and no installation of boost is required.
ojlt
executable, in C++ programs accessing include/frp/jl.h, and using python bindings.cd python && python3 setup.py install
.make
should compile a variety of tests.
We assume you're using BLAS for your linear algebra; to avoid doing that, modify the Makefile and remove the -DBLAZE*
flags.
To specify a different blas header file, use the CBLASFILE variable when compiling:
make ojlt CBLASFILE=mkl_cblas.h
# Or, use an environmental variable
export CBLASFILE=mkl_cblas.h && \
make ojlt
The initial design of this library was to implement methods from https://arxiv.org/abs/1703.00864. The core transformss on which it is built are fast fast-hadamard transform accelerated structured matrix vector products. This has applications in memory-efficient, accelerated Johnson-Lindenstrauss Transforms, gaussian kernel approximation for linearizing datasets and FastFood/Adaptive Random Spinners.
Notes:
During construction, it may be advantageous to use a std::set to maintain sorted indexes (logarithmic update time), whereas at query time, it's faster to use a contiguous array. We provide the cvt function, which copies the index, but converts the sorted index type from what it used to be (usually a red-black tree) into the destination type, by default an always-sorted array.
We suggest doing this for the purposes of faster construction and faster queries.
Additionally, we do not store any points, just references to them.
When using a non-default container which supports lower_bound functionality, one needs to both use std::less<void>
for a comparator and overload has_lower_bound_mf
struct.