Jacob Sanders edited Compressibility.tex  over 9 years ago

Commit id: 25b058babad457bc44a5c20d8108a703a17362aa

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 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 isoften  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 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 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 to be zero or at least quite small.