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.
-
3$\begingroup$ Did you consider to look into principal components analysis (PCA)? $\endgroup$– Gottfried HelmsOct 7, 2011 at 16:41
-
$\begingroup$ 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". $\endgroup$– Michael HardyOct 7, 2011 at 20:31
-
$\begingroup$ Looking at this later, I'm inclined to agree with Gottfried Helms' suggestion. $\endgroup$– Michael HardyOct 7, 2011 at 22:22
-
1$\begingroup$ 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. $\endgroup$– Michael HardyOct 7, 2011 at 22:23
-
$\begingroup$ I don't know in advance which m vectors to choose. They could be from among the N ones, but it's not mandatory. $\endgroup$– Titus NicolaeOct 8, 2011 at 9:20
1 Answer
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