Jacob Sanders edited Compressibility.tex  over 9 years ago

Commit id: 88dfd8cac025385da6459355fa3a58265fce5532

deletions | additions      

       

The first step in our approach is to find a representation for the problem where the matrix to be calculated is expected to be sparse. In general, finding this \textit{sparsifying basis} is specific to each problem and ranges from trivial to quite complex; it has to do with the knowledge we have about the problem or what we expect about its solution.  Using additional information about a problem  is an essential concept in compressed sensing and it is intimately related to the concepts of sparsity and compressibility, but it is also a concept that is routinely used in numerical simulations. For example, in quantum chemistry it is customary to represent the orbitals of a molecule in a basis formed by the orbitals of the atoms in the molecule~\cite{Szabo1996}, which allows for an efficient and compact representation and a controlled discretization error. This choice comes from the notion that the electronic structure of the molecule is roughly described by ``patching together'' the electronic structure of the constituent atoms. An ideal basis in which to reconstruct a matrix is the basis of its eigenvectors, or \textit{eigenbasis}, as this basis only requires the evaluation of the diagonal elements to obtain the whole matrix. Of course, finding the eigenbasis requires knowing the matrix in the first place, so reconstructing a matrix in its eigenbasis is not useful for practical purposes. However, in many cases it is possible to obtain a set of reasonable approximations to the eigenvectors (an idea which also forms the basis of perturbation theory in quantum mechanics). The approximate eigenbasis probably constitutes a good sparsifying basis for many problems, as we expect the matrix to be diagonally dominant, with a large fraction of the off-diagonal elements equal to zero or at least quite small.