Отправить статью по E-mail О существовании близкой к оптимальной крестовой аппроксимации в норме Фробениуса
- Авторы: Осинский А.И.1,2
-
Учреждения:
- Сколковский институт науки и технологий, г. Москва
- Институт вычислительной математики им. Г. И. Марчука Российской академии наук, г. Москва
- Выпуск: Том 216, № 9 (2025)
- Страницы: 69-85
- Раздел: Статьи
- URL: https://journals.rcsi.science/0368-8666/article/view/309464
- DOI: https://doi.org/10.4213/sm10123
- ID: 309464
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Доказано, что для любой матрицы существует крестовая (псевдоскелетная) аппроксимация на основе $n$ строк и $n$ столбцов, погрешность которой по норме Фробениуса выше наилучшей возможной аппроксимации того же ранга не более чем в $1+{r}/{n}+o (n^{-1})$ раз, где $r$ – ранг крестовой аппроксимации.Библиография: 14 названий.
Об авторах
Александр Игоревич Осинский
Сколковский институт науки и технологий, г. Москва; Институт вычислительной математики им. Г. И. Марчука Российской академии наук, г. Москва
Автор, ответственный за переписку.
Email: a.osinskiy@skoltech.ru
кандидат физико-математических наук
Список литературы
- A. I. Osinsky, “Lower bounds for column matrix approximations”, Ж. вычисл. матем. и матем. физ., 63:11 (2023), 1816
- A. Deshpande, S. Vempala, “Adaptive sampling and fast low-rank matrix approximation”, Approximation, randomization and combinatorial optimization, Lecture Notes in Comput. Sci., 4110, Springer-Verlag, Berlin, 2006, 292–303
- V. Guruswami, A. K. Sinop, Optimal column-based low-rank matrix reconstruction, 2012
- A. Deshpande, L. Rademacher, S. S. Vempala, G. Wang, “Matrix approximation and projective clustering via volume sampling”, Theory Comput., 2 (2006), 225–247
- C. Boutsidis, P. Drineas, M. Magdon-Ismail, “Near-optimal column-based matrix reconstruction”, 2011 IEEE 52nd annual symposium on foundations of computer science (Palm Springs, CA), IEEE Comput. Soc., Los Alamitos, CA, 2011, 305–314
- A. I. Osinsky, N. L. Zamarashkin, “Pseudo-skeleton approximations with better accuracy estimates”, Linear Algebra Appl., 537 (2018), 221–249
- Н. Л. Замарашкин, А. И. Осинский, “О точности крестовых и столбцовых малоранговых MaxVol-приближений в среднем”, Ж. вычисл. матем. и матем. физ., 61:5 (2021), 813–826
- E. Tyrtyshnikov, “Incomplete cross approximation in the mosaic-skeleton method”, Computing, 64:4 (2000), 367–380
- M. Bebendorf, S. Rjasanow, “Adaptive low-rank approximation of collocation matrices”, Computing, 70:1 (2003), 1–24
- S. A. Goreinov, I. V. Oseledets, D. V. Savostyanov, E. E. Tyrtyshnikov, N. L. Zamarashkin, “How to find a good submatrix”, Matrix methods: theory, algorithms and applications, World Sci. Publ., Hackensack, NJ, 2010, 247–256
- A. Michalev, I. V. Oseledets, “Rectangular maximum-volume submatrices and their applications”, Linear Algebra Appl., 538 (2018), 187–211
- A. Osinsky, “Volume-based subset selection”, Numer. Linear Algebra Appl., 31:1 (2024), e2525, 14 pp.
- C. Boutsidis, D. P. Woodruff, “Optimal CUR matrix decompositions”, STOC'14: Proceedings of the 46th annual ACM symposium on theory of computing, ACM Press, New York, 2014, 353–362
- Shusen Wang, Luo Luo, Zhihua Zhang, “SPSD matrix approximation vis column selection: theories, algorithms, and extensions”, J. Mach. Learn. Res. (JMLR), 17 (2016), 49, 49 pp.
Дополнительные файлы
