Package com.apple.foundationdb.linear

Class FhtKacRotator

java.lang.Object
com.apple.foundationdb.linear.FhtKacRotator
All Implemented Interfaces:
LinearOperator, VectorOperator
public final class FhtKacRotator extends Object implements LinearOperator
FhtKac-like random orthogonal rotator which implements LinearOperator.

An orthogonal rotator conceptually is an orthogonal matrix that is applied to some vector x yielding a new vector y that is rotated in some way along its n dimensions. Important to notice here is that such a rotation preserves distances/lengths as well as angles between vectors.

Practically, we do not want to materialize such a rotator in memory as for n dimensions that would amount to n^2 cells. In addition to that multiplying a matrix with a vector computationally is O(n^2) which is prohibitively expensive for large n.

We also want to achieve some sort of randomness with these rotations. For small n, we can start by creating a randomly generated matrix and decompose it using QR-decomposition into an orthogonal matrix Q and an upper triangular matrix R. That matrix Q is indeed random (see matrix Haar randomness) and what we are actually trying to find. For larger R this approach becomes impractical as Q needs to be represented as a dense matrix which increases memory footprint and makes rotations slow (see above).

The main idea is to use several operators in conjunction:

  • K which is orthogonal and applies several Givens rotation at once.
  • D_n which are Random Rademacher diagonal sign matrices, i.e. matrices that are conceptually all 0 except for the diagonal which contains any combination -1, 1. These matrices are also orthogonal. In particular, it flips only the signs of the elements of some other matrix when applied to it.
  • H a Hadamard matrix of a suitable size.

All these linear operators are combined in a way that we eventually compute the result of 

 
     x' = D1 H D_2 H ... D_(R-1) H D_(R) H K x
(for R rotations). None of these operators require a significant amount of memory (O(R * n) bits for signs). They perform the complete rotation in O(R * (n log n)).