Johnson-Lindenstrauss Dimension Bound

Problem

Return a Johnson-Lindenstrauss embedding dimension that preserves all pairwise distances of num_points points within a factor of 1 +/- epsilon.

The commonly used sufficient bound is ceil(8 * ln(n) / epsilon ** 2) random projection dimensions. Return 0 when there are fewer than two points or epsilon lies outside (0, 1).

Hint

The dimension depends logarithmically on the number of points but quadratically on the distortion.

Test cases

case 1

in: [100,0.1]

expected: 3685

case 2

in: [1000,0.2]

expected: 1382

case 3

in: [100,0.5]

expected: 148

case 4

in: [1,0.1]

expected: 0

case 5

in: [100,0]

expected: 0

Starter codePython

import math


def jl_dimension(num_points, epsilon):
    # Your code here
    pass

5 test cases · run your code against them in the editor