擦除后查找矩阵的最大条件数

Question

我正在处理以下问题：给定一个大尺寸的随机高斯矩阵，例如 1000 x 500。然后任意删除 500 行并考虑矩阵剩余的条件数。我们可以高概率得到的最大可能条件数是多少？

这里的高斯矩阵意味着矩阵有i.i.d个标准正态项。我想写一个 MATLAB 程序来做一些模拟。我该如何编写程序？感谢您的帮助。

Answer 1

这是一个有趣的问题。我不知道任何理论结果，但是很容易设置 Monte Carlo 模拟并查看。

请注意，任意删除 500 行等同于始终删除 last 500 行，例如，因为这些行是 i.i.d.并且条件数对于更改行的顺序是不变的。

M = 100; %// initial number of rows
N = 50; %// number of columns
R = 1e4; %// number of Monte Carlo realizations
cond1 = NaN(1,R); %// preallocate
cond2 = NaN(1,R); %// preallocate
for r = 1:R
    X = randn(M,N); %// matrix with i.i.d normalized Gaussian entries
    cond1(r) = cond(X);
    cond2(r) = cond(X(1:N,:));
end
loglog(cond1, cond2, '.', 'markersize', 1) %// scatter plot of results in logarithmic scale
xlabel('Condition number of original matrix')
ylabel('Condition number of reduced matrix')

这是 M=100; N=50; 的结果。请注意，对于M=100; N=50;，可能需要很长时间才能获得大量实现。

正如预期的那样，当您删除行时条件数会增加（尽管我没想到会增加这么多！）。

根据获得的向量 cond1 和 cond2，您可以计算统计数据或百分位数。例如，在每种情况下，仅以 10% 的概率超出的值是

>> quantile(cond1,.9)
ans =
   5.837510220358853
>> quantile(cond2,.9)
ans =
     9.422516183444204e+02

这意味着在原始矩阵中，90%的情况下条件数小于5.8375；而在简化矩阵中，90% 的情况下条件数小于 942.25.

擦除后查找矩阵的最大条件数

Finding the maximum condition number of a matrix after erasure

matlab

matrix

linear-algebra

gaussian

numerical-methods