How does compressed sensing alter this scaling?  From eq.~\ref{eq:csscaling}, the number of matrix elements needed to recover the Hessian via compressed sensing scales as \(O(S \log N)\), where \(S\) is number of non-zero elements in the Hessian, so the net scaling is \(O(S \log N) \times OE\).  However, by the Hellman-Feynman argument given above, it is possible to obtain the Hessian one column at a time (i.e. \(O(N)\) elements at a time), so the net scaling is reduced to \(O(S/N \log N) \times OE\).

This scaling result illustrates the critical importance of recovering the Hessian in a sparse basis, with \(S\) as small as possible.  The sparsest possible basis for the Hessian is its eigenbasis, with \(S = N\), but of course knowing the exact eigenbasis corresponds to already knowing the Hessian we are trying to find.  So what is the smallest \(S\) that can reasonably be achieved?

For many large systems, the Hessian is already sparse directly in the basis of atomic Cartesian coordinates.  Since the elements of the Hessian are \emph{partial} second derivatives of the energy with respect to the positions of two atoms, with the positions of all other atoms held fixed, the elements do not take into account interactions mediated by the movement of other atoms.  For most systems we expect that this direct interaction has a finite range or decays strongly with distance.   (Note that this does not preclude collective vibrational modes, which can still emerge when the Hessian is diagonalized as a result of "chaining together" direct interactions between nearby atoms.)  

If we assume that a system has a finite range interaction between atoms, and since each atom has an approximately constant number of neighbors, irrespective of the total number of atoms in the molecule, the number of non-zero elements in a single column of the Hessian is constant.  Hence, for large molecules, the sparsity \(S\) of the Hessian scales linearly with the number of atoms \(N\).  Putting this result into  \(O(S/N \log N) \times OE\) yields a best-case final scaling result of \(O\left(\log N \right)\times OE\), which is a significant improvement over the original \(O(N)\times OE\) in the absence of compressed sensing.  \textbf{However, we should note that eq.~\ref{eq:csscaling} is only valid for a random
sampling, and it is not necessarily valid for a column sampling.}

To study the validity of our scaling results we have performed numerical calculations on a series of molecules known as polyacenes, which are aromatic compounds made of linearly fused benzene rings.  For polyacenes ranging from 1 to 15 rings, Fig.~\ref{fig:HessSparsity} illustrates the average number of non-zeros per column in the Hessian matrices obtained via molecular mechanics and quantum mechanical calculations in the basis of atomic coordinates.  In the molecular mechanics Hessians, the average sparsity per column approaches a constant value as the size of the polyacene increases, consistent with each atom having a roughly constant number of other atoms close enough for direct interaction.  (In fact, in molecular mechanics, the interaction energy for two atoms beyond a certain cut-off radius is set to zero.)