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

A. I. Osinsky<sup>ab

a</sup> Skolkovo Institute of Science and Technology, Moscow, Russia
^b Marchuk Institute of Numerical Mathematics of the Russian Academy of Sciences, Moscow, Russia

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.
Bibliography: 14 titles.

Keywords: low-rank matrix approximation, column approximation, cross approximation.

MSC: 15A23, 15A45, 65F55 , 68W25

Received: 21.05.2024 and 27.03.2025

DOI: 10.4213/sm10123

 English version: Sbornik: Mathematics, 2025, 216:9, 1255–1271

Bibliographic databases:

• 
• 
• 
•