Any Precondition for the slow decay singular value??

3 ビュー (過去 30 日間)
Ching-Te Lin
Ching-Te Lin 2020 年 10 月 12 日
コメント済み: Bjorn Gustavsson 2023 年 4 月 11 日
First, my problem is that I have to solve a linear system Ax=b. I try to use randomized Tikhonov regularization method, like this paper
However, I found my target A matrix has a slow-decaying singular value. Just like the picture show below
[the left is one of the matrix from the paper, and the right one is what I should deal with.]
According to the error analysis in the paper, the error of the solution is depending on the singular value decay rate of matrix A.
I would like to know is any precondition method for such slow-decaying singular value?
Or does anyone know any randomized method to solve this kind of linear system?
Thx

採用された回答

Bjorn Gustavsson
Bjorn Gustavsson 2020 年 10 月 12 日
Unfortunately I could not access the paper. However, I'll offer my opinion anyway. Once you've calculated your SVD-decomposition the Tikhonov-regularization is perfectly trivial, and I have no idea how it could be improved by some randomization of anything.
Once you have your U, S and V the solution to your equation Ax = b is simply:
lamda = diag(S);
alpha = 1; % This is the crucial step! (*)
invZ = diag(lambda./(lambda.^2+alpha^2));
x_hat = V(:,1:size(iS,1))*(invZ*(U'*b));
There's a lot more to say for the selection of alpha. A lot more, and discussions to be had about the merits of my choise compared to the choise of others.
You can have a couple of different approaches to how to select alpha - I have always worked with problems where I've had a reasonably good knowledge about the statistics of the measurements in b, that is I know the "noise"-disribution of my measurements in the b I have compared to an ideal noise-free measurement. For that case I can look at x_hat as an estimate of an ideal x from which my b is one stochastical realization of the measurements. That measured b should have some random variations relative to an ideal noise-free measurement b_ideal that are consistent with the known noise-distribution. If for example the noise-distribution should be N(0,3) then I can check the distribution of b - b_ideal if it is too narrow, let say approximately N(0,1) then I know the residuals are too small which means that the choise of alpha is too small, the measurements are too close to the solution and x_hat is overfitted, if the distribution is too wide I know alpha is too large for the same type of reasoning as above. There will be a range of alpha for which the distribution of the residuals (or whatever you have to do to get the proper comparison in terms of weighting etc) are equally good. Which alpha to select from that range is a question of preferences (perhaps?), some might prefer the largest alpha since that gives the simplest solution x_hat (in some sense of simplest), others might prefer the smallest alpha because that is the smallest damping of the measurements in b. Depending on mood I might chose one or the other with rather equal conviction...
For the case where you don't really know anything about the statistical properties of b then you might proceed as above and make some post-hoc justification of a choise of alpha based on what the distribution of the b-residuals look like and chose one where it looks most normal-distributed with the justification that "errors should be normal-distributed, right?". Or you could make some other selection based on any of the other criteria around, L-curve etc...
HTH
  6 件のコメント
Phillip
Phillip 2023 年 4 月 7 日
Thanks very much for these references. regtools in particular looks amazing!
Bjorn Gustavsson
Bjorn Gustavsson 2023 年 4 月 11 日
@Phillip: Happy to share! Regtools is indeed amazing!

サインインしてコメントする。

その他の回答 (0 件)

カテゴリ

Help Center および File ExchangeMathematics and Optimization についてさらに検索

Community Treasure Hunt

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

Start Hunting!

Translated by