Talk:Gram–Schmidt process/Archive 1

This is an archive of past discussions about Gram–Schmidt process. Do not edit the contents of this page. If you wish to start a new discussion or revive an old one, please do so on the current talk page.

Archive 1

Maybe we need an illustration

Maybe we need an illustration of the projection just like most text books.

I just created this…

…would it fulfill its purpose? –Gustavb 07:16, 18 February 2006 (UTC)

Yes, I guess that is basically it. However, I think that

u_{2}

is too long. We need to have

u_{2}+\operatorname {proj} _{u_{1}}(v_{2})=v_{2},

so the direction of

u_{2}

is correct, but it should only go up to the dashed line. Does that make sense to you? If not, I'll change the picture myself, but I don't know the TeX package you are using (it looks quite easy to use though). -- Jitse Niesen (talk) 14:52, 18 February 2006 (UTC)

Yes, of course…guess I was tired when I did it. I have now created a new one but unfortunately I can't upload it due to a restriction in wikimedia commons which only allows users registered for more than four days to replace files (I registered yesterday.) –Gustavb 15:24, 18 February 2006 (UTC)

That seems rather silly to me; what's the purpose of prohibiting somebody from overwriting their own files? If you want, you can email it to me at my-first-name@ma.hw.ac.uk (making the obvious substitution) and I'll upload it on your behalf. You can also just wait a couple of days. -- Jitse Niesen (talk) 15:49, 18 February 2006 (UTC)

I don't think it checks who uploaded the original file – it just block all uploads for the purpose of reducing vandalism (I assume). So yes, it's a bad solution. Thanks for uploading the new version. –Gustavb 16:27, 18 February 2006 (UTC)

Basis

Does the set of vectors v₁, …, v_k not need to form a basis over the vector space? Tis is not mentioned anywhere on the page and is very important to the defintion I have learnt.Stb20 12:48, 22 January 2007 (UTC)

I'm rather sure that they don't need to form a basis. Do you have a text book which says that they do need to form a basis?

They do need to be linearly independent though. This is mentioned in the article. -- Jitse Niesen (talk) 11:35, 23 January 2007 (UTC)

My book does mention it yes, although it is refering to this process in forming an othogonal basis, rather than just an orthogonal set of vectors, so I assume this is the only time it applies. Is it still worth a mention? Stb20 11:47, 24 January 2007 (UTC)

Notation

for the projection, shouldn't it be proj(V) = [(V*U)/(U*U)] * U?? * is the dot product.

The author wrote it as (v,u)/(u, u) * u, which I don't understand what they mean.

<V,U> is a matrix or something else?

If it is a matrix then there shouldn't be division. If the expression is still correct, please explain what do the symbols mean.

Xfliang 05:40, 16 February 2007 (UTC)

<v,u> is another notation for the dot product of v and u. I added a bit to the article to explain this. -- Jitse Niesen (talk) 07:17, 16 February 2007 (UTC)

Factual accuracy on the method presented here

Maybe I'm reading the information on the page wrong, but as far as I can tell if I try and use the information here to create the 4th Legendre polynomial starting from 1,x,x^2,x^3 etc. I get an incorrect answer $\left(x^{4}-{\frac {5}{7}}x^{2}-{\frac {1}{5}}\right)$ , however if I use the information on Mathworld I get the right answer. Eraserhead1 23:31, 18 February 2007 (UTC)

I'm sorry, but I can't see where the algorithm on this page is different from the algorithm in MathWorld. Could you perhaps explain where the algorithms differ? Is P₄ the first case where you get different results? -- Jitse Niesen (talk) 13:01, 10 March 2007 (UTC)

modified gram-schmidt

It'd be nice to go over the distinction between classical and modified gram-schmidt. If anyone's interested in writing it up, the following PDF is a decent example to follow: http://www-math.mit.edu/~persson/18.335/lec5handout6pp.pdf Lavaka (talk) 01:04, 3 January 2008 (UTC)

numerically stable algorithm

I think there"s a mistake in the superscripts in that section. In the last equation it should be either u_k^(k-1) OR on the right-hand side of the eqution all superscripts must be increased by one. Also the notation for the projection operator is a bit confusing: isn't actually meant proj_uk(k-1)uk(k-2) instead of proj_u(k-1)uk(k-2)? There seems to be a k missing... 134.60.1.151 12:31, 14 June 2007 (UTC)

Perhaps it's easier to write the algorithm as

\mathbf {u} _{k}^{(1)}=\mathbf {v} _{k}-\mathrm {proj} _{\mathbf {u} _{1}}\,\mathbf {v} _{k},

\mathbf {u} _{k}^{(2)}=\mathbf {u} _{k}^{(1)}-\mathrm {proj} _{\mathbf {u} _{2}^{(1)}}\,\mathbf {u} _{k}^{(1)},

\vdots

\mathbf {u} _{k}^{(k-2)}=\mathbf {u} _{k}^{(k-3)}-\mathrm {proj} _{\mathbf {u} _{k-2}^{(k-1)}}\,\mathbf {u} _{k}^{(k-3)},

\mathbf {u} _{k}^{(k-1)}=\mathbf {u} _{k}^{(k-2)}-\mathrm {proj} _{\mathbf {u} _{k-1}^{(k-2)}}\,\mathbf {u} _{k}^{(k-2)}.

The vectors

\mathbf {u} _{1},\mathbf {u} _{2}^{(1)},\ldots ,\mathbf {u} _{k}^{(k-1)}

are then orthogonal. If you now use

\mathbf {u} _{k}

to denote the vector

\mathbf {u} _{k}^{(k-1)}

, you get the algorithm as mentioned in the article. Perhaps the notation isn't quite consistent, but I prefered to save some superscripts. Do you think the version with

\mathbf {u} _{k}^{(k-1)}

is less confusing?

Do you understand the difference between the original and the stabilized algorithm on an implementation level? There is pseudocode for the stabilized version in the article. The original version looks like

input: v₁, …, v_k; output: u₁, …, u_k

for j from 1 to k do

\mathbf {u} _{j}\leftarrow \mathbf {v} _{j}

for i from 1 to j − 1 do

\mathbf {u} _{j}\leftarrow \mathbf {u} _{j}-\langle \mathbf {v} _{j},\mathbf {u} _{i}\rangle \mathbf {u} _{i}

end for

\mathbf {u} _{j}\leftarrow {\frac {\mathbf {u} _{j}}{\|\mathbf {u} _{j}\|}}

end for

It's only a subtle difference in the code. -- Jitse Niesen (talk) 13:26, 14 June 2007 (UTC)

Yes, I got the difference:-) Thanks for the answer. Though I'm still thinking about the why...Raneko 10:20, 15 June 2007 (UTC)

Shouldn't the line in the pseudocode:

for i from 1 to j − 1 do

actually be:

for i from j + 1 to k do

With that change, my Python implementation produces sensible results (unlike the original):

def stabGramSchmidt(a):
	# (http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process#Algorithm )
	k,n = a.shape
	for j in xrange(k):
		for i in xrange(j+1,k):
			a[j] -= a[i] * dot(a[i],a[j]) / dot(a[i],a[i]) # remove from a[j] projection of a[j] over a[i]
		a[j] /= linalg.norm(a[j])	# normalize
	return a

— Preceding unsigned comment added by 219.77.188.254 (talk) 01:18, 12 July 2009 (UTC)

Untitled

I agree with the user below. How can it have been wrong here for SO long. Someone needs to change this. Check ANY reference if its not obvious.

—Preceding unsigned comment added by 128.95.30.185 (talk) 22:11, 15 December 2009 (UTC)

The projection $P_{u}(v)=u{\frac {<u,v>}{<u,u>}}$ = is not self adjoint. It should be $P_{u}(v)=u{\frac {<v,u>}{<u,u>}}$ , or else it should be pointed out that $<,>$ is understood as linear in the second argument. Weeping604 (talk) 12:14, 10 July 2008 (UTC)

In the definition of the projection operator I changed <u, v> to denote the inner product instead of the dot product. The dot product is just a special case.

Maciej

Does anyone know when the Gram Schimdt process was discovered? And who Mr. Gram and Mr. Schmidt are?

Jørgen Pedersen Gram (1850-1916), Danish mathematician.

Sebastjan

See EXTERNAL LINKS in the article. It tells you.JFB80 (talk)

I was going to rewrite the process in terms of projections to clean it up a bit, but I'll probably stuff it up somewhere and be shouted at. So, if you feel up to doing so, I think it'd clear up the process greatly. Dysprosia 01:41, 26 August 2004 (UTC)

I changed the calculation of u_2 etc. to use projection onto u_1 instead of onto e_1. This allows the process to work in fields where you cannot take square roots, such as the rationals. I have a program that produces a series of orthogonal vectors spanning the right space. norm@cap-lore.com .

Ewwwwww, I really don't like the notation proj_u v. If anything it should be written proj_v u, to emphasize that the projection is just a scaling of u. — Preceding unsigned comment added by 136.152.145.84 (talk) 17:34, 10 September 2006 (UTC)

Unknown alternative method

The last paragraph is intriguing, but there's no actual substance to it:

"In Quantum Mechanics there are several orthogonalization schemes with characteristics better suited for applications than the Gram-Schmidt one. The most important among them are the Symmetric and the Canonical orthonormalization (see Solivérez & Gagliano)."

I added a clarification tag. 128.171.78.5 (talk) 23:18, 29 October 2012 (UTC)

modified Gram-Schmidt is possibly flawed

The normalisation procedure may introduce errors in finite precision calculations. Thus, in the modified Gram-Schmidt process, the higher-order vectors have to be projected onto the *normalised* vectors previously obtained, haven't they?? Drgst (talk) 21:10, 29 July 2013 (UTC)

Joke

Twice I removed ([1], [2]) the joke added by 134.10.12.115 (talk · contribs) aka 134.10.25.131 (talk · contribs · WHOIS). It was also, for obvious reasons, removed by Cluebot ([3]). I think we shouldn't insult our humourless readers with that kind of lame jokes. - DVdm (talk) 22:17, 30 October 2013 (UTC)

Not sure

Not sure what Weeping604 was thinking, but he's wrong. Both of those expressions are vectors, and so it's impossible for either to be self-adjoint. However, if you consider $P_{u}(v)=u{\frac {<u,v>}{<u,u>}}=u{\frac {u^{*}v}{u^{*}u}}={\frac {uu^{*}}{u^{*}u}}v$ , then $P_{u}={\frac {uu^{*}}{u^{*}u}}$ is the projection matrix you multiply any vector against: $P_{u}v$ to project it onto $u$ and it IS self adjoint.

I don't even see how to convert Weeping604's second expression into a projection matrix time $v$ .

There's a very good reason why the standard is to define Hermitian forms (the complex version of bilinear forms which encompass inner product and dot product) as conjugate linear in the first term and linear in the second term; it simplifies the notation. Because of how matrix multiplication is defined, you're able to denote the complex inner product as $a^{*}b$ . If you define your Hermitian form as conjugate linear in the second term, then you have to represent your inner product as $a^{T}{\overline {b}}$ . --Yoda of Borg (talk) 08:39, 5 November 2013 (UTC)

I aggree that

P_{u}(v)=u{\frac {<u,v>}{<u,u>}}

is selfadjoint; the problem is that it reads

P_{u}(v)=u{\frac {<v,u>}{<u,u>}}

in the article!

I could change it in the text, but the gif next to it uses also the *wrong* version; I don't know how to update it. JoghurtGF (talk) 09:50, 5 January 2017 (UTC)