MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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
v=20   // this is big-N in the problem description
         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
share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.