Thread Subject: find a full rank submatrix from a rank-deficient matrix

Dear All,

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

"Hua Wang" <ehwang@163.com> wrote in message <j28thq$nqh$1@newscl01ah.mathworks.com>...
> 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

"Matt J" wrote in message <j28tt6$opm$1@newscl01ah.mathworks.com>...
> "Hua Wang" <ehwang@163.com> wrote in message <j28thq$nqh$1@newscl01ah.mathworks.com>...
> > 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

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" <ehwang@163.com> wrote in message <j29dr5$9ii$1@newscl01ah.mathworks.com>...
> "Matt J" wrote in message <j28tt6$opm$1@newscl01ah.mathworks.com>...
> > "Hua Wang" <ehwang@163.com> wrote in message <j28thq$nqh$1@newscl01ah.mathworks.com>...
> > > 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
>
> 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
>

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

On Aug 14, 12:36 pm, "Hua Wang" <ehw...@163.com> wrote:
> Dear All,
>
> 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

Not sure how you are thinking because B is full rank

>> min(size(B))==rank(B)

ans =

     1

Hope this helps somehow.

Greg

Dear Greg,

> > 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


> 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" <ehwang@163.com> wrote in message

> 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

> 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

"Hua Wang" <ehwang@163.com> wrote in message <j2an33$4oo$1@newscl01ah.mathworks.com>...
>
> [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

> 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.

"Hua Wang" <ehwang@163.com> wrote in message <j2ardq$gdg$1@newscl01ah.mathworks.com>...
>
> > 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.

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