2025-11-16T15:10:11.983649

A note on generalized tensor CUR approximation for tensor pairs and tensor triplets based on the tubal product

Ahmadi-Asl, Rezaeian

In this note, we briefly present a generalized tensor CUR (GTCUR) approximation for tensor pairs (X,Y) and tensor triplets (X,Y,Z) based on the tubal product (t-product). We use the tensor Discrete Empirical Interpolation Method (TDEIM) to do these extensions. We show how the TDEIM can be utilized to generalize the classical tensor CUR (TCUR) approximation, which acts only on a single tensor, to jointly compute the TCUR of two and three tensors. This approach can be used to sample relevant lateral/horizontal slices of one data tensor relative to one or two other data tensors. For some special cases, the Generalized TCUR (GTCUR) approximation is reduced to the classical TCUR for both tensor pairs and tensor triplets in a similar fashion as shown for the matrices.

academic

A note on generalized tensor CUR approximation for tensor pairs and tensor triplets based on the tubal product

基本信息

论文ID: 2305.00754
标题: A note on generalized tensor CUR approximation for tensor pairs and tensor triplets based on the tubal product
作者: Salman Ahmadi-Asl (Innopolis University), Naeim Rezaeian (Peoples' Friendship University of Russia)
分类: math.NA cs.NA
发表时间: arXiv preprint, 2023年5月 (最新版本2025年1月)
论文链接: https://arxiv.org/abs/2305.00754

摘要

本文提出了基于管状积(t-product)的张量对(X,Y)和张量三元组(X,Y,Z)的广义张量CUR(GTCUR)近似方法。作者使用张量离散经验插值方法(TDEIM)来实现这些扩展，展示了如何利用TDEIM将经典的仅作用于单个张量的张量CUR(TCUR)近似推广到联合计算两个或三个张量的TCUR。该方法可用于相对于一个或两个其他数据张量采样一个数据张量的相关侧向/水平切片。

研究背景与动机

要解决的问题: 经典的CUR分解只能处理单个矩阵或张量，无法同时处理多个相关的数据结构。在实际应用中，经常需要同时分析多个相关的张量数据，提取一个数据集相对于其他数据集的最具判别性的特征。
问题的重要性:
- 现实世界的数据集通常具有多维结构，需要保持数据张量的结构
- 在子群发现、彩色噪声数据恢复、典型相关分析等应用中需要同时处理多个张量
- 传统方法无法有效利用多个张量之间的共同信息
现有方法的局限性:
- 矩阵CUR(MCUR)只能处理单个矩阵
- 现有的张量分解方法如Tucker分解、CP分解在截断时不能提供最优的低秩近似
- 缺乏针对多张量的统一处理框架
研究动机: 受到矩阵情况下广义MCUR成功应用的启发，作者希望将这一思想扩展到张量情况，利用基于t-产品的张量SVD的优良性质，开发能够同时处理多个张量的GTCUR方法。

核心贡献

提出了广义张量CUR(GTCUR)方法: 首次将CUR近似从单张量扩展到张量对和张量三元组的情况
开发了基于TDEIM的采样策略: 利用张量离散经验插值方法来选择最优的侧向/水平切片
建立了理论连接: 证明了GTCUR在特殊情况下可以退化为经典的TCUR，类似于矩阵情况
提供了高效算法: 给出了计算GTCUR的快速算法，包括在傅里叶域的高效实现
扩展了张量分解理论: 基于广义张量SVD(GTSVD)和限制张量SVD(t-RSVD)建立了完整的理论框架

方法详解

任务定义

张量对的GTCUR: 给定两个张量 $\mathbf{X} \in \mathbb{R}^{I_1 \times I_2 \times I_3}$ 和 $\mathbf{Y} \in \mathbb{R}^{I_4 \times I_2 \times I_3}$ ，找到近似： $\mathbf{X} \approx \mathbf{C}_1 \ast \mathbf{U}_1 \ast \mathbf{R}_1, \quad \mathbf{Y} \approx \mathbf{C}_2 \ast \mathbf{U}_2 \ast \mathbf{R}_2$

张量三元组的GTCUR: 给定三个张量 $\mathbf{X} \in \mathbb{R}^{I_1 \times I_2 \times I_3}$ , $\mathbf{Y} \in \mathbb{R}^{I_1 \times I_4 \times I_3}$ , $\mathbf{Z} \in \mathbb{R}^{I_5 \times I_2 \times I_3}$ ，找到相应的近似。

模型架构

1. 张量基础运算

论文基于管状积(t-product)定义了一系列张量运算：

t-product: $\mathbf{C} = \mathbf{X} \ast \mathbf{Y} = \text{fold}(\text{circ}(\mathbf{X}) \cdot \text{unfold}(\mathbf{Y}))$
张量转置: 对所有前向切片进行转置并反转顺序
正交张量: 满足 $\mathbf{X}^T \ast \mathbf{X} = \mathbf{X} \ast \mathbf{X}^T = \mathbf{I}$

2. 张量SVD (t-SVD)

$\mathbf{X} \approx \mathbf{U} \ast \mathbf{S} \ast \mathbf{V}^T$ 其中 $\mathbf{U}$ 和 $\mathbf{V}$ 是正交张量， $\mathbf{S}$ 是f-对角张量。

3. TDEIM算法

核心思想是构建张量插值投影算子： $\mathbf{P} = \mathbf{U} \ast (\mathbf{S}^T \ast \mathbf{U})^{-1} \ast \mathbf{S}^T$

采样过程：

选择第一个具有最大欧几里得范数的管状结构
迭代选择残差切片中范数最大的索引
使用投影算子去除已选方向的影响

技术创新点

统一的多张量处理框架: 通过共享因子矩阵实现多张量的联合分解
基于GTSVD的索引选择: 利用广义张量SVD提供的共同因子进行一致的切片采样
傅里叶域高效计算: 所有运算都可在频域并行执行，大大提高计算效率
理论保证: 提供了误差上界 $\|\mathbf{X}-\mathbf{C} \ast \mathbf{U} \ast \mathbf{R}\|_F^2 \leq (\tilde{\eta}_p + \tilde{\eta}_q)\sum_{i=1}^{I_3}\sum_{t>R}(\sigma_t^i)^2$