生成垂直于一组给定向量的随机向量

Question

我有一组成对垂直的向量。然后我想生成一个新的向量，它应该垂直于给定集合中的所有向量，并且应该随机选择。基本上，如果 d 是问题的维数，m 是给定向量的数量，那么垂直于这些向量的向量集跨越 (d-m) 维子空间。我想从这个子空间中随机抽取一个向量。

我可以使用 np.linalg.lstsq 来找到一个垂直于所有其他向量的向量，但结果不会是随机的：

import numpy as np

rng = np.random.default_rng(seed=0)

d = 8  # number of dimensions

vectors = [rng.normal(size=d)]
for _ in range(d-1):
    vectors.append(np.linalg.lstsq(
        np.stack(vectors, axis=0),
        np.zeros(len(vectors)),
        rcond=None,
    )[0])


import itertools as it

for i, j in it.combinations(range(d), r=2):
    assert abs(vectors[i] @ vectors[j]) < 1e-16

所以我认为我应该随机抽样 (d-m) 个组件，然后用 np.linalg.solve 确定其他组件。例如：

import numpy as np

rng = np.random.default_rng(seed=0)

d = 10  # number of dimensions

vectors = [rng.normal(size=d)]
for _ in range(d-1):
    random_indices = rng.choice(np.arange(d), size=d-len(vectors), replace=False)
    random_mask = np.zeros(d, dtype=bool)
    random_mask[random_indices] = True

    random_components = rng.normal(size=random_mask.sum())

    matrix = np.stack(vectors, axis=0)
    other_components = np.linalg.solve(
        matrix[:, ~random_mask],
        -(matrix[:, random_mask] @ random_components),
    )
    new = np.empty_like(vectors[-1])
    new[random_mask] = random_components
    new[~random_mask] = other_components

    for v in vectors:
        assert abs(v @ new) < 1e-12, f'dot product: {v @ new}'
    vectors.append(new)

但是，为了使上述工作正常，我必须根据维数放宽垂直条件 v @ new == 0。例如，对于 d = 10，我只能要求 v @ new < 1e-12，而对于 d = 20，阈值是 1e-10。对于最小二乘解，使用与 d 无关的相同阈值就足够了（事实上，所有点积都为零）。

此外，我不确定上述算法（即首先随机抽取待随机化组件的索引，然后确定其他组件）是否会从该子空间中产生真正随机的向量。我该如何验证？

Answer 1

您可以使用 Gram-Schmidt process

迭代地执行此操作

n = 100;
d = 20;
v = np.random.rand(n);
v = v / np.sqrt(np.sum(np.abs(v)**2));
V = [v]

for i in range(d):
    v = np.random.rand(n);
    # orthogonalize
    v = v - sum(vi * np.sum(vi.conj() * v) for vi in V);
    # normalize
    v = v / np.sqrt(np.sum(np.abs(v)**2))
    V.append(v);
A = np.array(V)
np.allclose(A @ A.T, np.eye(d+1)) # check the result

在这个例子中，我从一个空基开始。

如果您已经有了基础并且想要一个向量，您只需重复我在上一次迭代中所做的即可。

生成垂直于一组给定向量的随机向量

Generate random vector which is perpendicular to a set of given vectors

python

numpy

linear-algebra