SVD to a matrix subset (rows)

6 次查看(过去 30 天)
Davide Cataldo
Davide Cataldo 2025-9-5
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?

回答(2 个)

John D'Errico
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)
Warning: Result may not be exact. Coefficient has a maximum relative error of 3.5527e-15, corresponding to absolute error 9.789885939637849e+38.
ans = 2.7556e+53
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 个评论
Davide Cataldo
Davide Cataldo 2025-9-11
Thank you for your time John.
What I am trying to do is implementing an algorithm for radar interferometry application (phase unwrapping algorithm from "Monserrat, O.. (2012). Deformation measurement and monitoring with GB-SAR." if you are interested).
In short,
1) I perform a least square estimation (the paper proposes SVD-LS estimation) of N variables from M>N observations.
2) Calculate the residuals between estimations and observations.
3) Perform SVD-LS estimation again without considering those observations for which the residuals exceed a threshold (thus, removing some rows from the matrix A).
4) Calculate the residuals again.
5) Evaluate which observations (those that were excluded at step 3) are to be definitively excluded, can be corrected or reintegrated.
6) Repeat untill all (or enough) residuals remain within the threshold.
7) Repeat for all the pixels of interest in the image under test.
TLDR: I have to perform a least square estimation using the entire matrix A first and then, iteratively, remove rows from the matrix (and perform LS estimation again) untill I find the optimal set of observations (subset of rows).
Another option was to use the lsqminnorm Matlab function, which is slightly faster than the LS estimation using the SVD.
Steven Lord
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
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
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.

请先登录,再进行评论。

类别

Help CenterFile Exchange 中查找有关 Linear Algebra 的更多信息

标签

产品


版本

R2024b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by