从Matlab中的一组向量中提取最大的线性独立向量集 [英] Extracting the largest set of linearly independent vectors from a set of vectors in matlab

问题描述

与matlab合作是我的新手.我找不到一种明显的方法来从给定的向量集中提取线性独立向量的最大子集.

I am new to working with matlab. I couldn't find an obvious way to to extract the largest subset of linearly independent vectors from a given set of vectors.

因此，给定一个集合V = [v1 v2-vn]，其中dim(vi)>> n(i = 1,2,3，....)我需要找到一个随机的r个线性独立向量的集合"vi"(其中r为最大)，即从V中删除所有线性相关的"vi"向量.抱歉，如果这是模棱两可的，但找不到更好的陈述方式.

So given a set V = [v1 v2 -- vn] where dim(vi) >> n (i=1,2,3,....) I need to find a random set of r linearly independent vectors "vi" (where r is maximal), i.e removing ALL (n-r) linearly dependent "vi" vectors from V. Sorry if this is ambiguous but can't find a better way to state it.

推荐答案

我将假设您的向量均为n维，我们可以将它们全部合并为一个矩阵.如果我们讨论矩阵和线性代数，您正在寻找的是矩阵的列空间 .简而言之，列空间定义为矩阵中可以在n维空间中唯一生成另一个向量的列的集合.或者，它是列向量的所有可能的线性组合的集合.这样，如果您想找到最大的线性独立向量集，您要做的就是确定矩阵的列空间是多少.

I'm going to assume that your vectors are all n-dimensional, and that we can concatenate them all into a single matrix. If we go into matrix and linear algebra, what you are looking for is the Column Space of a matrix. Simply put, the column space is defined as the set of columns in your matrix that can uniquely produce another vector in n-dimensional space. Or, it is the set of all possible linear combinations of the column vectors. As such, if you want to find the largest set of linearly independent vectors, all you have to do is determine what the column space of your matrix is.

因此，假设您的矩阵V的大小为n x m，我们有m列/向量，每列的大小为n x 1(或n行)，则您可以将 rref 或 R ow- R 受教育的 E chelon F orm(RREF)命令.这样可以将矩阵缩减为行缩减的梯形表格.这是找到矩阵的列空间的开始.您将这样称呼它:

Therefore, given your matrix V which is of size n x m, where we have m columns / vectors, with each column being of size n x 1 (or n rows), you would call the rref or the Row-Reduced Echelon Form (RREF) command. This reduces your matrix down to its row-reduced echelon form. This is the beginning of finding the column space for a matrix. You would call it like so:

[R, RB] = rref(V);

R将包含RREF形式的V，而RB将包含R的索引或列号形成列空间.因此，如果要生成线性独立的向量，则只需执行以下操作:

R would contain the RREF form of V and RB would contain the indices or column numbers of R that form the column space. Therefore, if you want to produce your linearly independent vectors, you simply have to do:

VMax = V(:,RB);

VMax将仅包含形成列空间的V列，因此是线性独立的向量.如果要确定有多少个独立向量，只需简单地计算我们有多少RB个值:

VMax will contain only those columns of V that formed the column space, and hence those that are linearly independent vectors. If you want to determine how many independent vectors we have, you simply have to count how many values of RB we have:

r = numel(RB);

---

这是一个简单的例子来说明我的观点.假设我有这个矩阵:

---

Here's a quick example to illustrate my point. Supposing I have this matrix:

>> V = [1 1 2 0; 2 2 4 9; 3 3 6 7; 4 4 8 3]

V =

     1     1     2     0
     2     2     4     9
     3     3     6     7
     4     4     8     3

第二列/向量仅仅是第一个向量.第三列/向量只是第一个向量加第二个向量，也可以是第一个或第二个向量的两倍.无论哪种方式，这都不是线性独立的向量，因为它基于第一个向量.第二个向量也是如此.最后一个向量与其他三个向量无关，因为我们无法创建可以从其他三个向量产生最后一个向量的组合或缩放.如果我们调用rref，将会发生以下情况:

The second column / vector is simply the first vector. The third column / vector is simply the first vector plus the second vector, or it could be twice the first or second vector. Either way, this is not a linearly independent vector as this is based off of the first vector. The same goes with the second vector. The last vector is independent of the other three as there is no way we can create combinations or a scaling that can produce this last vector from the other three. If we called rref, this is what will happen:

>> [R, RB] = rref(V)

R =

     1     1     2     0
     0     0     0     1
     0     0     0     0
     0     0     0     0


RB =

     1     4

R包含行精简梯形形式，而RB告诉我们哪些列是线性独立的或形成A的列空间.如您所见，只有第1列和第4列是线性独立的，这很合理.如果您还查看R的最后两行，我们可以看到它们由全零组成.这暗示着矩阵的 rank ，它只是矩阵的总数非零的行(或列，具体取决于您的工作).这也告诉您有多少向量形成列空间.

R contains the row reduced echelon form, while RB tells us which columns are linearly independent or form the column space of A. As you can see, only columns 1 and 4 are linearly independent, which makes perfect sense. If you also take a look at the last two rows of R, we can see that they consist of all zeroes. This alludes to the rank of a matrix, where it is simply the total number of rows (or columns depending on what you're doing) that are non-zero. This also tells you how many vectors form the column space.

要完成任务，只需执行以下操作:

To complete your task, simply do:

>> VMax = V(:,RB)

VMax =

     1     0
     2     9
     3     7
     4     3

如您所见，VMax的每一列都是V的线性独立向量，它也形成了V的列空间.

As you can see, each column of VMax is a linearly independent vector from V, which also forms the column space of V.

现在，您的下一个任务是每次运行算法时从此列空间中随机选择线性独立的向量.请记住，由于有多种产生列空间的方法，因此rref的解决方案将只为您提供一个这样的列空间.如果我正确地解释了您的问题，则希望生成随机的列空间，并每次都选择这些向量的一个子集.多亏了Luis Mendo(以及knedlsepp的出色产品)，您可以做的是随机重排或置换列，然后在此置换后的矩阵上运行rref.

Now, your next task is to randomly choose linearly independent vectors from this column space each time you run the algorithm. Bear in mind that because there are multiple ways to produce the column space, the solution by rref will only give you one such column space. If I am interpreting your question correctly, you wish to generate random column spaces and choose a subset of those vectors each time. Thanks to Luis Mendo (and also a gentle prod from knedlsepp), what you can do is randomly rearrange or permute the columns, then run rref on this permuted matrix.

这样，您可以执行以下操作:

As such, you can do something like this:

ind = randperm(size(V,2));
Vperm = V(:,ind);
[R,RB] = rref(Vperm);
VMax = Vperm(:,RB);

randperm 将从1开始生成随机排列数组指定给randperm的参数.在我们的例子中，这是矩阵V中的总列数.我们使用此数组随机地洗排V的列，将其存储到Vperm并运行我们之前完成的代码.通过执行随机混洗，您会将输入偏置为rref，从而迫使其选择不同的基向量，但是如果您有多个线性相关的向量，则在某些情况下，我们将选择其中的一个线性相关向量来建立我们的基础.

randperm will generate a random permutation array from 1 up to the argument that you specify to randperm. In our case, this is the total number of columns in your matrix V. We use this array to randomly shuffle the columns of V, store this into Vperm and run our code that we have done before. By doing this random shuffling, you are biasing the input to rref so that you are forcing it to choose different basis vectors, but if you have several vectors that are linearly dependent, there will be a case where we will choose one of these linearly dependent vectors to build our basis.

这篇关于从Matlab中的一组向量中提取最大的线性独立向量集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！