Approximation of the matrix with positive elements by the single rank matrix

A. V. Panyukov ; Kh. Z. Chaloob ; Ya. A. Mezaal

Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematika, mehanika, fizika, Tome 10 (2018) no. 2, pp. 28-36

Résumé

Most of the modern mathematical methods for solving problems of science, technology, and economics require the solution of linear problems of large dimension. To reduce the computational complexity, a special structure of matrices corresponding to these problems is used. Block-low-rank matrices represent the approximation with good accuracy of dense matrices in a low-parametric format. Blocks of small rank are represented as a product of matrices of smaller sizes. This allows you to significantly save computer memory. Approximate factorization methods for block-low-rank matrices can be used for approximate solution and preconditioning of systems with dense matrices in aero-, hydro- and electrodynamics problems, as well as in applied statistics and logistics. To build low-parametric representations of matrices based on small-rank approximations of individual blocks, algebraic methods are widely used. In this paper we consider an effective method for approximating blocks of a matrix with positive elements by a single rank matrix, i.e. in the form of a product of a column per line. The solution of the problem is sought among the admissible representations that minimize the average modulus of the logarithms of the ratio of an approximate representation of an element to the exact value. The approximating problem is reduced to the problem of linear programming, for which the dual problem is the task of building a circulation of the minimum value in a complete bipartite graph with the throughputs of all arcs equal to one. To solve this problem, we propose an algorithm that has a computational complexity of at most of $O(|I|\cdot|J|\cdot\log(|I|\cdot|J|))$, where $I$ is the set of rows in the block, and $J$ is the set of columns to the block.

Détail

Mots-clés : matrix
Keywords: low-rank approximation, linear programming, algorithm, computational complexity.