How Random Orthogonal Rotation Stabilizes Coordinate Distributions in Turbovec

Random orthogonal rotation stabilizes coordinate distributions by applying a deterministic orthogonal matrix that preserves L2 norms while making each coordinate follow an identical marginal distribution, ensuring consistent statistical properties for downstream quantization.

Turbovec is a Rust-based vector quantization library that employs random orthogonal rotation to preprocess high-dimensional vectors before quantization. This technique, implemented in the rotation.rs module, ensures that coordinate distributions become statistically stable and isotropic, regardless of the original data orientation. By rotating vectors with a fixed random seed before processing, the library guarantees that the downstream quantizer operates on coordinates with predictable, uniform statistical properties.

Generating the Rotation Matrix

The rotation matrix is constructed deterministically using a fixed seed (ROTATION_SEED) to ensure reproducibility across different runs and machines.

Gaussian Sampling and QR Decomposition

In turbovec/src/rotation.rs, the library generates the orthogonal matrix by:

1. Sampling a Gaussian matrix using the crate-wide ROTATION_SEED
2. Performing QR decomposition on the Gaussian matrix
3. Fixing the sign of the resulting $Q$ matrix so that the diagonal of $R$ remains non-negative

This process yields a true orthogonal matrix where $Q^T Q = I$, meaning the transformation preserves Euclidean distances while redistributing coordinate values.

use turbovec::rotation::make_rotation_matrix;

/// Generate a 128×128 orthogonal rotation matrix
let rot = make_rotation_matrix(128);

/// Simple helper to apply the matrix to a vector
fn mat_vec(m: &[f32], v: &[f32], dim: usize) -> Vec<f32> {
    let mut out = vec![0.0f32; dim];
    for i in 0..dim {
        let mut acc = 0.0;
        for j in 0..dim {
            acc += m[i * dim + j] * v[j];
        }
        out[i] = acc;
    }
    out
}

// Example input vector (randomly generated or real data)
let x = vec![0.5f32; 128];   // a dummy unit-norm vector
let y = mat_vec(&rot, &x, 128);   // y = Q * x

// Verify norm preservation (optional)
let norm = |v: &[f32]| v.iter().map(|c| c * c).sum::<f32>().sqrt();
assert!((norm(&x) - norm(&y)).abs() < 1e-3);

Why Rotation Stabilizes Distributions

The orthogonal transformation provides three critical stability guarantees that improve quantization performance and reduce bias.

Norm Preservation

Because $Q$ is orthogonal, the rotation preserves the L2 norm of any input vector. The preserves_norm test in turbovec/tests/rotation.rs verifies that $|Qx|_2 = |x|_2$ for all inputs. This guarantee ensures that the quantizer in src/codebook.rs receives vectors with the same magnitude as the original data, preventing scale distortion during the quantization process.

Coordinate-wise Distribution Stability

For unit-norm vectors uniformly sampled from the sphere $S^{d-1}$, each coordinate of the rotated vector $y = Qx$ follows an identical marginal distribution—a Beta distribution with parameters $\frac{1}{2}$ and $\frac{d-1}{2}$. The orthogonal transformation mixes the original coordinates uniformly, making every coordinate statistically identical. This means the distribution of each coordinate becomes stable and independent of the original orientation of the data, ensuring the quantizer sees well-behaved, isotropic coordinates regardless of input structure.

Deterministic Reproducibility

The ROTATION_SEED ensures the same rotation matrix regenerates on every run. The test deterministic_for_same_dim in turbovec/tests/rotation.rs confirms that identical dimensions produce identical matrices across different executions. This determinism guarantees reproducible results across builds and machines, while inverse_round_trip_via_transpose verifies that $Q^T Q = I$ holds exactly, confirming the matrix is truly orthogonal.

Verification and Testing

Turbovec includes a comprehensive test suite in turbovec/tests/rotation.rs that validates the mathematical properties required for distribution stabilization:

• orthogonality: The orthogonal_across_dims test checks $Q^T Q = I$ for multiple dimensions
• norm preservation: Confirms that rotation does not alter vector magnitudes
• determinism: Validates that the same seed produces identical matrices
• invertibility: Confirms that the transpose correctly reverses the rotation

Run the verification suite with:

cargo test --test rotation

These tests ensure that the random orthogonal rotation behaves as a true isometry, providing the statistical guarantees required by the quantization pipeline in src/codebook.rs.

Summary

• Random orthogonal rotation in Turbovec uses a deterministic Gaussian matrix with fixed ROTATION_SEED and QR decomposition to generate orthogonal matrices.
• Norm preservation is guaranteed by the orthogonality property ($Q^T Q = I$), ensuring quantization operates on vectors with unchanged magnitudes.
• Distribution stabilization occurs because each rotated coordinate follows an identical Beta distribution, making the data isotropic and statistically uniform.
• Deterministic behavior ensures reproducibility across machines, with comprehensive tests verifying orthogonality, preservation, and invertibility.

Frequently Asked Questions

How does Turbovec ensure the rotation matrix is truly orthogonal?

Turbovec generates the matrix by sampling a Gaussian distribution and applying QR decomposition, then fixing the sign of the $Q$ matrix so that $R$ has a non-negative diagonal. The orthogonal_across_dims test in turbovec/tests/rotation.rs explicitly verifies that $Q^T Q = I$ for various dimensions, confirming the matrix satisfies the mathematical definition of orthogonality.

Why is determinism important for random orthogonal rotation?

Determinism ensures that every instance of Turbovec generates the identical rotation matrix for the same dimension using the crate-wide ROTATION_SEED. This guarantees reproducible quantization results across different machines and builds, preventing variance in search results that could occur if the rotation changed between runs.

What statistical distribution do coordinates follow after rotation?

After applying the random orthogonal rotation $Q$ to a unit-norm vector uniformly sampled from sphere $S^{d-1}$, each coordinate follows a Beta distribution with parameters $\frac{1}{2}$ and $\frac{d-1}{2}$. This identical marginal distribution across all coordinates ensures the quantizer processes statistically uniform data, reducing quantization bias and improving recall.

How does rotation improve vector quantization performance?

By stabilizing coordinate distributions to be isotropic and identically distributed, rotation prevents the quantizer from exhibiting varying error characteristics across different dimensions. The codebook.rs module consumes these rotated vectors, benefiting from the consistent statistical properties that reduce quantization bias and improve the accuracy of approximate nearest neighbor search.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}