Multi-level projection with exponential parallel speedup; Application to sparse auto-encoders neural networks

Code

• github.com/memo-p/projection
  OfficialIn paperpytorch★ 2

Abstract

The _1, norm is an efficient structured projection but the complexity of the best algorithm is unfortunately O(n m (n m)) for a matrix in R^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 O(n m ) for a matrix in R^n m, and O(n + m ) 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, instead of the product of the dimensions. we provide a large base of implementation of our framework for bi-level and tri-level (matrices and tensors) for various norms and provides also the parallel implementation. Experiments show that our projection is 2 times faster than the actual fastest Euclidean algorithms while providing same accuracy and better sparsity in neural networks applications.

Reproductions