## Abstract

In this paper new general modewise Johnson-Lindenstrauss (JL) subspace embeddings are proposed that can be both generated much faster and stored more easily than traditional JL embeddings when working with extremely large vectors and/or tensors. Corresponding embedding results are then proven for two different types of low-dimensional (tensor) subspaces. The first of these new subspace embedding results produces improved space complexity bounds for embeddings of rank-r tensors whose CP decompositions are contained in the span of a fixed (but unknown) set of r rank-1 basis tensors. In the traditional vector setting this first result yields new and very general near-optimal oblivious subspace embedding constructions that require fewer random bits to generate than standard JL embeddings when embedding subspaces of C^{N} spanned by basis vectors with special Kronecker structure. The second result proven herein provides new fast JL embeddings of arbitrary r-dimensional subspaces S ⊆ C^{N} which also require fewer random bits (and so are easier to store, i.e., require less space) than standard fast JL embedding methods in order to achieve small ∊ - distortions. These new oblivious subspace embedding results work by (i) effectively folding any given vector in S into a (not necessarily low-rank) tensor, and then (ii) embedding the resulting tensor into C^{m} for m ≤ Cr log^{c}(N)/∊^{2}. Applications related to compression and fast compressed least squares solution methods are also considered, including those used for fitting low-rank CP decompositions, and the proposed JL embedding results are shown to work well numerically in both settings.

Original language | English (US) |
---|---|

Pages (from-to) | 376-416 |

Number of pages | 41 |

Journal | SIAM Journal on Matrix Analysis and Applications |

Volume | 42 |

Issue number | 1 |

DOIs | |

State | Published - 2021 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Analysis

## Keywords

- CP decompositions
- Dimensionality reduction
- Fast approximation algorithms
- Johnson-Lindenstrauss embeddings
- Least squares fitting
- Low-rank tensors
- Tensors