A lower bound on the tensor rank based on its maximally square matrix unfolding
A lower bound on the tensor rank based on its maximally square matrix unfolding
复制标题
基于最大方阵展开的张量秩的下界
DOI：
10.1016/j.sigpro.2020.107862
复制
发表时间：
2021
影响因子：
4.4
通讯作者：
Calvi G
中科院分区：
文献类型：
--
作者：
Calvi G
张量分解代表了一类以自然方式分析高维和多样性数据集的工具，典型多元分解(CPD)是其主要支柱。虽然CPD的概念与张量秩R的概念紧密地交织在一起，但与矩阵秩不同的是，由于计算CPD的相关计算负担，张量秩的计算是一个NP-Hard问题。为了帮助缓解这个问题，我们研究了张量秩下界，目的是提供一个更小的搜索空间，从而降低CPD计算的计算量。这是通过在R上可达到的最大下界和其长宽比最接近于单位(最大为平方)的张量的矩阵展开的维度之间建立联系来实现的。此外，我们证明了在非常温和的条件下可以得到这样的下界，这有助于有效地识别和计算实际的张量阶。数值算例和实际应用表明了该方法的有效性。
Tensor decompositions represent a class of tools for analysing datasets of high dimensionality and variety in a natural manner, with the Canonical Polyadic Decomposition (CPD) serving as a main pillar. While the notion of CPD is closely intertwined with that of the tensor rank, R, unlike the matrix rank, the computation of the tensor rank is an NP-hard problem, owing to the associated computational burden of evaluating the CPD. To help alleviate this issue, we investigate lower bounds on the tensor rank, with the aim to provide a reduced search space, and hence relax the computational costs of CPD evaluation. This is achieved by establishing a link between the maximum attainable lower bound on R and the dimensions of the matrix unfolding of the tensor for which the aspect ratio is closest to unity (maximally square). Moreover, we demonstrate that such lower bound can be attained under very mild conditions, which facilitates the efficient identification and computation of the actual tensor rank. Numerical examples and a real-world application demonstrate the benefits of this approach.