On the Best Approximation Algorithm by Low-Rank Matrices in Chebyshev’s Norm
Tóm tắt
The problem of approximation by low-rank matrices is found everywhere in computational mathematics. Traditionally, this problem is solved in the spectral or Frobenius norm, where the approximation efficiency is associated with the rate of decrease of the matrix singular values. However, recent results show that this requirement is not necessary in other norms. In this paper, a method for solving the problem of approximating by low-rank matrices in Chebyshev’s norm is proposed. It makes it possible to construct effective approximations of matrices for which singular values do not decrease in an acceptable amount time.
Tài liệu tham khảo
M. Bebendorf, “A means to efficiently solve elliptic boundary value problems,” Hierarchical Matrices, Lect. Notes Comput. Sci. 63, 49–98 (2008).
S. W. Son, Z. Chen, W. Hendrix, A. Agrawal, W. K. Liao, and A. Choudhary, “Data compression for the exascale computing era—survey,” Supercomput. Frontiers Innovations 1 (2), 76–88 (2014).
X. He, H. Zhang, M. Y. Kan, and T. S. Chua, “Fast matrix factorization for online recommendation with implicit feedback,” Proc. of the 39th Int. ACM SIGIR Conference on Research and Development in Information Retrieval, 2016, pp. 549–558.
C. Yang, Y. Akimoto, D. Kim, and M. Udell, “Oboe: Collaborative filtering for autoML initialization,” arXiv preprint arXiv:1808.03233. 2018.
S. Goreinov, E. Tyrtyshnikov, and N. Zamarashkin, “A theory of pseudoskeleton approximations,” Linear Algebra Appl. 261 (1), 1–21 (1997).
A. Osinsky and N. Zamarashkin, “Pseudo-skeleton approximations with better accuracy estimates,” Linear Algebra Appl. 537, 221–249 (2018).
P. M. N. Halko and J. Tropp, “Finding structures with randomness: Probabilistic algorithms for constructing approximate matrix decompositions,” SIAM Rev. 53 (2), 217–288 (2011).
M. Udell and A. Townsend, “Why are big data matrices approximately low rank?” SIAM J. Math. Data Sci. 1, 144–160 (2019).
V. Daugavet, “On a uniform approximation of a function of two variables specified in tabular form as a product of functions of one variable,” Zh. Vychisl. Mat. Mat. Fiz. 11 (2), 289–303 (1971).
V. K. Dzyadyk, Introduction to the Theory of Uniform Approximation of Functions by Polynomials (Nauka, Moscow, 1977) [in Russian].
V. I. Smirnov and N. A. Lebedev, Constructive Theory of a Complex Variable (Nauka, Moscow, 1964) [in Russian].
V. K. Dzyadyk, “On the approximation of functions on sets consisting of a finite number of points,” in Theory of Function Approximation and its Applications (Kiev, 1974), pp. 69–80.