Approximation problems related to the mosaic-skeleton method and hierarchical matrices

Structures in matrices on the first place mean that all the entries are expressed through some few parameters. Examples are matrices with certain sparsity patterns, low-rank matrices, Toeplitz matrices, and many others. However, if only the entries are given, an expected structure might be not evident and need to be recovered.

In many situations, one may expect that a matrix A can be represented in the form A=T+R+E with E small in norm, R small in rank (or mosaic rank), and T belonging to some class of structured matrices (for example, Toeplitz matrices, circulants, an algebra of simultaneously diagonalizable matrices). However, since only A is given, there arises a problem of recovering T and R with a prescribed bound on the norm of E. We propose a sufficiently robust algorithm for this kind of problem.

More generally, T and R may belong to some classes of differently parametrized matrices assumed to approximate any matrix with a given accuracy, and now the problem is one of selecting those T and R that minimize the total number of parameters within the same approximation accuracy. Structures related to block mosaic and hierarchical partitioning of matrices are certainly of particular interest for BEM and FEM applications.