hyperplane least square through points - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-18T21:03:51Z http://mathoverflow.net/feeds/question/77465 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77465/hyperplane-least-square-through-points hyperplane least square through points Titus Nicolae 2011-10-07T16:25:53Z 2011-10-08T12:09:32Z <p>I have a set of N, N>>n. n-dimensional vectors and would like to represent each of them, with approximation, as a linear combination of m, m &lt; n, n-dimensional vectors. How should I choose the vectors so that the approximation is the best possible? I think it is an extension of the least square fitting of a line through points in a 2D plane, but I don't know how.</p> http://mathoverflow.net/questions/77465/hyperplane-least-square-through-points/77525#77525 Answer by Gottfried Helms for hyperplane least square through points Gottfried Helms 2011-10-08T10:50:11Z 2011-10-08T12:09:32Z <p>Hmm, I'm not sure, whether I got your problem right, but well, I'll give it a try. </p> <p>I assume the N datvectors as rowvectors consisting of n datapoints (where n &lt;&lt; N). Then the usual PCA assumes the columns as axes in an n-dimensional coordinate-system having N vectors beginning at the origin, say the data-matrix $\small Z$. The usual principal components can then be found by rotations of the columns, in matrix-notation $\small Z \cdot T$ , where $\small T$ is a rotation-matrix. </p> <p>Now I understand your question such that you want to express your <strong>N</strong> data-vectors as linear combinations of a smaller set of (pairwise orthogonal) component(-vectors). </p> <p>This seems simply the question of rotating the <em>rows</em> of $\small Z$ to their PC-position, thus $\small T \cdot Z$ and you get (at most) <em>n</em> component-rowvectors which can be composed to represent $\small Z$ by the inverse row-rotation.<br> And the best representation of $\small Z$ by <em>m</em> components only, where $\small m \lt n$ would likely be done to use only the first <em>m</em> components ; so to say $\small PC_n = T \cdot Z$ giving at most <em>n</em> non-zero component-vectors in $\small PC_n$ . Then to have the best representation by $\small m \lt n$ rowvectors set all vectors in $\small PC_n$ of indexes <em>k</em> where $\small m &lt; k \le n$ to zero to get $\small PC_m$ and apply $\small Z_m=T^\tau \cdot PC_m$ where $\small Z_m$ might then be the best rank- <em>m</em> -approximation to $\small Z$ </p> <p><hr> Example: (sorry, this is in my proprietary MatMate-code (don't have Maple/Matlab/Math'ca) but should illustrate the pseudocode sufficiently) <a href="http://go.helms-net.de/stat/mo/MO_111008.htm" rel="nofollow">see protocol of worked example</a> : </p> <pre><code>//****** MatMate Version 0.1108 Beta ***************************** // MO-Problem: // Express N rowvectors optimally by m component-vectors (least squares) // Proposed solution: use PCA on rows of datamatrix // ------------------------------------------------------------- // 1) generate random-data n=6 v=20 // this is big-N in the problem description m=3 set randomstart=41 Z = randomn(v,n) // generate normally distributed randomdata Z = zvaluezl(abwzl(Z)) // center and standardize Z rowwise //------------------------------------------------------- // 2) find principal components rowwise; // note: due to centering of rowdata there are // maximally only n-1 independent components! // center data columnwise ME = meansp(Z) // get a rowvector containing the columnwise means C = Z - ME // ME will implicitely be expanded to fit the dimension of Z // C contains then the columnwise recentered data // get the required rotation-matrix T first // because in MatMate rotations are done on columns, we have // to transpose C as well as the result (using ' as transpose-operator) T = gettrans(C',"pca")' PC_n = T * C // the first n-1 rows contain the principal components // 3) now set all rowvectors with index k&gt;m to zero into a new matrix PC_m PC_m = { PC_n[1..m,*], Null(v-m,n) } // 4) reverse the rotation where only the m-components are used C_m = T' * PC_m Z_m = C_m + ME // the rowvector ME is automatically expanded to fit the C_m matrix // 5) check quality of approximation chk = (Z-Z_m) ^# 2 // Check differences, ^# 2 means: apply power of 2 elementwise err = sqrt(sum(chk)) // check overall-error </code></pre>