The $\ell_{1,\infty}$ norm is an efficient structured projection but the
complexity of the best algorithm is unfortunately $\mathcal{O}\big(n m \log(n
m)\big)$ for a matrix in $\mathbb{R}^{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}\big(n m \big)$ for a matrix in
$\mathbb{R}^{n\times m}$, and $\mathcal{O}\big(n + m \big)$ with full parallel
power. We generalize our method to tensors and we propose a new multi-level
projection, having an induced decomposition that yields a linear parallel
speedup up to an exponential speedup factor, resulting in a time complexity
lower-bounded by the sum of the dimensions. Experiments show that our bi-level
$\ell_{1,\infty}$ projection is $2.5$ times faster than the actual fastest
algorithm provided by \textit{Chu et. al.} while providing same accuracy and
better sparsity in neural networks applications.

提出了一种新的双层投影方法，其 l1,inf 范数在矩阵中的时间复杂度仅为 O (nm)，在具有完全并行能力时为 O (n+m)，同时还将方法推广到张量，并提出了一个引发线性并行加速和指数加速因子的分解的多级投影方法，结果是时间复杂度的下限为维度之和。实验证明，该双层 l1,inf 投影方法比文献中提供的最快算法快 2.5 倍，同时在神经网络应用中具有相同的准确度和更好的稀疏性。