  Quasi-Newton methods refer to a class of algorithms at the interface between
first and second order methods. They aim to progress as substantially as second
order methods per iteration, while maintaining the computational complexity of
first order methods. The approximation of second order information by first
order derivatives can be expressed as adopting a variable metric, which for
(limited memory) quasi-Newton methods is of type ``identity $\pm$ low rank''.
This paper continues the effort to make these powerful methods available for
non-smooth systems occurring, for example, in large scale Machine Learning
applications by exploiting this special structure. We develop a line search
variant of a recently introduced quasi-Newton primal-dual algorithm, which adds
significant flexibility, admits larger steps per iteration, and circumvents the
complicated precalculation of a certain operator norm. We prove convergence,
including convergence rates, for our proposed method and outperform related
algorithms in a large scale image deblurring application.
