Поиск максимального числа условий матрицы после стирания

Question

Я имею дело со следующим вопросом: если задана случайная гауссовская матрица большого размера, скажем, например, 1000 на 500. Затем произвольно удалите 500 строк и рассмотрите номер условия матрицы оставил. Какое максимально возможное число условий мы можем получить с высокой вероятностью?

Здесь гауссова матрица означает, что матрица имеет стандартные стандартные записи. Я хотел бы написать программу MATLAB для моделирования. Как я могу написать программу? Спасибо за любую помощь.

Answer 1

Это интересная проблема. Я не знаю никаких теоретических результатов, но легко настроить симуляцию Монте-Карло и посмотреть.

Обратите внимание, что произвольно удаления 500 строк эквивалентно всегда удаления последних 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.