A Structured Sparse Neural Network and Its Matrix Calculations Algorithm

• URL: http://arxiv.org/abs/2207.00903v1
• Date: Sat, 2 Jul 2022 19:38:48 GMT
• Title: A Structured Sparse Neural Network and Its Matrix Calculations Algorithm
• Authors: Seyyed Mostafa Mousavi Janbeh Sarayi and Mansour Nikkhah Bahrami
• Abstract summary: We introduce a nonsymmetric, tridiagonal matrix with offdiagonal sparse entries and offset sub and super-diagonals. For the cases where the matrix inverse does not exist, a least square type pseudoinverse is provided. Results show significant improvement in computational costs specially when the size of matrix increases.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Gradient descent optimizations and backpropagation are the most common methods for training neural networks, but they are computationally expensive for real time applications, need high memory resources, and are difficult to converge for many networks and large datasets. [Pseudo]inverse models for training neural network have emerged as powerful tools to overcome these issues. In order to effectively implement these methods, structured pruning maybe be applied to produce sparse neural networks. Although sparse neural networks are efficient in memory usage, most of their algorithms use the same fully loaded matrix calculation methods which are not efficient for sparse matrices. Tridiagonal matrices are one of the frequently used candidates for structuring neural networks, but they are not flexible enough to handle underfitting and overfitting problems as well as generalization properties. In this paper, we introduce a nonsymmetric, tridiagonal matrix with offdiagonal sparse entries and offset sub and super-diagonals as well algorithms for its [pseudo]inverse and determinant calculations. Traditional algorithms for matrix calculations, specifically inversion and determinant, of these forms are not efficient specially for large matrices, e.g. larger datasets or deeper networks. A decomposition for lower triangular matrices is developed and the original matrix is factorized into a set of matrices where their inverse matrices are calculated. For the cases where the matrix inverse does not exist, a least square type pseudoinverse is provided. The present method is a direct routine, i.e., executes in a predictable number of operations which is tested for randomly generated matrices with varying size. The results show significant improvement in computational costs specially when the size of matrix increases.

Related papers

• Graph Neural Networks and Applied Linear Algebra [1.8749305679160366]
  Graph neural networks (GNNs) are an approach suitable to sparse matrix computations. This paper provides an introduction to GNNs for a numerical linear algebra audience. Concrete examples are provided to illustrate how many common linear algebra tasks can be accomplished using GNNs.
  arXiv  Detail & Related papers  (2023-10-21T18:37:56Z)
• Multiresolution kernel matrix algebra [0.0]
  We show the compression of kernel matrices by means of samplets produces optimally sparse matrices in a certain S-format. The inverse of a kernel matrix (if it exists) is compressible in the S-format as well. The matrix algebra is justified mathematically by pseudo differential calculus.
  arXiv  Detail & Related papers  (2022-11-21T17:50:22Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Sparse Factorization of Large Square Matrices [10.94053598642913]
  In this paper, we propose to approximate a large square matrix with a product of sparse full-rank matrices. In the approximation, our method needs only $N(log N)2$ non-zero numbers for an $Ntimes N$ full matrix. We show that our method gives a better approximation when the approximated matrix is sparse and high-rank.
  arXiv  Detail & Related papers  (2021-09-16T18:42:21Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• Meta-learning for Matrix Factorization without Shared Rows or Columns [39.56814839510978]
  The proposed method uses a neural network that takes a matrix as input, and generates prior distributions of factorized matrices of the given matrix. The neural network is meta-learned such that the expected imputation error is minimized. In our experiments with three user-item rating datasets, we demonstrate that our proposed method can impute the missing values from a limited number of observations in unseen matrices.
  arXiv  Detail & Related papers  (2021-06-29T07:40:20Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach [4.710916891482697]
  A pseudoinverse is a generalization of a matrix inverse, which has been extensively utilized in machine learning. FastPI is a novel incremental singular value decomposition (SVD) based pseudoinverse method for sparse matrices. We show that FastPI computes the pseudoinverse faster than other approximate methods without loss of accuracy.
  arXiv  Detail & Related papers  (2020-11-09T07:47:10Z)
• What if Neural Networks had SVDs? [66.91160214071088]
  Various Neural Networks employ time-consuming matrix operations like matrix inversion. We present an algorithm that is fast enough to speed up several matrix operations.
  arXiv  Detail & Related papers  (2020-09-29T12:58:52Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
  arXiv  Detail & Related papers  (2020-02-23T03:07:31Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.