检查向量是否增加矩阵秩的最快方法
给定一个 n×m 矩阵 A，保证 n>m=rank(A)，并给定一个 n×1 列 v，检查 [A v] 是否严格具有秩的最快方法是什么比A还大？
对于我的应用程序，A 是稀疏的，n 约为 2^12，m 为 1:n-1 中的任意位置。 比较rank(full([A v]))在我的机器上大约需要一秒钟，并且我需要执行数万次，所以我很高兴发现一种更快的方法。
Given an n-by-m matrix A, with it being guaranteed that n>m=rank(A), and given a n-by-1 column v, what is the fastest way to check if [A v] has rank strictly bigger than A?
For my application, A is sparse, n is about 2^12, and m is anywhere in 1:n-1.
Comparing rank(full([A v])) takes about a second on my machine, and I need to do it tens of thousands of times, so I would be very happy to discover a quicker way.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
如果您有能力对零空间进行一次计算，则无需重复求解。只需调用一次 null 就足够了。给定一个新向量 V，如果 V 与零空间基的点积非零，则 V 将增加矩阵的秩。例如，假设我们有矩阵 M，它的秩当然是 2。
如果我们将新的列向量 [1;1;1;1] 附加到 M 上，它的秩会增加吗？
是的，因为它在 nullM 中的至少一个基向量上具有非零投影。
这个向量怎么样：
在这种情况下，两个数字本质上都是零，因此所讨论的向量不会增加 M 的秩。
关键是，一旦生成了零空间基，只需要简单的矩阵向量乘法。如果您的矩阵太大（并且矩阵几乎满秩），对 null 的调用将在此处失败，那么您将需要做更多的工作。不过，只要矩阵的列数不太多，n = 4096 就不会太大。
如果 null 太多，一种替代方法是调用 svds，以找到那些基本上为零的奇异向量。这些将形成我们需要的零空间基础。
There is no need to do repeated solves IF you can afford to do ONE computation of the null space. Just one call to null will suffice. Given a new vector V, if the dot product with V and the nullspace basis is non-zero, then V will increase the rank of the matrix. For example, suppose we have the matrix M, which of course has a rank of 2.
Will a new column vector [1;1;1;1] increase the rank if we appended it to M?
Yes, since it has a non-zero projection on at least one of the basis vectors in nullM.
How about this vector:
In this case, both numbers are essentially zero, so the vector in question would not have increased the rank of M.
The point is, only a simple matrix-vector multiplication is necessary once the null space basis has been generated. If your matrix is too large (and the matrix nearly of full rank) that a call to null will fail here, then you will need to do more work. However, n = 4096 is not excessively large as long as the matrix does not have too many columns.
One alternative if null is too much is a call to svds, to find those singular vectors that are essentially zero. These will form the nullspace basis that we need.
我会使用 sprank 来表示稀疏矩阵。检查一下，它可能比任何其他方法都快。
编辑：正如@IanHincks正确指出的那样，这不是排名。我将答案留在这里，以防将来其他人需要它。
I would use
sprankfor sparse matrixes. Check it out, it might be faster than any other method.Edit : As pointed out correctly by @IanHincks, it is not the rank. I am leaving the answer here, just in case someone else will need it in the future.
也许你可以尝试解决系统
A*x=v，如果它有一个解决方案意味着等级不会增加。Maybe you can try to solve the system
A*x=v, if it has a solution that means that the rank does not increase.