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

The ${\mathrm{\ell }}_{1,\mathrm{\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 ${\mathrm{\ell }}_{1,\mathrm{\infty }}$ norm is only $\mathcal{O}\left(nm\right)$ for a matrix $n\times m$. Moreover, we provide a new ${\mathrm{\ell }}_{1,\mathrm{\infty }}$ identity with mathematical proof and experimental validation. Experiments show that our bi-level ${\mathrm{\ell }}_{1,\mathrm{\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.