The fort package provides convenient access to fast, structured, random linear transforms implemented in C++ (via ‘Rcpp’) that are (at least approximately) orthogonal or semi-orthogonal, and are often much faster than matrix multiplication, in the same spirit as the Fastfood, ACDC, HD and SD families of random structured transforms.
Useful for algorithms that require or benefit from uncorrelated random projections, such as fast dimensionality reduction (e.g., Johnson-Lindenstrauss transform) or kernel approximation (e.g., random kitchen sinks) methods.
For more technical details, see the reference page for fort().
Illustration
This plot shows a speed comparison between using a fort-type transform vs. a matrix multiplication, for different transform sizes, on commodity hardware.
Here we can see that, for transform sizes in spaces larger than ℝ64, you can obtain significant speed-ups through the use of structured transforms (such as the ones implemented in fort) instead of matrix multiplication. In particular, the time elapsed can go down by 10 to 100 times, for practical transform sizes (e.g., an orthogonal transform in ℝ4096 can take a second, instead of a minute).
Installation
You can install the development version of fort from GitHub with:
# install.packages("devtools")
devtools::install_github("tomessilva/fort")Note: you will need to have the Rcpp and RcppArmadillo packages installed, as well as a working build environment (to compile the C++ code), in order to install a development version of fort.
Example
This is a basic example which shows how to use fort in practice:
library(fort)
(fast_transform <- fort(4)) # fast orthogonal transform from R^4 to R^4
#> fort linear operation: R^4 -> [fft2] -> R^4
matrix_to_transform <- diag(4) # 4 x 4 identity matrix
(new_matrix <- fast_transform %*% matrix_to_transform) # transformed matrix
#> [,1] [,2] [,3] [,4]
#> [1,] 0.7267114 -0.1421089 0.3232329 -0.5892504
#> [2,] 0.2627348 -0.7866239 -0.5065061 0.2358916
#> [3,] -0.5892504 -0.3232329 -0.1421089 -0.7267114
#> [4,] 0.2358916 0.5065061 -0.7866239 -0.2627348
(inverse_transform <- solve(fast_transform)) # get inverse transform
#> fort linear operation (inverted): R^4 <- [fft2] <- R^4
round(inverse_transform %*% new_matrix, 12) # should recover the identity matrix
#> [,1] [,2] [,3] [,4]
#> [1,] 1 0 0 0
#> [2,] 0 1 0 0
#> [3,] 0 0 1 0
#> [4,] 0 0 0 1Here is a comparison of using a fort transform against a simple matrix multiplication, in terms of speed:
library(fort)
matrix_to_transform <- diag(1024) # 1024 x 1024 identity matrix
fast_transform <- fort(1024) # fast orthogonal transform from R^1024 to R^1024
slow_transform <- as.matrix(fast_transform) # the same, but in matrix form
# time it takes for the fast transform
system.time(for (i in 1:100) test <- fast_transform %*% matrix_to_transform, gcFirst = TRUE)
#> user system elapsed
#> 5.50 2.12 8.00
# time it takes for the equivalent slow transform (via matrix multiplication)
system.time(for (i in 1:100) test <- slow_transform %*% matrix_to_transform, gcFirst = TRUE)
#> user system elapsed
#> 70.57 0.61 77.95 Note: in this case, using a fort fast transform leads to a speed-up of about 10x compared to the use of matrix multiplication.
For more information on how to use fort in practice, check out the package’s vignette.
References
Krzysztof M. Choromanski, Mark Rowland, and Adrian Weller. “The unreasonable effectiveness of structured random orthogonal embeddings.”, NIPS (2017).
Felix Xinnan X. Yu, Ananda Theertha Suresh, Krzysztof M. Choromanski, Daniel N. Holtmann-Rice, and Sanjiv Kumar. “Orthogonal random features.”, NIPS (2016).
Marcin Moczulski, Misha Denil, Jeremy Appleyard, and Nando de Freitas. “ACDC: A structured efficient linear layer.”, arXiv:1511.05946 (2015).
Quoc Le, Tamás Sarlós and Alex Smola. “Fastfood - approximating kernel expansions in loglinear time.”, ICML (2013).
Ali Rahimi, and Benjamin Recht. “Random features for large-scale kernel machines”, NIPS (2007).