  This paper proposes a novel class of block quasi-Newton methods for convex
optimization which we call symmetric rank-$k$ (SR-$k$) methods. Each iteration
of SR-$k$ incorporates the curvature information with~$k$ Hessian-vector
products achieved from the greedy or random strategy. We prove that SR-$k$
methods have the local superlinear convergence rate of
$\mathcal{O}\big((1-k/d)^{t(t-1)/2}\big)$ for minimizing smooth and strongly
convex function, where $d$ is the problem dimension and $t$ is the iteration
counter. This is the first explicit superlinear convergence rate for block
quasi-Newton methods, and it successfully explains why block quasi-Newton
methods converge faster than ordinary quasi-Newton methods in practice. We also
leverage the idea of SR-$k$ methods to study the block BFGS and block DFP
methods, showing their superior convergence rates.
