Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2503.18921 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917967309045760 |
|---|---|
| author | Zhang, Yifan Fornace, Mark Lindsey, Michael |
| author_facet | Zhang, Yifan Fornace, Mark Lindsey, Michael |
| contents | In this work, we develop deterministic and random sketching-based algorithms for two types of tensor interpolative decompositions (ID): the core interpolative decomposition (CoreID, also known as the structure-preserving HOSVD) and the satellite interpolative decomposition (SatID, also known as the HOID or CURT). We adopt a new adaptive approach that leads to ID error bounds independent of the size of the tensor. In addition to the adaptive approach, we use tools from random sketching to enable an efficient and provably accurate calculation of these decompositions. We also design algorithms specialized to tensors that are sparse or given as a sum of rank-one tensors, i.e., in the CP format. Besides theoretical analyses, numerical experiments on both synthetic and real-world data demonstrate the power of the proposed algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_18921 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Fast and Accurate Interpolative Decompositions for General, Sparse, and Structured Tensors Zhang, Yifan Fornace, Mark Lindsey, Michael Numerical Analysis 15A69, 65F55, 68W20 In this work, we develop deterministic and random sketching-based algorithms for two types of tensor interpolative decompositions (ID): the core interpolative decomposition (CoreID, also known as the structure-preserving HOSVD) and the satellite interpolative decomposition (SatID, also known as the HOID or CURT). We adopt a new adaptive approach that leads to ID error bounds independent of the size of the tensor. In addition to the adaptive approach, we use tools from random sketching to enable an efficient and provably accurate calculation of these decompositions. We also design algorithms specialized to tensors that are sparse or given as a sum of rank-one tensors, i.e., in the CP format. Besides theoretical analyses, numerical experiments on both synthetic and real-world data demonstrate the power of the proposed algorithms. |
| title | Fast and Accurate Interpolative Decompositions for General, Sparse, and Structured Tensors |
| topic | Numerical Analysis 15A69, 65F55, 68W20 |
| url | https://arxiv.org/abs/2503.18921 |