Matrix-free Krylov iteration for implicit convolution of numerically low-rank data

详细信息    查看全文

• 作者：Alex Breuer^a ; ^{alexander.m.breuer.civ@mail.mil" class="auth_mail" title="E-mail the corresponding author} ; Andrew Lumsdaine^b ; ^{lums@cs.indiana.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Low-rank approximation ; Convolution ; SVD ; PCA
• 刊名：Journal of Computational and Applied Mathematics
• 出版年：2016
• 出版时间：15 December 2016
• 年：2016
• 卷：308
• 期：Complete
• 页码：98-116
• 全文大小：1008 K

文摘

Evaluating the response of a linear shift-invariant system is a problem that occurs frequently in a wide variety of science and engineering problems. Calculating the system response via a convolution may be done efficiently with Fourier transforms. When one must compute the response of one system to m$m$ input signals, or the response of m$m$ systems to one signal, it may be the case that one may approximate all system responses without having to compute all m$m$ Fourier transforms. This can lead to substantial computational savings. Rather than process each point individually, one may only process basis vectors that span the output data space. However, to get a low-error approximation, it is necessary that the output vectors have low numerical rank if they were assembled into a matrix. We develop theory that shows how the singular value decay of a matrix ΦA$\Phi A$ that is a product of a convolution operator Φ$\Phi$ and an arbitrary matrix A$A$ depends in a linear fashion on the singular value decays of Φ$\Phi$ and A$A$. We propose gap-rank, a measure of the relative numerical rank of a matrix. We show that convolution cannot destroy the numerical low-rank-ness of ΦA$\Phi A$ data with only modest assumptions. We then develop a new method that exploits low-rank problems with block Golub–Kahan iteration in a Krylov subspace to approximate the low-rank problem. Our method can exploit parallelism in both the individual convolutions and the linear algebra operations in the block Golub–Kahan algorithm. We present numerical examples from signal and image processing that show the low error and scalability of our method.