On the Existence of a Nearly Optimal Skeleton Approximation of a Matrix in the Frobenius Norm

N. L. Zamarashkina,b,c and A. I. Osinskya,c,*
Translated by I. Ruzanova

a Institute of Numerical Mathematics, Russian Academy of Sciences, Moscow, 119333 Russia

b Faculty of Computational Mathematics and Cybernetics, Moscow State University, Moscow, 119991 Russia

c Moscow Institute of Physics and Technology (State University), Dolgoprudnyi, Moscow oblast, 141700 Russia

Correspondence to: *e-mail: sasha_o@list.ru

Received 21 November, 2017

Abstract—For an arbitrary matrix, we prove the existence of a skeleton approximation of rank $r$ whose accuracy estimate is only $r + 1$ times worse than the estimate of the optimal approximation of rank r in the Frobenius norm.

DOI: 10.1134/S1064562418020205