Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: full QR decomposition

• To: mathgroup at smc.vnet.net
• Subject: [mg51687] Re: [mg51645] full QR decomposition
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Fri, 29 Oct 2004 03:39:13 -0400 (EDT)
• References: <200410280343.XAA09703@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

Jan Schmedes wrote:
> Dear group,
> 
> i have the following problem. For a given a NxM (e.g. 3000x600) matrix A i
> get a matrix Q (MxN) and R (MxM) after the QRDecomposition. But i would
> like to get the full decomposition with a matrix QF (NxN) and RF (NxM) where RF
> contains only zero lines below the line with index M. I'm especially
> interrested in the last N-M lines in QF which create the zero lines in RF.
> At the moment i use QRDecomposition and append then N-M random lines to
> the matrix Q. With this new matrix i go into the routine GramSchmidt and extract the last N-M
> lines from the result. But this is very slow and i'm not sure if it will
> always work? Are there any suggestions or hints?
> 
> best regards and thank you
> 
> jan schmedes

I'll discuss this with respect to real valued matrices so as to avoid 
requiring Conjugate in various places. The important defining relation 
between a given real matrix mat and the decomposition into q and r is 
that Transpose[q].r==mat. From this and your requirement for the full 
decomposition it is not hard to see that extra rows in q are simply any 
orthonormal set for the null space of q. To make the null space 
orthogonal we simply use another invocation of QRDecomposition and 
extract the "Q" part.

This may be obtained as in the example below.

SeedRandom[1111];
randomMatrix[n_,m_] := Table[Random[], {n}, {m}]
rows = 7;
cols = 3;
mat = randomMatrix[rows, cols];
{q,r} = QRDecomposition[mat];

First we check the QR decomposition.

In[64]:= Transpose[q] . r == mat
Out[64]= True

In[65]:= Chop[q . Transpose[q]] == IdentityMatrix[Length[q]]
Out[65]= True

Now we form the full decomposition.

qextra = NullSpace[q];
{q2,r2} = QRDecomposition[Transpose[qextra]];
qf = Join[q,q2];
rf = Join[r, Table[0, {rows-Length[r]}, {cols}]];

Now check the full decomposition:

In[66]:= Transpose[qf] . rf == mat
Out[66]= True

In[67]:= Chop[qf . Transpose[qf]] == IdentityMatrix[Length[qf]]
Out[67]= True

In[68]:= Dimensions[qf] == {rows,rows}
Out[68]= True


Daniel Lichtblau
Wolfram Research

• References:
  • full QR decomposition
    • From: Jan Schmedes <schmedes@rz.uni-potsdam.de>