\section{Finding a sparse description of the problem}

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.

Leveraging additional information about a problem is an essential concept in compressed sensing, but it is also a concept that is routinely exploited 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.

Since the determination of an approximate eigenbasis depends on the specific problem at hand, a general prescription is difficult to give.  Nevertheless, a few general ideas could work in many situations.  For example, in iterative or propagative simulations, results from previous iterations or steps could be used to generate a guess for the next step.  Alternatively, cheap low-accuracy methods can be used to generate a guess for an approximate eigenbasis.  In this case, the procedure we propose provides a framework for bootstraping the results of a low-cost calculation in order to reduce the required number of costly high-accuracy calculations. This last strategy is the one we apply to the case of molecular vibrations.

What makes looking for sparsifying basis attractive, even at some computational cost and code-complexity overhead, are the properties of the recovery method.  First, the cost of recovering the matrix is roughly proportional to its sparsity.  Second, the reconstruction of the matrix is always exact up to a desired precision; even if the sparsifying basis is not a good one, we eventually converge to the correct result.  The penalty for a bad sparsifying basis is additional computation, which in the worst case makes the calculation as costly as if compressed sensing were not used at all.  This feature implies that the method will almost certainly offer some performance gain.

There is one important qualification to this performance gain. For some matrices, there is a preferred basis in which the matrix is cheaper to compute, and the extra cost of computing its elements in a different basis might offset the reduction in cost offered by compressed sensing.

%There are serveral peculiarities to our approach. While in general the additional knowledge %about the problem must be integrated a priori while designing the simulation strategy, our %approach is general and can

%The properties of the method: no need to know the location of the non-zero elements, quasi%-linear scaling with the matrix sparsity and exact recovery, make it practical to use