How to find out a smallest sub-matrix B from a sparse matrix A which has the equal rank and # of non-zero columns?

6 ビュー (過去 30 日間)
Dear All,
I have a very sparse matrix A. I need to find out a number of rows (smallest #) of A which satisfies the following conditions:
1). Let us suppose the number of rows form a sub-matrix B. In another word, for a given sparse tall matrix A, we need to find out sub-matrix B;
2). Matrix B must contain the first row of A;
3). The rank of B must be equal to the number of non-zero columns (a non-zero column is defined as a column containing at least one non-zero element in the column) of B.
4). The rank of B must be smaller than the rank of matrix A.
For example,
A = [
1 -1 0 0 0
0 2 0 0 0
0 0 2 -1 -1
1 0 1 0 0
];
The anwser is obvious. The matrix B is formed by the first 2 rows of A:
B = [
1 -1 0 0 0
0 2 0 0 0
];
The condition is satisfied: rank(B) = # of non-zero columns (the first 2 columns are non-zero columns) in B.
How about the following example?
A = [
1 -1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0
0 0 -1 -1 0 0 0 -1 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
-1 0 0 0 4 -1 -1 -1 0
0 0 0 0 -1 1 0 0 0
0 0 0 0 -1 0 1 0 0
0 0 0 0 -1 0 0 2 0
0 0 0 0 0 0 0 0 0
3 -1 0 0 -1 0 0 0 -1
-1 1 0 0 0 0 0 0 0
-1 0 0 0 0 0 0 0 1
];
Please help to find out a sub-matrix B for a given sparse matrix A.
Thanks a lot.
Benson
  2 件のコメント
Bob Thompson
Bob Thompson 2021 年 1 月 20 日
編集済み: Bob Thompson 2021 年 1 月 20 日
I don't understand what exactly you're trying to capture for B. This is what my understanding is, please correct where I'm wrong.
1) You have a matrix, A, which contains some numbers sprinkled among a bunch of zeros.
2) You want to look at the first row of A, and count the number of non-zero values in it, and the rank. What is rank?
3) You want to examine all rows of A to find which ones contain the same number of non-zero values, and same rank, as the first row.
4) Rows which pass step 3 should be placed in a separate matrix, B.
This kind of work certainly seems possible in MATLAB, I just want to make sure I understand what you're actually trying to do before I go fishing for answers.
Benson Gou
Benson Gou 2021 年 1 月 20 日
Hi, Bob,
Thanks for your reply. I modified the description and place feel free to point it out if you still do not understand my question.
Thanks a lot.
Benson

サインインしてコメントする。

採用された回答

Bruno Luong
Bruno Luong 2021 年 1 月 20 日
編集済み: Bruno Luong 2021 年 1 月 20 日
Done, B=A (so all rows of A) meets your requirement
>> A = [
1 -1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 -1
0 0 0 0 0 0 0 0 0
0 0 -1 -1 0 0 0 -1 0
0 0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0
-1 0 0 0 4 -1 -1 -1 0
0 0 0 0 -1 1 0 0 0
0 0 0 0 -1 0 1 0 0
0 0 0 0 -1 0 0 2 0
0 0 0 0 0 0 0 0 0
3 -1 0 0 -1 0 0 0 -1
-1 1 0 0 0 0 0 0 0
-1 0 0 0 0 0 0 0 1
];
>> B=A;
>> sum(any(B,1))
ans =
9
>> rank(B)
ans =
9
  9 件のコメント
Benson Gou
Benson Gou 2021 年 1 月 21 日
Hi, Bruno,
Thanks a lot for your great help. Your code wroks well. But it took more than 2400 iterations to reach the solution.
I have an idea to speed up the calculation. The idea is:
In order to find B, any row, which has zero elements in columns 1 & 2 (because the first row has non-zero elements in columns 1 & 2), will contribute more non-zero coulmns than (at most equal) the rank increase of B. For example, rows 2, 3, 4, 5, 6, 11 and 13 in this case. I compare those rows with the first row below:
Row 1: 1 -1 0 0 0 0 0 0 0 (Must included)
Row 3: 0 0 0 0 0 0 0 0 0
Row 4: 0 0 -1 -1 0 0 0 -1 0
Row 5: 0 0 1 0 0 0 0 0 0
Row 6: 0 0 0 1 0 0 0 0 0
Row 11: 0 0 0 0 0 0 0 0 0
Row 13: -1 1 0 0 0 0 0 0 0
We can define above rows (Rows 2, 3, 4, 5, 6, 11 and 13) as Irrelative Rows.
So my idea is: 1) in each iteration, we can avoid the Irrelative Rows; 2) in each iteration, we can only conider increasing the number of non-zero columns of B by 1; 3) As the size of B increses, the number of irrelative rows will reduce.
I am not a good Matlab coder and my code normally is more complex than necessary.
Thanks a lot again for your great help.
Benson
Bruno Luong
Bruno Luong 2021 年 1 月 22 日
編集済み: Bruno Luong 2021 年 1 月 22 日
Nothing in your question indicates that there is such sequencial suites of rows that the number of non-zeros columns increase by at most 1 between two adjacent selected rows.
You can make a modification in A by making an arbitrary combination the rows=[1 7 8 9 10 12 14] in A, and it will return the same row selection, and without such suites (they all have 7 non-zeros columns).
In this case it you apply your method of "speeding" up, it will fail to detect B.

サインインしてコメントする。

その他の回答 (1 件)

Walter Roberson
Walter Roberson 2021 年 1 月 21 日
In general there is no solution.
Every dense matrix is also a spare matrix.
An NxN full-rank dense matrix might happen to have no zeros.
B is a submatrix of A, so if A has no zeros at all, it is impossible for the number of non-zero columns of B to be smaller than the number of columns of A.
B has N columns because A has N columns.
You require rank of B to be the number of non-zero columns of B, but the number of non-zero columns of B is, in this case, the number of columns of B.
A is square and (by selection) has full rank, N. And as discussed above, B would have to be rank N.
But rank(B) = N and rank(A) = N, so therefore rank(B) < rank(A) must be false.
Therefore there are matrices for which the conditions cannot hold.
  3 件のコメント
Walter Roberson
Walter Roberson 2021 年 1 月 22 日
The example is not normative. The rules you gave for solution do not require that M > N or that it has any minimum sparsity. The question asks "Given a matrix A, find B that follows these rules", and I demonstrated that you cannot always do that. You could revise the rules, of course.
Benson Gou
Benson Gou 2021 年 1 月 22 日
Hi, Walter,
Thanks for your reply. I added the condition of matrix A according to your concerns. Now I think it should be OK.
Thanks a lot again.
Benson

サインインしてコメントする。

カテゴリ

Help Center および File ExchangeJust for fun についてさらに検索

タグ

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by