确定矩阵是否稀疏？
Joh*_*ohn 2 algorithm matlab matrix
我有一个矩阵.我想知道它是否稀疏.matlab中是否有任何函数来评估该属性？我试图使用issparse函数,但它总是返回0(不稀疏).例如,我的矩阵(27 by 27)是
A=
[ 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0
0 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0
0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0
0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0
250 243 247 245 244 244 244 122 61 144 72 36 18 9 4 2 1 1 0 0 0 0 0 0 0 0 0
151 197 236 118 181 212 106 53 26 13 136 68 34 17 8 4 2 0 1 0 0 0 0 0 0 0 0
24 12 6 3 143 201 234 117 180 90 45 152 76 38 19 9 4 0 0 1 0 0 0 0 0 0 0
18 9 138 69 172 86 165 220 224 112 56 28 128 64 32 16 8 0 0 0 1 0 0 0 0 0 0
27 131 207 103 189 94 47 153 194 239 119 59 29 128 64 32 16 0 0 0 0 1 0 0 0 0 0
44 22 133 204 232 116 58 147 199 237 248 124 62 31 129 64 32 0 0 0 0 0 1 0 0 0 0
238 119 181 90 45 152 76 38 19 135 205 232 116 58 29 128 64 0 0 0 0 0 0 1 0 0 0
48 24 12 6 3 143 201 100 50 25 130 207 233 116 58 29 128 0 0 0 0 0 0 0 1 0 0
168 84 42 21 132 66 33 158 79 39 19 135 205 232 116 58 29 0 0 0 0 0 0 0 0 1 0
235 117 58 29 128 64 32 16 8 4 2 1 142 201 234 117 58 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
0 1 1 0 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0
0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0]
这是上面矩阵的图
这个看似简单的问题很难回答.实际上没有已知的标准来确定矩阵是稀疏的还是满的.
然而,我所知道的最常见的衡量标准是衡量矩阵的稀疏性.这只是元素总数中零总数的一部分.如果这超过某个合理的阈值,那么你可以说矩阵是稀疏的.
如果给你矩阵A,可能是这样的:
sparsity = (numel(A) - nnz(A)) / numel(A);
numel确定矩阵中元素的总数,A并nnz确定非零元素的总数.因此,numel(A) - nnz(A)应该给你零元素的总数.
所以,按照门槛的想法,这就是我所说的:
is_sparse = sparsity > tol;
tol将是一小部分[0,1],所以类似的东西0.75可以工作.这意味着如果你的矩阵的75%由零组成,那么这可能是一个稀疏矩阵.尽管如此,这都是启发式的.选择您认为最有意义的阈值.
- @ user8264稀疏是如何"稀疏"取决于矩阵.来自WolframMathWorld:"矩阵为了被认为是"稀疏"所需的零数取决于矩阵的结构和对其执行的期望操作.例如,随机生成的稀疏n×n矩阵,其中cn条目分散在威尔金森(直接方法)意义上,整个矩阵中随机分布并不稀疏,因为它需要O(n ^ 3)时间因子(具有高概率和足够大的c; Gilbert等1992).http://mathworld.wolfram.com/SparseMatrix.html (2认同)
- @ user8264考虑到Matlab使用额外的`nnz` +列数内存来表示稀疏矩阵的事实,所以如果`numel(A) - nnz(A)<nnz(A)+ size(A,2)`那么它在Matlab中将它作为"稀疏"存储更具内存效率. (2认同)