python - 如何在 python 中生成稀疏正交矩阵？

Question

如何生成随机稀疏正交矩阵？

我知道 scipy 库中有一个稀疏矩阵，但它们通常是非正交的。可以利用 QR 分解，但它不一定能保持稀疏性。

Answer 1

作为初步想法，您可以将矩阵划分为对角线 block ，用 QR 填充这些 block ，然后排列行/列。生成的矩阵将保持正交。或者，您可以为 Q 定义一些稀疏模式，并尝试最小化 f(Q, xi) subject to QQ^T=I where f 是一些(最好)凸函数，它通过随机变量 xi 添加熵。不能说这两种方法的功效，因为我还没有真正尝试过它们。

编辑:关于第二种方法的更多信息。 f 实际上可以是任何函数。一种选择可能是非零元素与随机高斯向量(或任何其他随机变量)的相似性:f = ||vec(Q) - x||_2^2, x ~ N(0, sigma * I)。您可以使用任何通用的约束优化器来处理这个问题。当然，问题在于并非每个模式 S 都保证具有(满秩)正交填充。如果您有足够的内存力，L1 正则化(或平滑近似)可以促进密集矩阵变量的稀疏性:g(Q) = f(Q) + P(Q) 其中 P 是任何稀疏性诱导惩罚函数。查看 Wen & Yen (2010)“一种可行的正交约束优化方法”，了解专门为优化(密集)正交矩阵上的一般(可微)函数而设计的算法，以及 Liu, Wu, So (2015)“二次优化与Orthogonality Constraints”，用于对二次函数的几种线/弧搜索算法进行更多的理论评估。如果内存有问题，您可以使用稀疏基础追踪分别生成每一行/列，根据问题的性质，有很多算法。算法参见 Qu、Sun 和 Wright (2015)“Finding a sparse vector in a subspace: linear sparsity using alternate directions”和 Bian et al (2015)“Sparse null space basis pursuit and analysis dictionary learning for high-dimensional data analysis”细节，但在这两种情况下，您都必须合并/替换约束以促进与所有先前向量的正交性。

还值得注意的是，有稀疏 QR 算法将 Q 作为稀疏/结构化矩阵的乘积返回。如果您只关心存储空间，这可能是创建大型高效正交运算符的最简单方法。