生成一个向量,该向量在任何维度上都与一组其他向量正交
Generate a vector that is orthogonal to a set of other vectors in any dimension
假设我有一组向量 $ a_1, ..., a_d $ 彼此正交。现在,我想找到另一个与所有其他向量正交的向量 $ a_{d+1} $。
有没有高效的算法来实现这个?只能想到最后加一个随机向量,然后应用gram-schmidt。
是否有 python 库已经实现了这一点?
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")
假设我有一组向量 $ a_1, ..., a_d $ 彼此正交。现在,我想找到另一个与所有其他向量正交的向量 $ a_{d+1} $。
有没有高效的算法来实现这个?只能想到最后加一个随机向量,然后应用gram-schmidt。
是否有 python 库已经实现了这一点?
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")