  Knowledge distillation is an effective way for model compression in deep
learning. Given a large model (i.e., teacher model), it aims to improve the
performance of a compact model (i.e., student model) by transferring the
information from the teacher. Various information for distillation has been
studied. Recently, a number of works propose to transfer the pairwise
similarity between examples to distill relative information. However, most of
efforts are devoted to developing different similarity measurements, while only
a small matrix consisting of examples within a mini-batch is transferred at
each iteration that can be inefficient for optimizing the pairwise similarity
over the whole data set. In this work, we aim to transfer the full similarity
matrix effectively. The main challenge is from the size of the full matrix that
is quadratic to the number of examples. To address the challenge, we decompose
the original full matrix with Nystr{\"{o}}m method. By selecting appropriate
landmark points, our theoretical analysis indicates that the loss for transfer
can be further simplified. Concretely, we find that the difference between the
original full kernel matrices between teacher and student can be well bounded
by that of the corresponding partial matrices, which only consists of
similarities between original examples and landmark points. Compared with the
full matrix, the size of the partial matrix is linear in the number of
examples, which improves the efficiency of optimization significantly. The
empirical study on benchmark data sets demonstrates the effectiveness of the
proposed algorithm. Code is available at \url{https://github.com/idstcv/KDA}.
