On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Understand

The problem of finding a $k \times k$ submatrix of maximum volume of a matrix $A$ is of interest in a variety of applications.

• For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of $A$.
• We show that such a submatrix can always be chosen to be a principal submatrix if $A$ is symmetric semidefinite or diagonally dominant.
• Then we analyze the low-rank approximation error returned by a greedy method for volume maximization, cross approximation with complete pivoting.