Нахождение наименьшего угла между векторами в логарифмическом времени

Question

У меня n=10000 10-мерные векторы. Для каждого вектора v1 я хочу знать вектор v2, который минимизирует угол между v1 и v2.

Есть ли способ решить эту проблему быстрее, чем O(n^2)?

Answer 1

То, что у вас есть, - это, по сути, проблема ближайших точек на сфере (поскольку угол между векторами равен примерно расстоянию между точками на сфере, на которых лежат их единичные векторы), так что вы, вероятно, могли бы сделать что-то вроде двоичного (возможно, троичного было бы легче избежать слишком большого количества проблем с границами) декомпозиции с разделением пространства.

Но это было бы неприятно для кода, и, вероятно, не намного быстрее, чем простой метод, всего за 10 000 точек (в частности, вы начинаете с деления точек между 3 ^ 10 = 59049 ящиками, хотя большинство из них будет быть пустым). Сто миллионов продуктов из десяти элементов должны быть меньше одной секунды.

Answer 2

Вы можете нормализовать все векторы за время O (n) и найти их параметризацию в результирующей 9-мерной гиперсфере. Затем вы можете использовать структуру пространственного поиска в n-1-мерном пространстве, например, дерево Kd, чтобы ускорить запрос ближайшего соседа. Для этого существуют хорошо известные методы ( ANN ).

Answer 3

Ничего себе.Десятимерные векторы?Что вы делаете с ними?

Полагаю, я бы начал с уменьшения каждого вектора до единичной длины, т. Е. До точек на гиперсфере, а затем использовал бы некоторый алгоритм "поиска ближайших соседей" (NNS), такой какkD-дерево (k-мерное двоичное дерево), R-дерево, Best Bin First и т. д.

Вероятно, невозможно решить эту проблему быстрее, чем O (n log n), потому что, если бы вы могли решить эту проблему быстреекроме того, вы могли бы решить более простую «задачу с ближайшей парой точек» быстрее, чем текущая нижняя граница O (n log n).

Как отметил Том Вомак, грубая сила O (n ^2) алгоритм потребует меньше фактического времени настенных часов, чем эти более сложные алгоритмы для «небольших» объемов данных, и, похоже, «n = 10000» относительно мало для 10 измерений.

Answer 4

Как насчет вычисления углов для каждого вектора (O (n)), затем сортировки массива на основе углов (O (nlogn)), а затем просто пройтись по массиву (O (n)), ближайший вектор либо i + 1 или i-1.

Edit: Как отмечено в комментариях, это работает только в 2 измерениях.