Pseudo-skeleton approximations by matrices of maximal volume (Q1277563)

Assume that the matrices \(A_n\) are generated by the formula \(A_n= [f(x_i, y_j)]^n_{i,j=1}\), where \(x_i\), \(y_j\) are nodes of a (quasi-uniform) grid on a bounded domain of Euclidean space \(\mathbb{R}^d\). In this case, for the class of the so-called asymptotically smooth functions \(f\), it is possible to indicate a method for partitioning the points \(x_i\) and \(y_j\) into groups that lead to the decomposition of the matrix into blocks of small \(\varepsilon\)-rank, the complexity of the multiplication by the resultant approximant of the entire matrix \(A_n\) is \(O(n\log n\log^d\varepsilon^{-1})\). In more detail, if the \(\varepsilon\)-rank of the matrix \(A\in \mathbb{R}^{n\times n}\) is at most \(k\), then \(A\) contains \(k\) columns \(C\in\mathbb{R}^{n\times k}\) and \(k\) rows \(R\in \mathbb{R}^{k\times n}\) such that \[ \| A- CGR\|_2\leq \varphi(k, n)\varepsilon,\tag{1} \] where \(G\in\mathbb{R}^{k\times k}\) is determined by \(C\) and \(R\), and the function \(\varphi\) is bounded above by a polynomial of small degree. In the present note, we prove estimates of type (1) for the rows and columns whose intersections give a submatrix with the following extremal property: among all submatrices in the matrix \(A\) of size \(k\times k\), this submatrix has determinant with maximal modulus. In other words, to obtain ``good'' rows and columns, it suffices to choose a submatrix of maximal ``volume'' (or a submatrix that nearly has this property).