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

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.

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

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, то вам не нужно «расшифровывает» х и у и может вычислить скалярное произведение напрямую.

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

Answer 3

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