Email this article On the existence of a close to optimal cross approximation in the Frobenius norm
- Authors: Osinskii A.I.1,2
-
Affiliations:
- Skolkovo Institute of Science and Technology, Moscow, Russia
- Marchuk Institute of Numerical Mathematics of the Russian Academy of Sciences, Moscow, Russia
- Issue: Vol 216, No 9 (2025)
- Pages: 69-85
- Section: Articles
- URL: https://journals.rcsi.science/0368-8666/article/view/309464
- DOI: https://doi.org/10.4213/sm10123
- ID: 309464
Cite item
Open Access
Access granted
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
- 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.
Supplementary files
