0
$\begingroup$

Problem

I was wondering if there are any theoretical results that tackle the following problem:

Construct the following matrices $\mathbf{\mathcal{S}_{1}},\mathbf{\mathcal{S}_{2}},\ldots,\mathbf{\mathcal{S}_{p}}$ all of size $m\times n$ with $m\geqslant n$. The goal is to compute: $$ \mathbf{\mathcal{S}}=\mathcal{S}_{1}+\mathcal{S}_{2}+\ldots+\mathcal{S}_{p} $$ not explicitly

My goal is to add up these matrices not explicitly but rather by performing QR or SVD on each individual matrix and attempting to take advantage of the properties of the (assuming QR decomposition) orthonormal matrices $\mathbf{Q_{\mathcal{S}_{1}}},\mathbf{Q_{\mathcal{S}_{2}}},\ldots,\mathbf{Q_{\mathcal{S}_{p}}}$ and the upper triangular matrices $\mathbf{R_{\mathcal{S}_{1}}},\mathbf{R_{\mathcal{S}_{2}}},\ldots,\mathbf{R_{\mathcal{S}_{p}}}$ somehow (not by literally adding each pair together). Therefore, are there any theoretical result for matrix-matrix addition using matrix decomposition for the sake of computational feasibility and can the same be said using SVD?

Motivation

Many matrix decomposition allow computations to be simpler by exploiting their special properties. The most important aspect of handling matrices numerically is to reduce numerical errors obtained due to finite precision on computers for instance addition operation of matrices are sometimes subject to the issue of absorption. Therefore, it might/might not be useful to look at the properties of matrix decompositions to tackle this issue which is why I am asking this question and I would be grateful for any comment/answer :)

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ trying to understand what you are hoping for; take $n=1$, so you are adding vectors, what alternative is there to adding them elementwise? $\endgroup$
    – Carlo Beenakker
    Jul 4, 2021 at 20:41
  • $\begingroup$ Let's assume we're taking two matrices $\mathbf{\mathcal{S}_{1}}$ and $\mathbf{\mathcal{S}_{2}}$ and we sum them up. Suppose I want to compute $\det(\mathbf{\mathcal{S}_{1}}+\mathbf{\mathcal{S}_{2}})$ or $\operatorname{tr}(\mathbf{\mathcal{S}_{1}}+\mathbf{\mathcal{S}_{2}})$ where I am dealing with matrices that could possible have elements with scale of $\epsilon<<<1$ and $1/\epsilon$, one thing that addition of these two elements does in finite precision is that $\epsilon$ gets absorbed in such cases and this could result in worst case wrong results. @CarloBeenakker $\endgroup$
    – Mykael Yuday
    Jul 4, 2021 at 20:46
  • 2
    $\begingroup$ Factorizations and sums hardly ever interact, in a very general setting. For instance, knowing how to factor into primes $a,b\in\mathbb{Z}$ will tell you nothing on how to factor $a+b$, barring special cases where there is a common factor. $\endgroup$
    – Federico Poloni
    Jul 5, 2021 at 9:28
  • $\begingroup$ Computing the sum directly needs $mnp$ additions. Every matrix decomposition needs more operations than $mn$, so I don't see the point. Am I missing something? $\endgroup$
    – Dirk
    Sep 18, 2021 at 8:14

1 Answer 1

Reset to default
0
$\begingroup$

If your matrices happen to be low-rank, you might want to consider a simultaneous low-rank approximation of your matrices (as in Inoue and Urahama - Equivalence of Non-Iterative Algorithms for Simultaneous Low Rank Approximations of Matrices), i.e. you compute $$ \min_{A,M_i,B} \sum_{i=1}^p \lVert S_i - A M_i B \rVert_F^2, $$ where $M_i$ are potentially smaller than $S_i$. You could then compute $$ S \approx A \bigl( \sum_{i=1}^p M_i \bigr) B.$$

I am however not aware of any result on the error of $S$. I would suspect that the error is equal to the sum of the individual low-rank approximation errors.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.