как быстро вычислить расстояние между векторами высокой размерности

Question

Предположим, есть три группы векторов высокой размерности:

{a_1, a_2, ..., a_N},

{b_1, b_2, ..., b_N},

{c_1, c_2, ..., c_N}.

каждый мой вектор может быть представлен как: x = a_i + b_j + c_k, где 1 <= i, j, k <= N. тогда вектор кодируется как (i, j, k), который затем может быть декодирован как x = a_i + b_j + c_k. </p>

мой вопрос: если есть два вектора: x = (i_1, j_1, k_1), y = (i_2, j_2, k_2), существует ли метод для вычисления евклидова расстояния этих двух векторов без декодирования x у.

Answer 1

Квадратный корень из суммы квадратов разностей между компонентами. Другого способа сделать это нет.

Вы должны масштабировать значения для защиты от проблем переполнения / недостаточного заполнения. Найдите максимальную разницу и разделите на нее все компоненты перед возведением в квадрат, суммированием и получением квадратного корня.

Answer 2

Предположим, у вас есть только две группы.Вы пытаетесь вычислить скалярное произведение

(a_i1 + b_j1, a_i2 + b_j2)
= (a_i1,a_i2) + (b_j1,b_j2) + (a_i1,b_j2) + (a_i2,b_j1) # <- elementary scalar products

Итак, если вы знаете необходимые элементарные скалярные произведения между элементами ваших векторов a_i, b_j, c_k, то вам не нужно «декодировать» xy и может вычислить скалярное произведение напрямую.

Обратите внимание, что это именно то, что происходит, когда вы вычисляете обычное евклидово расстояние на неортогональной основе.

Answer 3

Если вы довольны приблизительным результатом, вы можете спроецировать свои базисные векторы высокой размерности, используя случайную проекцию , в небольшое размерное пространство. Johnson-Lindenstrauss В лемме говорится, что вы можете уменьшить размер до O (log N), чтобы расстояния оставались примерно одинаковыми с высокой вероятностью.