\section{Conclusions}

We have presented a new approach for calculating matrices. This method is suitable for applications where the cost of computing each matrix element is high in comparison to the cost of linear algebra operations.  Our approach leverages the power of compressed sensing to avoid individually computing every matrix element, thereby achieving substantial computational savings. 

When applied to molecular vibrations of organic molecules, our method results in accurate frequencies and normal modes with about 30\% of the expensive quantum mechanical computations usually required, which represents a quite significant 3\(\times\) speed-up. Depending on the sparsity of the Hessian, our method can also improve the overall scaling of the computation. These computational savings could be further improved by using more sophisticated compressed sensing approaches, such as recovery algorithms based on belief propagation\cite{Krzakala_2012a,Krzakala_2012b} which offer a recovery cost directly proportional to the sparsity of the signal, and which could be easily integrated into our approach.

Our method could also be applied to other common calculations in computational chemistry, including the Fock matrix in electronic structure or the Casida matrix in linear-response time-dependent DFT~\cite{TDDFT2012}. Nevertheless, our method is not restricted to quantum chemistry and is applicable to many problems throughout the physical sciences and beyond. The main requirement is an \emph{a priori} guess of a basis in which the matrix to be computed is sparse.  The optimal way to achieve this requirement is problem-dependent, but as research into sparsifying transformations continues to develop, we believe our method will enable considerable computational savings in a wide array of scientific fields.

In fact, a recent area of interest in compressed sensing is the development of dictionary learning methods that do not directly require knowledge of a sparsifying basis, but instead generate it on-the-fly based on the problem~\cite{Aharon_2006,Rubinstein_2010}.  We believe that combining our matrix recovery protocol with state-of-the-art dictionary learning methods may eventually result in further progress towards the calculation of scientific matrices.

Beyond the specific problem of computing matrices, this work demonstrates that compressed sensing can be integrated into the core of computational simulations as a workhorse to reduce numerical costs by optimizing the information obtained from each computation.

Finally, we introduced an effective method of bootstraping low-accuracy calculations to reduce the number of high-accuracy calculations that need to be done, something which is not simple to do in quantum chemical calculations. In this new paradigm, the role of expensive high-accuracy methods is to correct the low-accuracy results, with a cost proportional to the magnitude of the required correction, rather than recalculating the results from scratch.