生成一个向量，该向量在任何维度上都与一组其他向量正交

Question

假设我有一组向量 $ a_1, ..., a_d $ 彼此正交。现在，我想找到另一个与所有其他向量正交的向量 $ a_{d+1} $。

有没有高效的算法来实现这个？只能想到最后加一个随机向量，然后应用gram-schmidt。
是否有 python 库已经实现了这一点？

Answer 1

Related. Can't speak to optimality, but here is a working solution. The good thing is that numpy.linalg does all of the heavy lifting, so this may be speedier and more robust than doing Gram-Schmidt by hand. Besides, this表明复杂度不比Gram-Schmidt差。

想法：

将您的输入正交向量视为矩阵的列 O。
向 O 添加另一个随机列。通常 O 将保持满秩矩阵。
选择 b = [0, 0, ..., 0, 1] 和 len(b) = d + 1。
求解一个最小二乘问题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")

生成一个向量，该向量在任何维度上都与一组其他向量正交

Generate a vector that is orthogonal to a set of other vectors in any dimension

python

matrix

orthogonal