SVD to a matrix subset (rows)
6 次查看(过去 30 天)
显示 更早的评论
Hello everyone
I have a quite large matrix A (MxN with M>N) and a for cycle of many (tens of thousands) iterations where, for each iteration, I have to exclude some rows of the matrix A and perform a single value decomposition of it.
Something like
for n = 1:NLoops
[U,S,V] = svd( A(rows_selection(n,:),:) );
% Do stuff with U, S and V...
end
where rows_selection is a logical matrix that select the rows to be analyzed for each loop.
Since this code happens to be really slow, is it possible to calculate [U,S,V] = svd(A) before the for cycle and then arrange the U, S and V matrices based on the particular rows to be selected for each for loop?
0 个评论
回答(2 个)
John D'Errico
2025-9-5
编辑:John D'Errico
2025-9-7
No, I don't think you can easily find the SVD of a subset of the rows of a matrix, based on the SVD of the full matrix. At least, not easily. (@Christine Tobler) may have an idea.
But whenever I see a question like this, I wonder if the real problem is, you are trying to solve the wrong problem. That is, one reason for computing the SVD repeatedly may be to find the numerical rank of each subset of the rows. Or maybe you want to find the subset of rows that are maximally independent from each other. And if you are doing something like one of these things, there are likely better ways of doing so than repeat calls to SVD.
It is often the case that someone asks a question, looking to make the scheme they have run faster, but the real issue is, you need to improve the approach you are taking. Find a better way of solving the problem than what you are doing.
Edit:
For example, if your goal is to find the subset of k rows of your matrix, such that the condition number of the resulting matrix is as small as possible, when you extract that set of rows and then compute the condition number on that subset? Now, rather than computing cond on EVERY subset of rows, I might try using GA. Have GA select the subset, with minimal condition number. Will this really gain? Well, yes. Consider this example:
A = rand(1e6,10);
Now, my goal is to find the subset of 10 rows from all 1e6 rows, such that the condition number is as small as possible. It might be a moderately interesting problem (though I have no idea if it is your real problem.) Were we to apply brute force, that would necessitate MATLAB to compute
nchoosek(1e6,10)
calls to COND (which calls SVD). And clearly that would be an insane thing to do. But we could use GA instead, to identify a subset of those rows, with a minimal condition number. Yes, GA might not find the perfectly optimal solution, but it would be massively better than anything you could do using brute force, and the result would take only some thousands of calls to COND. Even if it was many thousands of calls, you win by use of an optimization tool here.
Agin, I have no clue as to why you have decided to perform this programming task. Maybe someone told you to do it this way, or maybe you decided it was the way to solve some problem. But that does not make necessarily a good way to approach the real underlying problem. We don't know, because all we see is the final question that you think to be important.
3 个评论
Steven Lord
2025-9-11
What are the values of M and N for the problem you're considering? Knowing how big a problem you're trying to solve may help us more easily assess if any approaches we are about to suggest are feasible; possible but going to take a very, very long time; or not possible in the lifetime of this universe.
Chuguang Pan
2025-9-5
I find there is a svdappend function for calculating SVD of matrix incrementally, such as from SVD of A to SVD of [A,D] or [A;D], without explicitly forming full matrix [A,D] or [A;D]. However, the for loop of your requirement is not appending rows, maybe the logical selection of different rows can be transformed into appending form so that the svdappend function is useful.
1 个评论
Torsten
2025-9-7
The existence of "svdappend" seems to indicate that there exist at least techniques for "updating" or "downdating" an SVD when adding/removing columns. Thus a completely new SVD doesn't seem necessary in this case.
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!