QR and LQ Decomposition Matrix Backpropagation Algorithms for Square, Wide, and Deep -- Real or Complex -- Matrices and Their Software Implementation

• URL: http://arxiv.org/abs/2009.10071v4
• Date: Fri, 11 Dec 2020 12:54:23 GMT
• Title: QR and LQ Decomposition Matrix Backpropagation Algorithms for Square, Wide, and Deep -- Real or Complex -- Matrices and Their Software Implementation
• Authors: Denisa A.O. Roberts and Lucas R. Roberts
• Abstract summary: This article presents matrix backpropagation algorithms for the QR decomposition of matrices $A_m, n$, that are either square (m = n), wide (m n), or deep (m > n), with rank $k = min(m, n)$. We derive novel matrix backpropagation results for the pivoted (full-rank) QR decomposition and for the LQ decomposition of deep input matrices.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This article presents matrix backpropagation algorithms for the QR decomposition of matrices $A_{m, n}$, that are either square (m = n), wide (m < n), or deep (m > n), with rank $k = min(m, n)$. Furthermore, we derive novel matrix backpropagation results for the pivoted (full-rank) QR decomposition and for the LQ decomposition of deep input matrices. Differentiable QR decomposition offers a numerically stable, computationally efficient method to solve least squares problems frequently encountered in machine learning and computer vision. Other use cases such as graph learning and network compression are listed in the article. Software implementation across popular deep learning frameworks (PyTorch, TensorFlow, MXNet) incorporate the methods for general use within the deep learning community. Furthermore, this article aids the practitioner in understanding the matrix backpropagation methodology as part of larger computational graphs.

Related papers

• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Deep Unrolling for Nonconvex Robust Principal Component Analysis [75.32013242448151]
  We design algorithms for Robust Component Analysis (A) It consists in decomposing a matrix into the sum of a low Principaled matrix and a sparse Principaled matrix.
  arXiv  Detail & Related papers  (2023-07-12T03:48:26Z)
• Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
  EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications. We propose a QR-based ED method dedicated to the application scenarios of computer vision.
  arXiv  Detail & Related papers  (2022-07-09T09:14:12Z)
• Efficient GPU implementation of randomized SVD and its applications [17.71779625877989]
  Matrix decompositions are ubiquitous in machine learning, including applications in dimensionality data compression and deep learning algorithms. Typical solutions for matrix decompositions have complexity which significantly increases their computational cost and time. We leverage efficient processing operations that can be run in parallel on modern Graphical Processing Units (GPUs) to reduce the computational burden of computing matrix decompositions.
  arXiv  Detail & Related papers  (2021-10-05T07:42:41Z)
• 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)
• Robust CUR Decomposition: Theory and Imaging Applications [9.280330114137778]
  This paper considers the use of Robust PCA in a CUR decomposition framework and applications thereof. We consider two key imaging applications of Robust PCA: video foreground-background separation and face modeling.
  arXiv  Detail & Related papers  (2021-01-05T17:58:15Z)
• Denise: Deep Robust Principal Component Analysis for Positive Semidefinite Matrices [8.1371986647556]
  Denise is a deep learning-based algorithm for robust PCA of covariance matrices. Experiments show that Denise matches state-of-the-art performance in terms of decomposition quality.
  arXiv  Detail & Related papers  (2020-04-28T15:45:21Z)
• 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)
• Fast Generalized Matrix Regression with Applications in Machine Learning [46.79740387890322]
  We propose a fast generalized matrix regression algorithm (Fast GMR) which utilizes sketching technique to solve the GMR problem efficiently. We apply the Fast GMR algorithm to the symmetric positive definite matrix approximation and single pass singular value decomposition.
  arXiv  Detail & Related papers  (2019-12-27T07:03:37Z)

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.