A theory of pseudoskeleton approximations

Let an m x n matrix A be approximated by a rank-r matrix with an accuracy epsilon. We prove that it is possible to choose r columns and r rows of A forming a so-called pseudoskeleton component which approximates A with O(epsilon root r(root m + root n)) accuracy in the sense of the 2-norm. On the way to this estimate we study the interconnection between the volume (i.e., the determinant in the absolute value) and the minimal singular value sigma(r) of r x r submatrices of an n x r matrix with orthogonal columns. We propose a lower bound (better than one given by Chandrasekaram and Ipsen and by Hong and Pan) for the maximum of sigma(r) over all these submatrices and formulate a hypothesis on a tighter bound. (C) Elsevier Science Inc., 1997.