0

I have a set of vectors. For simplicity, suppose there are $n=20$ vectors and each has $p=5$ elements. These vectors are generated from some experiments, and so it is not very apparent how they are linearly dependent. A vector can be $V_1=[1,0,2,4,2.5]$ and another may be $V_2=[1.9,0,4.05,8,5.01]$, which seems like they are not linearly dependent, but if we look closely, it seems that the second vector could be a noisy version of the vector $V_2'=[2,0,4,8,5]$ which is definitely related to $V_1$.

So, if I have a situation like this, that may be out of the 20 vectors 6 are linearly related to each other but are noisy, another 12 are also linearly related together and the rest of the 2 are completely different. So, basically it seems that this set of 20 vectors can be represented by just 4 vectors, the 1st one represents the set of 6, the 2nd one represents the set of 12 and the last two are the two unique ones. How do I find these 4 vectors?

Also, I don't want to reduce the dimension of the vectors, they should have $p=5$ elements. I just want to reduce the number of vectors in the set and remove the redundancy.

I looked into Principal Components Analysis (PCA) but PCA reduces the dimension of the vector, not the redundancy which I don't want.

Also, the groups of 6 and 12 are just for example, I will not know in advance how many vectors in the set of 20 are similar to each other. Can anyone help me out with this problem?

Thanks in advance.

whuber
  • 281,159
  • 54
  • 637
  • 1,101
Arindam
  • 103
  • 1
  • 3
    PCA does not reduce the length of the vectors, nor does it reduce the number of vectors. However, if you select the first few principal components, you will typically have fewer vectors of the same length that, combined, explain most (often almost all) of the variation in the original set of vectors. This would seem to be what you want. – jbowman Nov 05 '18 at 16:59
  • 2
    I removed the "large-data" tag because since approximately the year 1600 nobody has conceived of 20 5-vectors as being "large"! @jbowman is correct about PCA: look into it. – whuber Nov 06 '18 at 02:07
  • Is not clear what exactly you want from the data. Is your issue with PCA that it returns vectors that are a linear combination of two extremes and you want the vectors in their 'natural' shape? Or do you just want to be able to group the vectors and get a representative vector for each group? – ReneBt Nov 06 '18 at 04:51
  • Thanks for the reply everyone. @ReneBt . Yes I want to group the vectors and want a representative of each group. – Arindam Nov 11 '18 at 17:40

2 Answers2

2

You could simply use row reduction. To do this, you could simply take each vector and place them in columns, place the matrix in row reduced echelon form, and then any column that does not have a leading 1, will be dependent on other vectors. For example, for simplicity and without loss of generality, let's say you have 4 vectors, each with four elements, placed in a vector A.

$A = \begin{bmatrix} 1 & 3 & -1 & 0 \\ 4 & 1 & 7 & 11 \\ 0 & 4 & -4 & -4 \\ 2 & 0 & 4 & 6 \end{bmatrix}$

Row reduce A to place it in row reduced echelon form ($RREF$):

$RREF(A)=\begin{bmatrix} 1 & 0 & 2 & 3 \\ 0 & 1 & -1 & -1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$

You'll see now that columns $3$ and $4$ in $RREF(A)$ do not have leading $1$'s. This implies that they they are dependent on other columns. Specifically:

$\begin{bmatrix} -1 \\ 7 \\ -4 \\ 4 \end{bmatrix}=2\begin{bmatrix} 1 \\ 4 \\ 0 \\ 2 \end{bmatrix}-\begin{bmatrix} 3 \\ 1 \\ 4 \\ 0 \end{bmatrix}$

$\begin{bmatrix} 0 \\ 11 \\ -4 \\ 6 \end{bmatrix}=3\begin{bmatrix} 1 \\ 4 \\ 0 \\ 2 \end{bmatrix}-\begin{bmatrix} 3 \\ 1 \\ 4 \\ 0 \end{bmatrix}$

Notice here that column $3$ of $RREF(A)$ corresponds to a linear scalar combination of columns $1$ and $2$, as does column $4$.

But if each column of $RREF(A)$ has a leading $1$, then each column is linearly independent.

StatsStudent
  • 10,205
  • 4
  • 37
  • 68
  • How stable is this under the stated probability assumptions about noise? (I suspect it is not.) – whuber Nov 06 '18 at 02:08
  • Or course, this will only work under exactly linear dependencies. It will not work under noise. I'm not sure any method would work without further restrictive assumptions. – StatsStudent Nov 06 '18 at 02:32
  • 1
    PCA, as suggested by @jbowman, works just fine. See https://stats.stackexchange.com/questions/16327 for explanations. – whuber Nov 06 '18 at 02:42
  • Yes, of course. But PCA, makes some additional restrictions, no? Thanks, @whuber. – StatsStudent Nov 06 '18 at 03:50
  • I don't know what restrictions you might be referring to. It makes no assumptions whatsoever--it's purely a geometrical analysis of a collection of vectors. – whuber Nov 06 '18 at 04:03
0

You should look at the correlation between your vectors : https://en.wikipedia.org/wiki/Pearson_correlation_coefficient

The correlation coefficient allow you to see how related two vectors are, it is ranged between [-1 ; 1] with 1 perfect positive linear relationship and -1 perfect negative linear relationship, 0 no relationship.

You can then select vectors that are not correlated.

Wawv
  • 101
  • 1
  • I'm afraid this stops working in dimensions larger than $2.$ Linear relations in higher dimensions cannot be understood simply by examining their pairwise correlations. – whuber Nov 06 '18 at 02:09