具有行和列长度约束的随机矩阵

机器算法验证 随机生成 正常化 马尔科夫过程 随机矩阵
2022-01-31 15:23:08

我需要生成随机非方阵R行和C列,元素以零均值随机分布,并受到约束,使得长度 (L2规范)的每一行是1每列的长度是RC. 等效地,平方值之和为1对于每一行和RC对于每一列。

到目前为止,我找到了一种方法来实现这一点:简单地随机初始化矩阵元素(例如,从均值为零和任意方差的均匀、正态或拉普拉斯分布),然后交替地将行和列标准化为长度1,以行规范化结束。这似乎很快收敛到预期的结果(例如R=40C=80, 列长的方差通常为 ~ 0.000012迭代),但我不确定我是否可以依赖这种快速收敛速度(对于各种矩阵维度和初始元素分布)。

我的问题是:有没有办法达到预期的结果(行长1, 列长RC) 直接在行/列标准化之间不进行迭代?例如,用于规范化随机向量的算法(随机初始化元素,测量平方和,然后通过公共标量缩放每个元素)。如果没有,是否有收敛速度的简单表征(例如,迭代次数直到错误<ϵ) 上面描述的迭代方法?

1个回答

正如@cardinal 在评论中所说:

实际上,经过一番思考,我认为您的算法正是Sinkhorn-Knopp 算法,只是做了很小的修改。X成为你的原始矩阵,让Y是一个相同大小的矩阵,使得Yij=Xij2. 然后,您的算法相当于将 Sinkhorn-Knopp 应用于Y,在最后一步,您可以通过以下方式恢复所需的形式X^ij=sgn(Xij)Yij. Sinkhorn-Knopp 保证收敛,除非在非常病态的情况下。阅读它应该非常有帮助。

...似乎我在原始问题中建议的迭代算法与 Sinkhorn-Knopp 算法非常相似。有趣的是,它似乎也与迭代比例拟合(IPF) 非常相似,正如 IPF 维基百科页面上所述,它与牛顿方法和期望最大化(都具有相同的限制)有关。

这些迭代方法通常应用于缺乏封闭形式解决方案的问题,因此我将暂时假设该问题的答案是否定的:没有行/列迭代就无法获得所需的解决方案。