find a full rank submatrix from a rank-deficient matrix
Hua Wang
I am looking for a method to get a susmatrix (a few rows) from a rank deficient matrix. For example,
B=[ 1 0 0 0 0;
1 1 0 0 0;
0 0 1 0 0;
0 0 1 1 1]
The first three rows are somewhat full rank (if I delete the last two columns), but the last row will make the matrix rank deficient. I'd like to get a subset of matrix A
A=[1 0 0 0 0;
1 1 0 0 0
0 0 1 0 0];
I tried rref function, but it's so slow. The original whole functiont takes about 3 minutes, but rref will take over 30 minutes for my data. The codes are as followed. Could you please shed light on it? It's a bit urgent. Thank you so much!
Hua
rmrow=0;
while ~isempty(rmrow)
[dump,licols]=rref(B);
rec=[1:nepoch-1];
rec(licols)=[];
[rmrow,rmcol]=find(nnz(B(:,rec))>0);
B(rmrow,:)=[];
ifgv(rmrow)=[];
end
Matt J
> Dear All,
>
> I am looking for a method to get a susmatrix (a few rows) from a rank deficient matrix. For example,
See this thread:
http://www.mathworks.com/matlabcentral/newsreader/view_thread/286877#828575
Hua Wang
Thanks Matt!
Following my above example, if I have a system of equations like y=B*x. I should get a unique solution for x1-x3, but infinite solutions for x4-x5.
I found that there is a way to solve the above equations using QR, like explained in the manual
[C,R,E] = qr(A,B,0)
X(E,:) = R\C
In this case, which are the corresponding solutions for x1-3 (the unique solutions) and x4-x5 (the minimum norm solutions) respectively? This my key questions. I have to separate them in my codes, and this is the reason I used rref there.
Looking forward to your answer! Many thanks!
Hua
Hua Wang
Hi Matt,
My question was solved by the following codes. I iteratively delete the rows (B and d) which have non-zeros elements beside the independent columns. It's quite fast to use these code. But alternative better method is very welcome.
rmrow=0;
while ~isempty(rmrow)
[q,r,e]=qr(B,0);
licols=e(rank(B)+1:nepoch-1);
[rmrow,rmcol]=find(B(:,licols)~=0);
B(rmrow,:)=[];
d(rmrow)=[];
end
Greg Heath
Not sure how you are thinking because B is full rank
>> min(size(B))==rank(B)
ans =
1
Hope this helps somehow.
Greg
Hua Wang
> > B=[ 1 0 0 0 0;
> > 1 1 0 0 0;
> > 0 0 1 0 0;
> > 0 0 1 1 1]
You are right, min(size(B))==rank(B). But we can only sort out unique solutions for the first unknown parameters (x1-x3). For the last two (x4-x5), we have infinite solutions. From the last row of B, it can be simplified as x4+x5=y. My purpose is to find out all rows which are like the last one in B.
Thanks!
Cheers
Hua
Bruno Luong
> You are right, min(size(B))==rank(B). But we can only sort out unique solutions for the first unknown parameters (x1-x3). For the last two (x4-x5), we have infinite solutions. From the last row of B, it can be simplified as x4+x5=y. My purpose is to find out all rows which are like the last one in B.
Who decides only x1-x3 are relevant? You? If you are only interested in x1-x3, why bother to consider 4th-5th column at the first place.
The rank of B is 4 (that's the fact). Therefore we can chose 4 independent columns from B. We can also chose 4 independent rows.
Why you decide to keep only x1-x3??? Your post is confusing.
Bruno
Hua Wang
> Who decides only x1-x3 are relevant? You? If you are only interested in x1-x3, why bother to consider 4th-5th column at the first place.
>
> The rank of B is 4 (that's the fact). Therefore we can chose 4 independent columns from B. We can also chose 4 independent rows.
>
> Why you decide to keep only x1-x3??? Your post is confusing.
>
Sorry for my confusing post. I'm going to solve a system of equation like
B*x=y.
It's hard to decide which rows and observations should be put in B and y ahead of time. So I make the full B and y first, and then remove the rows of B and y which can not give unique solutions (although it is not rank deficient).
All in a word, I'm only interested in the unique solutions of x. The other part of x can be solved by pinv, but pinv is somewhat like interpolation and will make my data noiser for the next processing.
Thanks!
Hua
Bruno Luong
>
> [snip] ... then remove the rows of B and y which can not give unique solutions (although it is not rank deficient).
"Not unique solution although it is not rank deficient"? You must kidding us.
Show us an example of two different combinations of 4-independent (column) vectors that give the out same resultant vector.
Stop writing non-sense.
Bruno
Hua Wang
> Show us an example of two different combinations of 4-independent (column) vectors that give the out same resultant vector.
An example is
B=[ 1 0 0; 0 1 1];
y=[1,3];
For B*x=y, we can find it out that x1=1; x2+x3=3. Here x1 is the unique solution I mentioned, and x2/x3 have infinite solutions. I want to remove the rows which can give infinite solutions like x2/x3.
Bruno Luong
Sorry, don't play the game with us: now you change your data. The rank of new B is 2. So I can pick out only 2 independent columns. In the original B given earlier, the rank is 4 and you insist to pick out *3* out of the blue without explaining why *3*.
Let's make it clear:
Given B a matrix.
If rank B == k, then we can select a integer set *cols* of length k such that
A := B(:,cols),
A is a full rank matrix.
In other word the (least-squares) system A*x = y has always unique solution x.
Bruno