Draw a rotation that spreads outlier energy over all coordinates

Quantizers do badly when a few coordinates carry most of the norm, and key embeddings are like that. Rotating first makes the coordinates exchangeable. The rotation must be genuinely orthogonal, not merely Gaussian, or it would change the norms it is meant to preserve.

Usage

Tqrot(d, seed = 1)

Arguments

d

Dimension.

seed

Seed for the shared generator.

Value

List with Q, estimate, d, orth_err.

Details

Determinism: Gaussian entries come from the shared Lehmer minstd stream and the factorisation is modified Gram-Schmidt, whose R diagonal is non-negative by construction, so both arms return the same Q. A LAPACK-versus-LINPACK QR would not.

Formula: A ~ N(0,1)^{d x d}, Q, R = QR(A), return Q.

References

Zandieh, A., Daliri, M. & Han, I. (2024). arXiv:2406.03482, section 4.1 (orthogonalized JL transform).

Examples

Tqrot(d = 4L, seed = 1)
#> $Q
#>             [,1]       [,2]        [,3]      [,4]
#> [1,] -0.90069344 -0.3532104  0.02686122 0.2515396
#> [2,]  0.40870641 -0.6830689 -0.28383932 0.5346131
#> [3,] -0.14003738  0.4323105 -0.86842086 0.1983491
#> [4,]  0.04582497  0.4709213  0.40565863 0.7820321
#> 
#> $estimate
#> [1] -0.9006934
#> 
#> $d
#> [1] 4
#> 
#> $orth_err
#> [1] 9.006913e-16
#> 
#> $method
#> [1] "Random orthogonal rotation, QR of a Gaussian matrix"
#> 
#> attr(,"class")
#> [1] "morie_rich_result" "list"