Fast randomized matrix and tensor interpolative decomposition using CountSketch
- PDF / 673,984 Bytes
- 28 Pages / 439.642 x 666.49 pts Page_size
- 117 Downloads / 233 Views
Fast randomized matrix and tensor interpolative decomposition using CountSketch Osman Asif Malik1
· Stephen Becker1
Received: 9 September 2019 / Accepted: 30 September 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We propose a new fast randomized algorithm for interpolative decomposition of matrices which utilizes COUNTSKETCH. We then extend this approach to the tensor interpolative decomposition problem introduced by Biagioni et al. (J. Comput. Phys. 281(C), 116–134 (2015)). Theoretical performance guarantees are provided for both the matrix and tensor settings. Numerical experiments on both synthetic and real data demonstrate that our algorithms maintain the accuracy of competing methods, while running in less time, achieving at least an order of magnitude speedup on large matrices and tensors. Keywords Matrix decomposition · Tensor decomposition · Sketching Mathematics Subject Classification (2010) 15-02
1 Introduction Matrix decomposition is a fundamental tool used to compress and analyze data, and to improve the speed of computations. For data and computational problems involving more than two dimensions, analogous tools in the form of tensors and associated decompositions have been developed [36]. In many modern applications, matrices
Communicated by: Gunnar J Martinsson Osman Asif Malik
[email protected] Stephen Becker [email protected] 1
Department of Applied Mathematics, University of Colorado Boulder, Boulder, CO, USA
76
Page 2 of 28
Adv Comput Math
(2020) 46:76
and tensors can be very large, which makes decomposing them especially challenging. One approach to dealing with this problems is to incorporate randomization in decomposition algorithms [33]. In this paper, we consider the interpolative decomposition (ID) for matrices, as well as the tensor ID problem. By tensor ID, we mean the tensor rank reduction problem as introduced by [8]; we provide an exact definition in Section 1.2.2. We make the following contributions in this paper: – –
– –
We propose a new fast randomized algorithm for matrix ID and provide theoretical performance guarantees. We propose a new randomized algorithm for tensor ID. To the best of our knowledge, we provide the first performance guarantees for any randomized tensor ID algorithm. We validate our algorithms on both synthetic and real data. We propose a small modification to the standard COUNTSKETCH formulation which helps avoid certain rank deficiency issues and slightly strengthen our matrix ID results.
1.1 Tensors and the CP decomposition For a more complete introduction to tensors and their decompositions, see the review paper by [36]. A tensor X ∈ RI1 ×I2 ×···×IN is an N-dimensional array of real numbers, also called an N-way tensor. The number of elements in such a tensor is def denoted by I˜ = N n=1 In . Boldface Euler script letters, e.g., X, denote tensors of dimension 3 or greater; bold capital letters, e.g., X, denote matrices; bold lowercase letters, e.g., x, denote vectors; and lowercase le
Data Loading...
