Default rank revealing tolerance

14 views (last 30 days)
Bruno Luong
Bruno Luong on 16 Feb 2024
Commented: Paul on 17 Feb 2024
In few MATLAB functions such as RANK, PINV, ORTH there is a parameter TOL.
MATLAB uses the default value as
% tol = max(size(A)) * eps(norm(A))
where A the matrix under study.
I have two quetions:
First question: what is the theoretical basis of such formula? Especially why the max(size(A)) factor?
In my simple test here, it seems the error or the singular value grows like a square root of the dimension m. Here is the script to create a matrix A of size m x 4 of rank 3. I use SVD to compute the singulars values, s(4) ideally should be 0, s1(1:3) about unity, but I see experimentally s(4) grow like sqrt(m) as showed in this script:
m0 = 1e5;
s4 = [];
m = [];
while m0 < 1e8
[Q, ~] =qr(rand(m0,3),0);
X = rand(3,4);
A = Q * X;
[~,s,~] = svd(A,0,'vector');
s4(end+1) = s(4);
m(end+1) = m0;
m0 = ceil(m0*1.1);
end
P = polyfit(log(m),log(s4),1);
p = P(1);
c=exp(P(2));
figure
loglog(m, s4);
hold on
h = loglog(m, c*m.^p);
xlabel('m')
ylabel('s(4)')
legend(h, sprintf('%g*m^{%g}', c, p))
PS: There is a floor noise about 1e-16 for m < 1e5, that could affect the fit, so I take the m value above 1e5 up to 1e8 .
Intuitively the square-root relationship seems reasonable to me since we could consider truncation errors in each component are somewhat random and independent.
Second question. The function lsqminnorm also have a default tol but is it NOT specified beside telling it computed from QR decomposition. It describes how the rank k is used to approximate the solution, but I don't see how the tol value is defined to estimate in turn the rank k. I would expect something like
% tol = eps(abs(R(1,1))) * max(size(A));
where R is the triangular matrix returned by qr, meaning abs(R(1,1)) = max(vecnorm(A)).
Can someone (TMW staff) shed a light and give the method to determine the default tol value implemented within lsqminnorm?
  8 Comments
Paul
Paul on 17 Feb 2024
Thanks for the links. I checked the LINPACK User's Guide from siam.org and I didn't see the TMW formula in Chapter 11, Section 1 (at least not explicitly).

Sign in to comment.

Answers (0)

Categories

Find more on Linear Algebra in Help Center and File Exchange

Products


Release

R2023b

Community Treasure Hunt

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

Start Hunting!