While the recovery of molecular mechanics Hessians provides a clear illustration of the scaling of our compressed sensing procedure, molecular mechanics matrix elements are not expensive to compute in comparison with rest of the linear algebra operations required to diagonalize the Hessian.  Hence, from a computational standpoint, the real challenge is to apply our procedure to the computation of quantum mechanical Hessians.

As Fig.~\ref{fig:HessSparsity} shows the sparsity \(S\) of a quantum mechanical Hessian does not necessarily scale linearly with the number of atoms \(N\) in the molecule.  Fig.~\ref{fig:NColumnsVsNRings} illustrates the cost of recovering the quantum mechanical Hessians of polyacenes using compressed sensing in a variety of sparse bases. Recovering the Hessian in the atomic coordinate basis already provides a considerable computational advantage over directly computing the entire Hessian. In fact, this curve mirrors the sparsity per column curve for quantum mechanical Hessians in Fig.~\ref{fig:HessSparsity}, consistent with our prediction that the number of sampled columns scales as \(O(S/N \log N) \times OE\).  More significantly, recovering the quantum mechanical Hessian in the molecular mechanics basis provides a substantial advantage over recovery in the atomic coordinates basis, reducing the number of columns which must be sampled approximately by a factor of two.  This is consistent with the quantum mechanical Hessian being considerably sparser in the approximate eigenbasis of molecular mechanics normal modes. Of course, nothing beats recovery in the exact eigenbasis, which is as sparse as possible, but which requires knowing the exact Hessian in the first place. 

In short, the take-home message of Fig.~\ref{fig:NColumnsVsNRings} is that using compressed sensing to recover a quantum mechanical Hessian in its basis of molecular mechanics normal modes is a practical procedure which substantially reduces the computational cost of the procedure.