On the existence of a close to optimal cross approximation in the Frobenius norm

Cover Page

Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

Abstract

We prove that for any matrix, there exists a cross (pseudoskeleton) approximation based on $n$ rows and $n$ columns whose error in the Frobenius norm differs from that of the best possible approximation of the same rank by a factor of at most $1+r/n+o (n^{-1})$, where $r$ is the rank of the cross approximation.

About the authors

Aleksandr Igorevich Osinskii

Skolkovo Institute of Science and Technology, Moscow, Russia; Marchuk Institute of Numerical Mathematics of the Russian Academy of Sciences, Moscow, Russia

Author for correspondence.
Email: a.osinskiy@skoltech.ru
Candidate of physico-mathematical sciences

References

  1. A. I. Osinsky, “Lower bounds for column matrix approximations”, Ж. вычисл. матем. и матем. физ., 63:11 (2023), 1816
  2. 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
  3. V. Guruswami, A. K. Sinop, Optimal column-based low-rank matrix reconstruction, 2012
  4. A. Deshpande, L. Rademacher, S. S. Vempala, G. Wang, “Matrix approximation and projective clustering via volume sampling”, Theory Comput., 2 (2006), 225–247
  5. 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
  6. A. I. Osinsky, N. L. Zamarashkin, “Pseudo-skeleton approximations with better accuracy estimates”, Linear Algebra Appl., 537 (2018), 221–249
  7. Н. Л. Замарашкин, А. И. Осинский, “О точности крестовых и столбцовых малоранговых MaxVol-приближений в среднем”, Ж. вычисл. матем. и матем. физ., 61:5 (2021), 813–826
  8. E. Tyrtyshnikov, “Incomplete cross approximation in the mosaic-skeleton method”, Computing, 64:4 (2000), 367–380
  9. M. Bebendorf, S. Rjasanow, “Adaptive low-rank approximation of collocation matrices”, Computing, 70:1 (2003), 1–24
  10. 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
  11. A. Michalev, I. V. Oseledets, “Rectangular maximum-volume submatrices and their applications”, Linear Algebra Appl., 538 (2018), 187–211
  12. A. Osinsky, “Volume-based subset selection”, Numer. Linear Algebra Appl., 31:1 (2024), e2525, 14 pp.
  13. 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
  14. 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.

Supplementary files

Supplementary Files
Action
1. JATS XML

Copyright (c) 2025 Osinskii A.I.

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».