Создать вектор, который ортогонален множеству других векторов в любом измерении

Question

Предположим, у меня есть набор векторов $ a_1, ..., a_d $, которые ортонормированы друг к другу.Теперь я хочу найти другой вектор $ a_ {d + 1} $, который ортогонален всем остальным векторам.

1. Существует ли эффективный алгоритм для достижения этой цели?Я могу думать только о добавлении случайного вектора в конец, а затем о применении грама-Шмидта.

2. Есть ли библиотека Python, которая уже достигает этого?

Answer 1

Относящиеся .Не могу говорить об оптимальности, но вот рабочее решение.Хорошо, что numpy.linalg выполняет всю тяжелую работу, так что это может быть быстрее и надежнее, чем ручная работа по Грам-Шмидту.Кроме того, это предполагает, что сложность не хуже, чем у Грам-Шмидта.

Идея:

1. Обрабатывать ваши входные ортогональные векторы как столбцы матрицы O.
2. Добавить еще один случайный столбец к O.Обычно O останется матрицей полного ранга.
3. Выберите b = [0, 0, ..., 0, 1] с помощью len(b) = d + 1.
4. Решите задачу наименьших квадратов x O = b.Тогда гарантируется, что x будет ненулевым и ортогональным ко всем исходным столбцам O.

---

import numpy as np
from numpy.linalg import lstsq
from scipy.linalg import orth

# random matrix
M = np.random.rand(10, 5)

# get 5 orthogonal vectors in 10 dimensions in a matrix form
O = orth(M)


def find_orth(O):
    rand_vec = np.random.rand(O.shape[0], 1)
    A = np.hstack((O, rand_vec))
    b = np.zeros(O.shape[1] + 1)
    b[-1] = 1
    return lstsq(A.T, b)[0]


res = find_orth(O)

if all(np.abs(np.dot(res, col)) < 10e-9 for col in O.T):
    print("Success")
else:
    print("Failure")