MathGroup Archive: March 2009 [00806]

[Date Index] [Thread Index] [Author Index]
Re: Orthogonazlie with Method->"Householder"
To: mathgroup at smc.vnet.net
Subject: [mg97772] Re: [mg97744] Orthogonazlie with Method->"Householder"
From: Daniel Lichtblau <danl at wolfram.com>
Date: Sat, 21 Mar 2009 05:17:25 -0500 (EST)
References: <200903200740.CAA17270@smc.vnet.net>
Maris Ozols wrote:
> I have a large numeric matrix M (see below), whose rank is 6. Clearly,
> the rank of Orthogonalize[M] must be the same (in particular, it
> should not increase). However, if I execute the following code on my
> matrix M:
> 
> MatrixRank@M
> MatrixRank@Orthogonalize[M]
> MatrixRank@Orthogonalize[M,Method->"Householder"]
> 
> I get 6, 6, and 12. So it appears to me that Householder's method has
> doubled the rank of M. I am using Mathematica 7.0 in Linux.
> 
> Is this a bug or a feature?
> 
> ~Maris Ozols~
> 
> Here is my matrix:

[I recopy the matrix below, since my email reader showed something that 
was messed up a bit. --dl]

It's not a bug. Given a matrix of approximate numbers, the rank is only 
defined up to some fuzziness that
(1) is to some extent arbitrary, and
(2) can depend on details of the computation and even implementation.

Mathematica is, I believe, counting the number of nonzero singular 
values for your matrix. On my platform (Linux) I obtain a matrix rank of 
5. For the orthogonalized version it is claimed to be 7. let's look at 
the basis for the first rank being 5.

In[2]:= InputForm[SingularValueList[mat]]
Out[2]//InputForm=
{7.053736007427739*^14, 44.4483160745624, 40.569302085579835,
25.471811796860234, 17.698020291765765}

This claims 5 singular values. But notice the first is almost 10^14 
times larger than the last. Since we have machine precision numbers, 
default tolerance behavior for SingularValuesList is going to discard 
any value that is smaller than (I believe) 100 times $MachineEpsilon 
times that largest. Let's see what the rest really are computed to be.

In[3]:= InputForm[SingularValueList[mat, Tolerance->0]]
Out[3]//InputForm=
{7.053736007427739*^14, 44.4483160745624, 40.569302085579835,
25.471811796860234, 17.698020291765765, 8.9043567804784, 8.893504452913108,
1.4628508027298205*^-12, 3.317011189474306*^-14, 4.513774554889041*^-15,
2.681411089549567*^-15, 1.2967499757995987*^-15, 1.0766832716866751*^-15,
1.0407511117597248*^-15, 2.6381881368443317*^-16, 1.509654864338757*^-16,
1.4557817277105998*^-16, 4.317417716067431*^-31, 3.411215393443724*^-31,
1.1945818043770994*^-31, 0.}

It is plausible that we should treat the next two as nonzero, and 
discard the rest, thus giving a rank of 7. A defensible alternative 
would be to discard all but the first, and claim the rank is 1. As I 
mentioned, there is some arbitrariness to how we decide to accept 
singular values as nonzero.

If you want matrixRank to look harder for nonzero singular values, you 
can give it an explicit Tolerance setting.

In[4]:= MatrixRank[mat, Tolerance->10^(-20)]
Out[4]= 7

Daniel Lichtblau
Wolfram Research

--------------

mat = {{-1.367128300941737, 0, 0, 0, -5.917767019974907, 0, 0, 0,
   1.2566212950683242, 0, 0, 0, 0.7325966416414449, 0, 0, 0,
   -5.917767019974907, 0, 0, 0, 1.1371276109150097, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 1.2566212950683242, 0, 0, 0, 0, 0, 0, 0, -0.3805278711063651, 
0, 0,
   0, 0, 0, 0, 0, 0.7325966416414449, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   1.034486709226178, 0, 0, 0}, {-1.367128300941737, -5.917767019974907,
   1.2566212950683242, 0.7325966416414449, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   -5.917767019974907, 1.1371276109150097, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 1.2566212950683242, 0, -0.3805278711063651, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0.7325966416414449, 0, 0, 1.0344867092261778, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0}, {-1.367128300941737, 0, 0, 0, 
-5.917767019974907, 0,
   0, 0, 1.2566212950683242, 0, 0, 0, 0.7325966416414449, 0, 0, 0,
   -5.917767019974907, 0, 0, 0, 1.1371276109150097, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 1.2566212950683242, 0, 0, 0, 0, 0, 0, 0, -0.3805278711063651, 
0, 0,
   0, 0, 0, 0, 0, 0.7325966416414449, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   1.034486709226178, 0, 0, 0}, {-1.367128300941737, -5.917767019974907,
   1.2566212950683242, 0.7325966416414449, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   -5.917767019974907, 1.1371276109150097, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 1.2566212950683242, 0, -0.3805278711063651, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0.7325966416414449, 0, 0, 1.0344867092261778, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0}, {-1.367128300941737, -5.917767019974907,
   1.2566212950683242, 0.7325966416414449, -5.917767019974907,
   1.1371276109150097, 0, 0, 1.2566212950683242, 0, 0., 0, 
0.7325966416414449,
   0, 0, 1.034486709226178, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0}, {-1.367128300941737, -5.917767019974907,
   1.2566212950683242, 0.7325966416414449, -5.917767019974907,
   1.1371276109150097, 0, 0, 1.2566212950683242, 0, 0., 0, 
0.7325966416414449,
   0, 0, 1.034486709226178, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   -0.557546880846985, -2.599916056557537, 0, 0, 0, 0, 
0.557546880846985, 0,
   0, 0.7873020502993349, 2.599916056557537, 0, -0.7873020502993349, 0, 0,
   -1.6661117377481922, 0, -12.243702660922095, 1.6661117377481922, 0, 0,
   2.352686800371387, 0, 0, 0, 0, 12.243702660922095, 
-2.352686800371387, 0,
   0, 0, 2.857877542171938, -4.50375057162902, 0, -2.857877542171938, 0,
   0.8654174979155087, 0, 4.50375057162902, -0.8654174979155087, 0, 0, 
0, 0,
   0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
-0.557546880846985,
   -2.599916056557537, 0, 0, 0, 0, 0.557546880846985, 0, 0,
   0.7873020502993349, 2.599916056557537, 0, -0.7873020502993349, 0, 0,
   -1.6661117377481922, 0, -12.243702660922095, 1.6661117377481922, 0, 0,
   2.352686800371387, 0, 0, 0, 0, 12.243702660922095, 
-2.352686800371387, 0,
   0, 0, 2.857877542171938, -4.50375057162902, 0, -2.857877542171938, 0,
   0.8654174979155087, 0, 4.50375057162902, -0.8654174979155087, 0, 0, 
0, 0,
   0, 0}, {0, 0, 0, 0, 0, 0, -0.557546880846985, -2.599916056557537, 0,
   -1.6661117377481922, 0, -12.243702660922095, 0, 2.857877542171938,
   -4.50375057162902, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1.6661117377481922, 0, 0,
   2.352686800371387, -2.857877542171938, 0, 0.8654174979155087, 0, 0, 
0, 0,
   0, 0.557546880846985, 0, 0, 0.7873020502993349, 0, 0, 0, 0,
   4.50375057162902, -0.8654174979155087, 0, 0, 0, 0, 0, 0, 
2.599916056557537,
   0, -0.7873020502993349, 0, 12.243702660922095, -2.352686800371387, 0, 
0, 0,
   0, 0, 0}, {0, 0, 0, 0, 0, 0, -0.557546880846985, -2.599916056557537, 0,
   -1.6661117377481922, 0, -12.243702660922095, 0, 2.857877542171938,
   -4.50375057162902, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1.6661117377481922, 0, 0,
   2.352686800371387, -2.857877542171938, 0, 0.8654174979155087, 0, 0, 
0, 0,
   0, 0.557546880846985, 0, 0, 0.7873020502993349, 0, 0, 0, 0,
   4.50375057162902, -0.8654174979155087, 0, 0, 0, 0, 0, 0, 
2.599916056557537,
   0, -0.7873020502993349, 0, 12.243702660922095, -2.352686800371387, 0, 
0, 0,
   0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
   0.557546880846985, 2.599916056557537, 0, 0, 0, 0, -0.557546880846985, 
0, 0,
   -0.7873020502993349, -2.599916056557537, 0, 0.7873020502993349, 0, 0,
   1.6661117377481922, 0, 12.243702660922095, -1.6661117377481922, 0, 0,
   -2.352686800371387, 0, 0, 0, 0, -12.243702660922095, 
2.352686800371387, 0,
   0, 0, -2.857877542171938, 4.50375057162902, 0, 2.857877542171938, 0,
   -0.8654174979155087, 0, -4.50375057162902, 0.8654174979155087, 0, 0, 
0, 0,
   0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, -1.6661117377481922, 2.857877542171938, 0,
   -0.557546880846985, 0, -4.50375057162902, 0, -2.599916056557537,
   -12.243702660922095, 0, 0, 0, 1.6661117377481922, -2.857877542171938, 
0, 0,
   0, 0, 0, 0, 0, 0.8654174979155087, 0, 0, 7.05373600742774*^14, 0, 0,
   0.557546880846985, 0, 4.50375057162902, 0, 0, 0, -0.8654174979155087, 
0, 0,
   0, 0, 0, 0.7873020502993349, 0, 0, 0, 2.599916056557537,
   12.243702660922095, 0, 0, 0, -2.352686800371387, 0, 0, 
-0.7873020502993349,
   0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, -1.6661117377481922,
   2.857877542171938, 0, -0.557546880846985, 0, -4.50375057162902, 0,
   -2.599916056557537, -12.243702660922095, 0, 0, 0, 1.6661117377481922,
   -2.857877542171938, 0, 0, 0, 0, 0, 0, 0, 0.8654174979155087, 0, 0,
   2.352686800371387, 0, 0, 0.557546880846985, 0, 4.50375057162902, 0, 
0, 0,
   -0.8654174979155087, 0, 0, 0, 0, 0, 0.7873020502993349, 0, 0, 0,
   2.599916056557537, 12.243702660922095, 0, 0, 0, -2.352686800371387, 
0, 0,
   -0.7873020502993349, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, -0.557546880846985, -2.599916056557537, 0, 0, 0, 0,
   0.557546880846985, 0, 0, 0.7873020502993349, 2.599916056557537, 0,
   -0.7873020502993349, 0, 0, -1.6661117377481922, 0, -12.243702660922095,
   1.6661117377481922, 0, 0, 2.352686800371387, 0, 0, 0, 0,
   12.243702660922095, -2.352686800371387, 0, 0, 0, 2.857877542171938,
   -4.50375057162902, 0, -2.857877542171938, 0, 0.8654174979155087, 0,
   4.50375057162902, -0.8654174979155087, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, -0.557546880846985, -2.599916056557537, 0,
   -1.6661117377481922, 0, -12.243702660922095, 0, 2.857877542171938,
   -4.50375057162902, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1.6661117377481922, 0, 0,
   2.352686800371387, -2.857877542171938, 0, 0.8654174979155087, 0, 0, 
0, 0,
   0, 0.557546880846985, 0, 0, 0.7873020502993349, 0, 0, 0, 0,
   4.50375057162902, -0.8654174979155087, 0, 0, 0, 0, 0, 0, 
2.599916056557537,
   0, -0.7873020502993349, 0, 12.243702660922095, -2.352686800371387, 0, 
0, 0,
   0, 0, 0}, {0, 0, 0, 0, 0, 0, -0.557546880846985, -2.599916056557537, 0,
   -1.6661117377481922, 0, -12.243702660922095, 0, 2.857877542171938,
   -4.50375057162902, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1.6661117377481922, 0, 0,
   2.352686800371387, -2.857877542171938, 0, 0.8654174979155087, 0, 0, 
0, 0,
   0, 0.557546880846985, 0, 0, 0.7873020502993349, 0, 0, 0, 0,
   4.50375057162902, -0.8654174979155087, 0, 0, 0, 0, 0, 0, 
2.599916056557537,
   0, -0.7873020502993349, 0, 12.243702660922095, -2.352686800371387, 0, 
0, 0,
   0, 0, 0}, {0, 0, 0, 0, 0, 0, -1.6661117377481922, 2.857877542171938, 0,
   -0.557546880846985, 0, -4.50375057162902, 0, -2.599916056557537,
   -12.243702660922095, 0, 0, 0, 1.6661117377481922, -2.857877542171938, 
0, 0,
   0, 0, 0, 0, 0, 0.8654174979155087, 0, 0, 2.352686800371387, 0, 0,
   0.557546880846985, 0, 4.50375057162902, 0, 0, 0, -0.8654174979155087, 
0, 0,
   0, 0, 0, 0.7873020502993349, 0, 0, 0, 2.599916056557537,
   12.243702660922095, 0, 0, 0, -2.352686800371387, 0, 0, 
-0.7873020502993349,
   0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, -1.6661117377481922,
   2.857877542171938, 0, -0.557546880846985, 0, -4.50375057162902, 0,
   -2.599916056557537, -12.243702660922095, 0, 0, 0, 1.6661117377481922,
   -2.857877542171938, 0, 0, 0, 0, 0, 0, 0, 0.8654174979155087, 0, 0,
   2.352686800371387, 0, 0, 0.557546880846985, 0, 4.50375057162902, 0, 
0, 0,
   -0.8654174979155087, 0, 0, 0, 0, 0, 0.7873020502993349, 0, 0, 0,
   2.599916056557537, 12.243702660922095, 0, 0, 0, -2.352686800371387, 
0, 0,
   -0.7873020502993349, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 
0, 0,
   0, 0, 0}};
References:
- Orthogonazlie with Method->"Householder"
  - From: Maris Ozols <marozols@gmail.com>
Prev by Date: Re: Re: Re: Using Mathematica notebooks in presentations?
Next by Date: Re: How to remove Head from expression
Previous by thread: Re: Orthogonazlie with Method->"Householder"
Next by thread: Re: Orthogonazlie with Method->"Householder"