Nonlinear growth of the $l_\infty$-norm of matrices for maximal cross approximation

S. S. Fedorovskii<sup>ab

a</sup> Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia
^b Moscow Center of Fundamental and Applied Mathematics, Moscow, Russia

Abstract: For the function $g(n)$ describing the maximal possible growth of the $l_\infty$-norms of maximal cross approximations of an $n \times n$ matrix, the inequality $4g(2k)\leqslant g(7k+3)$ is proved. This inequality implies the bound $g(n) \geqslant Cn^{\log_{7/2}4}$.
Bibliography: 8 titles.

Keywords: matrix, $l_\infty$-norm, cross approximation.

MSC: 15A23, 65F05

Received: 29.04.2025 and 15.07.2025

DOI: 10.4213/sm10338

 English version: Sbornik: Mathematics, 2025, 216:10, 1483–1492

Bibliographic databases:

• 
• 
• 
•