Why do we want to have orthogonal bases in decompositions? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T06:13:47Z http://mathoverflow.net/feeds/question/42040 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42040/why-do-we-want-to-have-orthogonal-bases-in-decompositions Why do we want to have orthogonal bases in decompositions? İsmail Arı 2010-10-13T17:52:24Z 2010-10-15T05:10:46Z <p>In the decompositions I encountered so far, we all had orthogonal set of bases. For example in Singular Value Decomposition, we had orthogonal singular right and left vectors, in [discrete] cosine transform (or [discrete] fourier transform) we had again orthogonal bases.</p> <p>To describe any vector $x \in \mathbb{C}^N$, we need to have $N$ independent set of basis vectors but independent doesn't necessarily mean orthogonal. My intentions behind selecting orthogonal vectors are as follows:</p> <ul> <li>The solution is not unique for $x$ if the basis are not orthogonal.</li> <li>It is easy to find the solution numerically by projecting $x$ onto each vector and this solution doesn't depend on the order of the bases. Otherwise, it depends on the order.</li> <li>If we are talking about some set of vectors, they might be correlated in the original space, but uncorrelated in the transformd space which might be important when analyzing the data, in dimensionality reduction or compression.</li> </ul> <p>I'm trying to understand the big picture. Do you think that I am right with these? Do you have any suggestions, what is the main reason for selecting orthogonal bases?</p> http://mathoverflow.net/questions/42040/why-do-we-want-to-have-orthogonal-bases-in-decompositions/42041#42041 Answer by Anadim for Why do we want to have orthogonal bases in decompositions? Anadim 2010-10-13T18:13:40Z 2010-10-13T18:13:40Z <p>Well, when multiplying a vector ${\bf x}$ (say of norm 1) with a matrix ${\bf A}$ you are expecting to get a vector that lies on the surface of the ellipse $\left\|{\bf A}{\bf x}\right\|^2_2$. The directions of the axes of this ellipse are the eigenvectors and the eigenvalues dictate the equatorial radii. So every time you multiply a vector with that matrix, this decomposition into axes and radii tell you how your matrix distorts an "input" vector. That might be one pictorial reason :)</p> http://mathoverflow.net/questions/42040/why-do-we-want-to-have-orthogonal-bases-in-decompositions/42053#42053 Answer by Willie Wong for Why do we want to have orthogonal bases in decompositions? Willie Wong 2010-10-13T19:00:11Z 2010-10-14T14:10:50Z <p>Your first point, non-uniqueness, is definitely false. One of the basic facts in linear algebra is precisely that for any fixed set of basis vectors (we don't even have to work on a vector space endowed with an inner product, so orthogonality doesn't come in at all), a given vector has a unique decomposition. </p> <p>For if that were not true, let the basis vectors be $e_1, \ldots, e_n$, then you have two sets of numbers $a_1, \ldots a_n$ and $b_1, \ldots, b_n$ such that</p> <p>$$a_1 e_1 + \cdots + a_n e_n = x = b_1 e_1 + \cdots + b_n e_n \implies (a_1 - b_1) e_1 + \cdots + (a_n - b_n) e_n = 0$$</p> <p>if the sets <code>$a_*$</code> and <code>$b_*$</code> are not identical, this implies that $e_1\ldots e_n$ are linearly dependent, contradicting the assumption that they form a basis. </p> <p>The second point, however, is a biggie. Without an inner product you cannot define an orthgonal projection. Now, generally, this is not too much of a problem. Given the basis vectors $e_1,\ldots, e_n$, finding the coordinates $a_1,\ldots, a_n$ of a given vector $x$ in this basis is just solving a linear system of equations, which actually is not too hard numerically, in <em>finite dimensional systems</em>. In infinite dimensional systems this inversion of the transformation matrix business gets slightly tricky. </p> <p>The key is to note that without using the orthogonal projection, you <em>cannot</em> answer the question "what is the length of $x$ in the direction of $e_1$?" without knowing the entire set of basis vectors. (Remember that without using the orthogonal projection, you need to solve a linear system of equations to extract the coordinates; if you only specify one of the basis vectors, you do not have a complete system of equations, and the solution is underdetermined. I suspect this is what you had in the back of your mind for the first point.) This is actually a very fundamental fact in geometry, regarding coordinate systems. (I've once heard this described as the "second fundamental mistake in multivariable calculus" made by many students.) </p> <p>Using the orthogonal projection/the inner product, you can answer the question, as long as you allow only orthgonal completions of the basis starting from the known vector. This fact is immensely useful when dealing with infinite dimensional systems. </p> <p>I also don't quite like your formulation of the third point. A vector is a vector is a vector. It is independent of the coordinate representation. So I'd expect that if two vectors are correlated (assuming correlation is an intrinsic property), they better stay correlated without regard to choice of bases. What is more reasonable to say is that two vectors maybe uncorrelated in reality, but not obviously so when presented in one particular coordinate system, whereas the lack of correlation is immediately obvious when the vectors are written in another basis. But this observation has rather little to do with orthogonality. It only has some relation to orthogonality if you define "correlation" by some inner product (say, in some presentations of Quantum Mechanics). But then you are just saying that orthogonality of two vectors are not necessarily obvious, except when they are. </p> <hr> <p>My personal philosophy is more one of practicality: the various properties of orthogonal bases won't make solving the problem harder. So unless you are in a situation where those properties don't make solving the problem easier, and some other basis does (like what Ryan Budney described), there's no harm in prefering an orthogonal basis. Furthermore, as Dick Palais observed above, one case where an orthogonal bases really falls out naturally at you is the case of the spectral theorem. The spectral theorem is, in some sense, the correct version of your point 3, that in certain situations, there <em>is</em> a set of basis vectors that are mathematically special. And this set happens to always be orthogonal. </p> <hr> <p><strong>Edit</strong> A little more about correlation. This is what I like to tell students when studying linear algebra. A vector is a vector. It is an object, not a bunch of numbers. When I hand you a rectangular box and ask you how tall the box is, the answer depends on which side is "up". This is similar to how you should think of the coordinate values of a vector inside a basis: it is obtained by a bunch of measurements. (Picking which side is "up" and measuring the height in that direction, however, in a non-orthogonal system, will require knowing all the basis vectors. See my earlier point.) </p> <p>The point is that to quantitatively study science, and to perform numerical analysis, you can only work with numbers, not physical objects. So you have to work with measurements. And in your case, the correlation you are speaking of is correlation between the measurements of (I suppse) different "properties" of some object. And since what and how you measure depends on which basis you choose, the correlation between the data will also depend on which basis you choose. If you pick properties of an object that are correlated, then your data obtained from the measurements will also be correlated. The PCA you speak of is a way to disentangle that. It may be difficult to determine whether two properties of an object is correlated. Maybe the presence of a correlation is what you want to detect. The PCA tells you that, if there were in fact two independent properties of an object, but you just chose a bad set of measurements so that the properties you measure do not "line up" with the independent properties (that the properties you measure have a little bit of each), you can figure it out with a suitable transformation of the data at the end of the day. So you don't need to worry about choosing the best set of properties to measure. </p> http://mathoverflow.net/questions/42040/why-do-we-want-to-have-orthogonal-bases-in-decompositions/42080#42080 Answer by Federico Poloni for Why do we want to have orthogonal bases in decompositions? Federico Poloni 2010-10-13T23:02:24Z 2010-10-13T23:02:24Z <p>I assume you are seeing things from a numerical point of view, since you only mentioned computation-oriented decompositions.</p> <p>So here's a computational motivation: orthogonal matrices have condition number 1, thus multiplying and dividing by them is a numerically tame operation that does not increase the (norm-wise) errors. For instance, even when you work with symplectic matrices, you usually look for symplectic <em>and</em> orthogonal matrices.</p> http://mathoverflow.net/questions/42040/why-do-we-want-to-have-orthogonal-bases-in-decompositions/42250#42250 Answer by Dirk for Why do we want to have orthogonal bases in decompositions? Dirk 2010-10-15T05:10:46Z 2010-10-15T05:10:46Z <p>Maybe some examples of non-orthogonal decompositions are helpful: In the context of wavelet one frequently uses <a href="http://en.wikipedia.org/wiki/Biorthogonal_system" rel="nofollow">bi-orthonormal systems</a>, i.e. two sets of vectors $(u_i)$ and $(v_i)$ such that $\langle u_i,v_j\rangle = \delta_{i,j}$. In this setting the calculations of coefficients can be done stably and efficiently. In real life, such bi-orthogonal wavelet bases are at the heart of the <a href="http://en.wikipedia.org/wiki/Jpeg_2000" rel="nofollow">JPEG 2000</a> compression standard.</p> <p>Another important notion in this context is the notion of <a href="http://en.wikipedia.org/wiki/Frame_of_a_vector_space" rel="nofollow">frames</a>.</p>