Localization of matrix factorizations

DOI10.1007/S10208-014-9196-XMaRDI QIDQ896551zbMATH OpenOpenAlexWikidataFDO

Authors Ilya A. Krishtal, Thomas Strohmer, Tim Wertz

Publication date 10 December 2015

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.1618

Abstract: Matrices with off-diagonal decay appear in a variety of fields in mathematics and in numerous applications, such as signal processing, statistics, communications engineering, condensed matter physics, and quantum chemistry. Numerical algorithms dealing with such matrices often take advantage (implicitly or explicitly) of the empirical observation that this off-diagonal decay property seems to be preserved when computing various useful matrix factorizations, such as the Cholesky factorization or the QR-factorization. There is a fairly extensive theory describing when the inverse of a matrix inherits the localization properties of the original matrix. Yet, except for the special case of band matrices, surprisingly very little theory exists that would establish similar results for matrix factorizations. We will derive a comprehensive framework to rigorously answer the question when and under which conditions the matrix factors inherit the localization of the original matrix for such fundamental matrix factorizations as the LU-, QR-, Cholesky, and Polar factorization.

Review text

Let \(\mathcal{A}\) be a Banach algebra of matrices in \(\mathcal{B}(\ell^2)\) and \(A \in \mathcal{A}\). Denote by \(\mathcal{L}\) the subalgebra of \(\mathcal{B}(\ell^2)\) consisting of lower triangular matrices, and \(\mathcal{L}^*\) the subalgebra consisting of upper triangular matrices. We say that \(A\) admits {\parindent=6mm \begin{itemize} \item[1.] an LU factorization in \(\mathcal{A}\) if \(A = LU\), where \(L,L^{-1} \in \mathcal{L} \cap \mathcal{A}\) and \(U,U^{-1} \in \mathcal{L}^* \cap \mathcal{A}\); \item [2.] a QR factorization in \(\mathcal{A}\) if \(A = QR\), where \(R,R^{-1} \in \mathcal{L}^* \cap \mathcal{A}\) and \(Q \in \mathcal{A}\) is unitary; \item [3.] a Cholesky factorization in \(\mathcal{A}\) if \(A\) is Hermitian positive definite, and \(A = C^*C\), where \(C,C^{-1} \in \mathcal{L} \cap \mathcal{A}\) and the diagonal entries of \(C\) are positive; \item [4.] a polar factorization in \(\mathcal{A}\) if \(A = UP\), where \(U \in \mathcal{A}\) is unitary and \(P \in \mathcal{A}\) is Hermitian positive semidefinite. \end{itemize}} The following subalgebras \(\mathcal{A}\) with off-diagonal decay are considered: {\parindent=6mm \begin{itemize} \item[1.] The Jaffard class \(\mathcal{A}_s\), where \(s > 1\), consisting of all matrices \(A = [a_{jk}]\) satisfying \[ |a_{jk}| \leq C (1+|j-k|)^{-s} \] for some \(C > 0\). \item [2.] The subalgebra \(\mathcal{A}_v\), consisting of all matrices \(A = [a_{jk}]\) satisfying \[ |a_{jk}| \leq Cv^{-1}(j-k), \] where \(C > 0\), and \(v\) is an admissible weight with the properties \(v^{-1} \in \ell^1(\mathbb{Z})\) and \(v^{-1} * v^{-1} \leq Cv^{-1}\). \item [3.] The Schur-type algebra \(\mathcal{A}_v^1\), consisting of all matrices \(A = [a_{jk}]\) satisfying \[ \sup_{j \in \mathbb{Z}} \sum_{k \in \mathbb{Z}} |a_{jk}|v(j-k) < \infty \text{ and } \sup_{k \in \mathbb{Z}} \sum_{j \in \mathbb{Z}} |a_{jk}|v(j-k) < \infty, \] where \(v\) is an admissible weight. \item [4.] The Gohberg-Baskakov-Sjöstrand class \(\mathcal{C}_v\), consisting of all matrices \(A = [a_{jk}]\) satisfying \[ \sum_{j \in \mathbb{Z}} \sup_{k \in \mathbb{Z}} |a_{k, k-j}|v(j) < \infty, \] where \(v\) is an admissible weight. \end{itemize}} The following are the main results: {\parindent=6mm \begin{itemize} \item[1.] Let \(\mathcal{A}\) be either \(\mathcal{A}_v\), \(\mathcal{A}_v^1\), or \(\mathcal{C}_v\). Let \(A \in \mathcal{A}\). If \(A\) has an LU factorization in \(\mathcal{B}(\ell^2)\), then \(A\) admits an LU factorization in \(\mathcal{A}\). \item [2.] Let \(\mathcal{A}\) be either \(\mathcal{A}_s\), \(\mathcal{A}_v\), \(\mathcal{A}_v^1\), or \(\mathcal{C}_v\). Then any Hermitian positive definite \(A \in \mathcal{A}\) admits a Cholesky factorization in \(\mathcal{A}\). \item [3.] Let \(\mathcal{A}\) be either \(\mathcal{A}_s\), \(\mathcal{A}_v\), \(\mathcal{A}_v^1\), or \(\mathcal{C}_v\). Let \(A \in \mathcal{A}\) be invertible. If \(A\) has a QR factorization in \(\mathcal{B}(\ell^2)\), then \(A\) admits a QR factorization in \(\mathcal{A}\). \item [4.] Let \(\mathcal{A}\) be either \(\mathcal{A}_s\), \(\mathcal{A}_v\), \(\mathcal{A}_v^1\), or \(\mathcal{C}_v\). Let \(A \in \mathcal{A}\) be invertible. If \(A\) has a polar factorization in \(\mathcal{B}(\ell^2)\), then \(A\) admits a polar factorization in \(\mathcal{A}\). \end{itemize}}

Recommendations

Cites work

Cited in

(17)

This page was built for publication: Localization of matrix factorizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q896551)