A new Linear Time Bi-level ℓ1,∞ projection ; Application to the sparsification of auto-encoders neural networks

The ℓ1,∞ norm is an efficient-structured projection, but the complexity of the best algorithm is, unfortunately, Obig(n m log(n m)big) for a matrix n× m. In this paper, we propose a new bi-level projection method, for which we show that the time complexity for the ℓ1,∞ norm is only Obig(n m big) for a matrix n× m. Moreover, we provide a new ℓ1,∞ identity with mathematical proof and experimental validation. Experiments show that our bi-level ℓ1,∞ projection is 2.5 times faster than the actual fastest algorithm and provides the best sparsity while keeping the same accuracy in classification applications.