Question

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.

Answer 1

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