  A common technique for compressing a neural network is to compute the
$k$-rank $\ell_2$ approximation $A_{k,2}$ of the matrix
$A\in\mathbb{R}^{n\times d}$ that corresponds to a fully connected layer (or
embedding layer). Here, $d$ is the number of the neurons in the layer, $n$ is
the number in the next one, and $A_{k,2}$ can be stored in $O((n+d)k)$ memory
instead of $O(nd)$.
  This $\ell_2$-approximation minimizes the sum over every entry to the power
of $p=2$ in the matrix $A - A_{k,2}$, among every matrix
$A_{k,2}\in\mathbb{R}^{n\times d}$ whose rank is $k$. While it can be computed
efficiently via SVD, the $\ell_2$-approximation is known to be very sensitive
to outliers ("far-away" rows). Hence, machine learning uses e.g. Lasso
Regression, $\ell_1$-regularization, and $\ell_1$-SVM that use the
$\ell_1$-norm.
  This paper suggests to replace the $k$-rank $\ell_2$ approximation by
$\ell_p$, for $p\in [1,2]$. We then provide practical and provable
approximation algorithms to compute it for any $p\geq1$, based on modern
techniques in computational geometry.
  Extensive experimental results on the GLUE benchmark for compressing BERT,
DistilBERT, XLNet, and RoBERTa confirm this theoretical advantage. For example,
our approach achieves $28\%$ compression of RoBERTa's embedding layer with only
$0.63\%$ additive drop in the accuracy (without fine-tuning) in average over
all tasks in GLUE, compared to $11\%$ drop using the existing
$\ell_2$-approximation. Open code is provided for reproducing and extending our
results.
