Searching for Strongly Non-Degenerate Submatrices and Their Connection to Column and Cross Approximations

Cross approximations of matrices are constructed based on a small number of rows and columns of the target matrix. Consequently, their accuracy is closely related to the properties of the submatrix at the intersection of the selected rows and columns. To achieve approximations accuracy close to the error of reduced singular value decomposition, it is necessary to select strongly non-degenerate submatrices: those with small norms of pseudo-inverses according to the spectral norm or Frobenius norm. The presentation will discuss several algorithms for selecting such submatrices, including those based on the principle of maximum volume, and estimates of their computational complexity will be proven.