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().

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 $\mathbb{R}^{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 $\mathbb{R}^{4096}$ can take a second, instead of a minute).

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.

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    1

Here 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.

MIT

• fort 0.01 package manual (pdf)

• Random projection (Wikipedia)

• Johnson-Lindenstrauss lemma (Wikipedia)

1. Krzysztof M. Choromanski, Mark Rowland, and Adrian Weller. “The unreasonable effectiveness of structured random orthogonal embeddings.”, NIPS (2017).

2. Felix Xinnan X. Yu, Ananda Theertha Suresh, Krzysztof M. Choromanski, Daniel N. Holtmann-Rice, and Sanjiv Kumar. “Orthogonal random features.”, NIPS (2016).

3. Marcin Moczulski, Misha Denil, Jeremy Appleyard, and Nando de Freitas. “ACDC: A structured efficient linear layer.”, arXiv:1511.05946 (2015).

4. Quoc Le, Tamás Sarlós and Alex Smola. “Fastfood - approximating kernel expansions in loglinear time.”, ICML (2013).

5. Ali Rahimi, and Benjamin Recht. “Random features for large-scale kernel machines”, NIPS (2007).