  Obtaining lightweight and accurate approximations of Hessian applies in
inverse problems governed by partial differential equations (PDEs) is an
essential task to make both deterministic and Bayesian statistical large-scale
inverse problems computationally tractable. The $\mathcal{O}(N^{3})$
computational complexity of dense linear algebraic routines such as that needed
for sampling from Gaussian proposal distributions and Newton solves by direct
linear methods, can be reduced to log-linear complexity by utilizing
hierarchical off-diagonal low-rank (HODLR) matrix approximations. In this work,
we show that a class of Hessians that arise from inverse problems governed by
PDEs are well approximated by the HODLR matrix format. In particular, we study
inverse problems governed by PDEs that model the instantaneous viscous flow of
ice sheets. In these problems, we seek a spatially distributed basal sliding
parameter field such that the flow predicted by the ice sheet model is
consistent with ice sheet surface velocity observations. We demonstrate the use
of HODLR approximation by efficiently generating Hessian approximations that
allow fast generation of samples from a Gaussianized posterior proposal
distribution. Computational studies are performed which illustrate ice sheet
problem regimes for which the Gauss-Newton data-misfit Hessian is more
efficiently approximated by the HODLR matrix format than the low-rank (LR)
format. We then demonstrate that HODLR approximations can be favorable, when
compared to global low-rank approximations, for large-scale problems by
studying the data-misfit Hessian associated to inverse problems governed by the
Stokes flow model on the Humboldt glacier and Greenland ice sheets.
