Поиск сильно невырожденных подматриц и их связь со столбцовыми и крестовыми аппроксимациями

Крестовые аппроксимации матриц по определению строятся на основе небольшого числа строк и столбцов приближаемой матрицы. Как следствие, их точность оказывается тесно связана со свойствами подматрицы на пересечении выбранных строк и столбцов. Для достижения точности аппроксимаций, близких к погрешности сокращенного сингулярного разложения, оказывается необходимым выбор сильно невырожденных подматриц: обладающих малой нормой псевдообратных по спектральной норме или норме Фробениуса. В докладе будут рассмотрены несколько алгоритмов выбора таких подматриц, в том числе основанных на принципе максимального объема, и доказаны оценки на их вычислительную сложность.