# hyperplane least square through points

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 < 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.

-
Did you consider to look into principal components analysis (PCA)? – Gottfried Helms Oct 7 '11 at 16:41
Thanks for the suggestion, I'm looking into it – Titus Nicolae Oct 7 '11 at 16:52
If $N=1$, this seems to be just ordinary linear regression. Could it be that just doing ordinary linear regression $N$ times is what you need? Especially in view of the word "each". – Michael Hardy Oct 7 '11 at 20:31
Looking at this later, I'm inclined to agree with Gottfried Helms' suggestion. – Michael Hardy Oct 7 '11 at 22:22
You don't tell us whether you know in advance which $m$ vectors you want as basis vectors. If you do, it's essentially $N$ different linear regressions. If you don't, but want to decide that based on the data, then PCA is probably what you want. – Michael Hardy Oct 7 '11 at 22:23

Hmm, I'm not sure, whether I got your problem right, but well, I'll give it a try.

I assume the N datvectors as rowvectors consisting of n datapoints (where n << 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.

Now I understand your question such that you want to express your N data-vectors as linear combinations of a smaller set of (pairwise orthogonal) component(-vectors).

This seems simply the question of rotating the rows of $\small Z$ to their PC-position, thus $\small T \cdot Z$ and you get (at most) n component-rowvectors which can be composed to represent $\small Z$ by the inverse row-rotation.
And the best representation of $\small Z$ by m components only, where $\small m \lt n$ would likely be done to use only the first m components ; so to say $\small PC_n = T \cdot Z$ giving at most n 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 k where $\small m < 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- m -approximation to $\small Z$

Example: (sorry, this is in my proprietary MatMate-code (don't have Maple/Matlab/Math'ca) but should illustrate the pseudocode sufficiently) see protocol of worked example :

//******  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>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
-