О точности крестовых и столбцовых малоранговых MaxVol-приближений в среднем

В данной статье рассматривается проблема малорангового столбцового и крестового ($CGR$, $CUR$) приближения матриц по норме Фробениуса с точностью до фиксированного множителя $1+\varepsilon$. Доказывается, что для случайных матриц в среднем справедлива оценка вида $1+\varepsilon\le\frac{m+1}{m-r+1}\frac{n+1}{n-r+1}$, где $m$ и $n$ – число строк и столбцов крестового приближения. Таким образом, оказывается, что матрицы, для которых принцип максимального объема не позволяет гарантировать высокой точности, довольно редки. Также рассматривается связь полученных оценок с методами поиска подматрицы максимального объема и максимального проективного объема. Численные эксперименты показывают близость теоретических оценок и достижимых на практике результатов быстрой крестовой аппроксимации.
Библ. 16. Фиг. 1.