A new Linear Time Bi-level ${\ell }_{1,\infty }$ projection ; Application to the sparsification of auto-encoders neural networks

Abstract

The ${\ell }_{1,\infty }$ norm is an efficient-structured projection, but the complexity of the best algorithm is, unfortunately, $\mathcal{O}(nm\log (nm))$ for a matrix $n\times m$.\\ In this paper, we propose a new bi-level projection method, for which we show that the time complexity for the ${\ell }_{1,\infty }$ norm is only $\mathcal{O}\left(nm\right)$ for a matrix $n\times m$. Moreover, we provide a new ${\ell }_{1,\infty }$ identity with mathematical proof and experimental validation. Experiments show that our bi-level ${\ell }_{1,\infty }$ projection is $2.5$ times faster than the actual fastest algorithm and provides the best sparsity while keeping the same accuracy in classification applications.

arXiv admin note: substantial text overlap with arXiv:2405.02086